選擇排序

非穩定版本與穩定版本

排序過程中選擇一個比較大（大到小排序）的數，然後把它放到數組中指定的位置；這時候可以直接與數組中指定位置交換數據，但是可能會導致同值的數據的順序發生改變，這就是所謂的“不穩定”。可以通過下圖來理解所謂的“穩定”和“非穩定”。

• 不穩定排序演算法按數字排序時，會打亂原本同值的花色順序
  [[♠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);	//穩定版本
	}
}