选择排序,选择排序为什么不稳定
为什么说选择排序不稳定?
因为你的序列并非随机数。
1.你的待排序列有个隐藏的边界，即满分、零分。
2.你根据经验，引入了归并排序的思想，而且你还对分堆有一个经验上预测（不同分段人数）。
3.数据的存储结构（实体的试卷）非常适合“插入”、“分堆”这样的操作，而最常见的二元swap，copy就不太便利。
假设满分为100分：
边界分数你第一轮遍历就可以以100%的概率放到正确的位置（比如100分，99分，0分，1分），离边界越近的分数就越容易达成这个效果（比如98分，97分，3分，2分），砍掉了随机数测试中可能会出现重排概率。
所以对于你的特例，经过你改良的选择排序就会非常稳定，而且排序的操作很适合实体的试卷。
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。
以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。
那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。
举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。
常见的排序算法—选择，冒泡，插入，快速，归并
太久没看代码了，最近打算复习一下java，又突然想到了排序算法，就把几种常见的排序算法用java敲了一遍，这里统一将无序的序列从小到大排列。
选择排序是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小元素，继续放在下一个位置，直到待排序元素个数为0。
选择排序代码如下：
public void Select_sort(int[] arr) {
int temp,index;
for( int i=0;i10;i++) {
index = i;
for(int j = i + 1 ; j 10 ; j++) {
if(arr[j] arr[index])
index = j;
}
/*
temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
*/
swap(arr,i,index);
}
System.out.print("经过选择排序后：");
for(int i = 0 ; i 10 ; i++)
System.out.print( arr[i] +" ");
System.out.println("");
}
冒泡排序是一种比较基础的排序算法，其思想是相邻的元素两两比较，较大的元素放后面，较小的元素放前面，这样一次循环下来，最大元素就会归位，若数组中元素个数为n，则经过（n-1）次后，所有元素就依次从小到大排好序了。整个过程如同气泡冒起，因此被称作冒泡排序。
选择排序代码如下：
public void Bubble_sort(int[] arr) {
int temp;
for(int i = 0 ; i 9 ; i++) {
for(int j = 0 ; j 10 - i - 1 ;j++) {
if(arr[j] arr[j+1]) {
/*
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
*/
swap(arr,j,j+1);
}
}
}
System.out.print("经过冒泡排序后：");
for(int i = 0 ; i 10 ; i++)
System.out.print( arr[i] +" ");
System.out.println("");
}
插入排序也是一种常见的排序算法，插入排序的思想是：创建一个与待排序数组等大的数组，每次取出一个待排序数组中的元素，然后将其插入到新数组中合适的位置，使新数组中的元素保持从小到大的顺序。
插入排序代码如下：
public void Insert_sort(int[] arr) {
int length = arr.length;
int[] arr_sort = new int[length];
int count = 0;
for(int i = 0;i length; i++) {
if(count == 0) {
arr_sort[0] = arr[0];
}else if(arr[i] = arr_sort[count - 1]) {
arr_sort[count] = arr[i];
}else if(arr[i] arr_sort[0]) {
insert(arr,arr_sort,arr[i],0,count);
}else {
for(int j = 0;j count - 1; j++) {
if(arr[i] = arr_sort[j] arr[i] arr_sort[j+1]) {
insert(arr,arr_sort,arr[i],j+1,count);
break;
}
}
}
count++;
}
System.out.print("经过插入排序后：");
for(int i = 0 ; i 10 ; i++)
System.out.print( arr_sort[i] +" ");
System.out.println("");
}
public void insert(int[] arr,int[] arr_sort,int value,int index,int count) {
for(int i = count; i index; i--)
arr_sort[i] = arr_sort[i-1];
arr_sort[index] = value;
}
快速排序的效率比冒泡排序算法有大幅提升。因为使用冒泡排序时，一次外循环只能归位一个值，有n个元素最多就要执行（n-1）次外循环。而使用快速排序时，一次可以将所有元素按大小分成两堆，也就是平均情况下需要logn轮就可以完成排序。
快速排序的思想是：每趟排序时选出一个基准值（这里以首元素为基准值），然后将所有元素与该基准值比较，并按大小分成左右两堆，然后递归执行该过程，直到所有元素都完成排序。
public void Quick_sort(int[] arr, int left, int right) {
if(left = right)
return ;
int temp,t;
int j = right;
int i = left;
temp = arr[left];
while(i j) {
while(arr[j] = temp i j)
j--;
while(arr[i] = temp i j)
i++;
if(i j) {
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
arr[left] = arr[i];
arr[i] = temp;
Quick_sort(arr,left, i - 1);
Quick_sort(arr, i + 1, right);
}
归并排序是建立在归并操作上的一种有效的排序算法，归并排序对序列的元素进行逐层折半分组，然后从最小分组开始比较排序，每两个小分组合并成一个大的分组，逐层进行，最终所有的元素都是有序的。
public void Mergesort(int[] arr,int left,int right) {
if(right - left 0) {
int[] arr_1 = new int[(right - left)/2 + 1];
int[] arr_2 = new int[(right - left + 1)/2];
int j = 0;
int k = 0;
for(int i = left;i = right;i++) {
if(i = (right + left)/2) {
arr_1[j++] = arr[i];
}else {
arr_2[k++] = arr[i];
}
}
Mergesort(arr_1,0,(right - left)/2);
Mergesort(arr_2,0,(right - left - 1)/2);
Merge(arr_1,arr_2,arr);
}
}
public void Merge(int[] arr_1,int[] arr_2,int[] arr) {
int i = 0;
int j = 0;
int k = 0;
int L1 = arr_1.length;
int L2 = arr_2.length;
while(i L1 j L2) {
if(arr_1[i] = arr_2[j]) {
arr[k] = arr_1[i];
i++;
}else {
arr[k] = arr_2[j];
j++;
}
k++;
}
if(i == L1) {
for(int t = j;j L2;j++)
arr[k++] = arr_2[j];
}else {
for(int t = i;i L1;i++)
arr[k++] = arr_1[i];
}
}
归并排序这里我使用了left，right等变量，使其可以通用，并没有直接用数字表示那么明确，所以给出相关伪代码，便于理解。
Mergesort(arr[0...n-1])
//输入：一个可排序数组arr[0...n-1]
//输出：非降序排列的数组arr[0...n-1]
if n1
copy arr[0...n/2-1] to arr_1[0...(n+1)/2-1]//确保arr_1中元素个数=arr_2中元素个数
//对于总个数为奇数时，arr_1比arr_2中元素多一个；对于总个数为偶数时，没有影响
copy arr[n/2...n-1] to arr_2[0...n/2-1]
Mergesort(arr_1[0...(n+1)/2-1])
Mergesort(arr_2[0...n/2-1])
Merge(arr_1,arr_2,arr)
Merge(arr_1[0...p-1],arr_2[0...q-1],arr[0...p+q-1])
//输入：两个有序数组arr_1[0...p-1]和arr_2[0...q-1]
//输出：将arr_1与arr_2两数组合并到arr
int i-0;j-0;k-0
while i
p span="" do="" j
if arr_1[i] = arr_2[j]
arr[k] - arr_1[i]
i-i+1
else arr[k] - arr_2[j];j-j+1
k-k+1
if i=p
copy arr_2[j...q-1] to arr[k...p+q-1]
else copy arr_1[i...p-1] to arr[k...p+q-1]
package test_1;
import java.util.Scanner;
public class Test01 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] arr_1 = new int[10];
for(int i = 0 ; i 10 ; i++)
arr_1[i] = sc.nextInt();
Sort demo_1 = new Sort();
//1~5一次只能运行一个，若多个同时运行，则只有第一个有效，后面几个是无效排序。因为第一个运行的已经将带排序数组排好序。
demo_1.Select_sort(arr_1);//-----------------------1
//demo_1.Bubble_sort(arr_1);//---------------------2
/* //---------------------3
demo_1.Quick_sort(arr_1, 0 , arr_1.length - 1);
System.out.print("经过快速排序后：");
for(int i = 0 ; i 10 ; i++)
System.out.print( arr_1[i] +" ");
System.out.println("");
*/
//demo_1.Insert_sort(arr_1);//--------------------4
/* //--------------------5
demo_1.Mergesort(arr_1,0,arr_1.length - 1);
System.out.print("经过归并排序后：");
for(int i = 0 ; i 10 ; i++)
System.out.print( arr_1[i] +" ");
System.out.println("");
*/
}
}
class Sort {
public void swap(int arr[],int a, int b) {
int t;
t = arr[a];
arr[a] = arr[b];
arr[b] = t;
}
public void Select_sort(int[] arr) {
int temp,index;
for( int i=0;i10;i++) {
index = i;
for(int j = i + 1 ; j 10 ; j++) {
if(arr[j] arr[index])
index = j;
}
/*
temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
*/
swap(arr,i,index);
}
System.out.print("经过选择排序后：");
for(int i = 0 ; i 10 ; i++)
System.out.print( arr[i] +" ");
System.out.println("");
}
public void Bubble_sort(int[] arr) {
int temp;
for(int i = 0 ; i 9 ; i++) {
for(int j = 0 ; j 10 - i - 1 ;j++) {
if(arr[j] arr[j+1]) {
/*
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
*/
swap(arr,j,j+1);
}
}
}
System.out.print("经过冒泡排序后：");
for(int i = 0 ; i 10 ; i++)
System.out.print( arr[i] +" ");
System.out.println("");
}
public void Quick_sort(int[] arr, int left, int right) {
if(left = right)
return ;
int temp,t;
int j = right;
int i = left;
temp = arr[left];
while(i j) {
while(arr[j] = temp i j)
j--;
while(arr[i] = temp i j)
i++;
if(i j) {
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
arr[left] = arr[i];
arr[i] = temp;
Quick_sort(arr,left, i - 1);
Quick_sort(arr, i + 1, right);
}
public void Insert_sort(int[] arr) {
int length = arr.length;
int[] arr_sort = new int[length];
int count = 0;
for(int i = 0;i length; i++) {
if(count == 0) {
arr_sort[0] = arr[0];
}else if(arr[i] = arr_sort[count - 1]) {
arr_sort[count] = arr[i];
}else if(arr[i] arr_sort[0]) {
insert(arr,arr_sort,arr[i],0,count);
}else {
for(int j = 0;j count - 1; j++) {
if(arr[i] = arr_sort[j] arr[i] arr_sort[j+1]) {
insert(arr,arr_sort,arr[i],j+1,count);
break;
}
}
}
count++;
}
System.out.print("经过插入排序后：");
for(int i = 0 ; i 10 ; i++)
System.out.print( arr_sort[i] +" ");
System.out.println("");
}
public void insert(int[] arr,int[] arr_sort,int value,int index,int count) {
for(int i = count; i index; i--)
arr_sort[i] = arr_sort[i-1];
arr_sort[index] = value;
}
public void Mergesort(int[] arr,int left,int right) {
if(right - left 0) {
int[] arr_1 = new int[(right - left)/2 + 1];
int[] arr_2 = new int[(right - left + 1)/2];
int j = 0;
int k = 0;
for(int i = left;i = right;i++) {
if(i = (right + left)/2) {
arr_1[j++] = arr[i];
}else {
arr_2[k++] = arr[i];
}
}
Mergesort(arr_1,0,(right - left)/2);
Mergesort(arr_2,0,(right - left - 1)/2);
Merge(arr_1,arr_2,arr);
}
}
public void Merge(int[] arr_1,int[] arr_2,int[] arr) {
int i = 0;
int j = 0;
int k = 0;
int L1 = arr_1.length;
int L2 = arr_2.length;
while(i L1 j L2) {
if(arr_1[i] = arr_2[j]) {
arr[k] = arr_1[i];
i++;
}else {
arr[k] = arr_2[j];
j++;
}
k++;
}
if(i == L1) {
for(int t = j;j L2;j++)
arr[k++] = arr_2[j];
}else {
for(int t = i;i L1;i++)
arr[k++] = arr_1[i];
}
}
}
若有错误，麻烦指正，不胜感激。
什么叫选择法排序？
选择排序法
是对
定位比较交换法
的一种改进。在讲选择排序法之前我们先来了解一下定位比较交换法。为了便于理解，设有10个数分别存在数组元素a[0]～a[9]中。定位比较交换法是由大到小依次定位a[0]～a[9]中恰当的值（和武林大会中的比武差不多），a[9]中放的自然是最小的数。如定位a[0],先假定a[0]中当前值是最大数，a[0]与后面的元素一一比较，如果a[4]更大，则将a[0]、a[4]交换，a[0]已更新再与后面的a[5]～a[9]比较，如果a[8]还要大，则将a[0]、a[8]交换，a[0]又是新数，再与a[9]比较。一轮比完以后，a[0]就是最大的数了，本次比武的武状元诞生了，接下来从a[1]开始，因为状元要休息了，再来一轮a[1]就是次大的数，也就是榜眼，然后从a[2]开始，比出探花，真成比武大会了，当比到a[8]以后，排序就完成了
选择法排序
选择法排序是一种简单的容易实现的对数据排序的算法，以整形数组元素为例，有数组A[10]，即A[0]，A[1]…A[8]，A[9]（假设其元素均互不相同），要求对其元素排序使之递增有序。
首先以一个元素为基准，从一个方向开始扫描，比如从左至右扫描，以A[0]为基准，接下来从A[0]…A[9]中找出最小的元素，将其与A[0]交换。
C语言选择排序详解
工作原理是每一次从无序组的数据元素中选出最小（或最大）的一个元素，存放在无序组的起始位置，无序组元素减少，有序组元素增加，直到全部待排序的数据元素排完。
以升序为例的图解：
代码：
#includestdio.h
void SelectionSort(int *num,int n)
{
int i = 0;
int min = 0;
int j = 0;
int tmp = 0;
for(i = 0;i n-1;i++)
{
min = i;//每次讲min置成无序组起始位置元素下标。
for(j = i;j n;j++)//遍历无序组，找到最小元素。
{
if(num[min]num[j])
{
min = j;
}
}
if(min != i)//如果最小元素不是无序组起始位置元素，则与起始元素交换位置。
{
tmp = num[min];
num[min] = num[i];
num[i] = tmp;
}
}
}
（此处空一行）
int main()
{
int num[6] = {5,4,3,2,9,1};
int i = 0;
SelectionSort(num,6);//这里需要将数列元素个数传入，有心者可用sizeof在函数内求得元素个数。
for(i = 0;i 6;i++)
{
printf("%d ",num[i]);
}
return 0;
}