选择排序的稳定版本与非稳定版本

选择排序

非稳定版本与稳定版本

排序过程中选择一个比较大（大到小排序）的数，然后把它放到数组中指定的位置；这时候可以直接与数组中指定位置交换数据，但是可能会导致同值的数据的顺序发生改变，这就是所谓的“不稳定”。可以通过下图来理解所谓的“稳定”和“非稳定”。

• 不稳定排序算法按数字排序时，会打乱原本同值的花色顺序
  [[?7], [?2], [?4], [?5], [?2], [?5]]
  [[?7], [?5], [?5], [?4], [?2], [?2]]
  原来 ?2 在前 ?2 在后，按数字再排后，他俩的位置变了
• 稳定排序算法按数字排序时，会保留原本同值的花色顺序，如下所示 ?2 与 ?2 的相对位置不变
  [[?7], [?2], [?4], [?5], [?2], [?5]]
  [[?7], [?5], [?5], [?4], [?2], [?2]]

代码示例（C实现）

//非稳定版本void move_selected_unstable_version(int *arr, int i, int m) {    if(m != i) 	//如果选择的这个数已经是在i位置（当前要放置的位置）就不用移动了    {        int tmp = arr[m];        arr[m] = arr[i];        arr[i] = tmp;    }}// 稳定版本，为了把 arr[m] 移动到 i，需要把中间的所有元素都右移void move_selected_stable_version(int *arr, int i, int m) {    int j, tmp;    if(m != i) 	//如果选择的这个数已经是在i位置（当前要放置的位置）就不用移动了    {        tmp = arr[m];        for(j = m; j > i; --j) 		{            arr[j] = arr[j - 1];        }        arr[i] = tmp;    }}//选择排序void select_sort(int *array, int size){	int max;	int pos;	int i,j;	for(i = 0; i < size-1; i++)	//循环一次就找到一个较大的数，然后与数组的第n个数据交换位置(n从0开始)	{		max = array[i];		pos = i;				for(j = i; j <= size-1; j++)		{			if(array[j] > max)			{				max = array[j];				pos = j;			}		}		move_selected_unstable_version(array, i, pos);	//非稳定版本		//move_selected_stable_version(array, i, pos);	//稳定版本	}}