选择排序

非稳定版本与稳定版本

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

• 不稳定排序算法按数字排序时，会打乱原本同值的花色顺序
  [[♠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);	//稳定版本 	} }