排序过程中选择一个比较大(大到小排序)的数,然后把它放到数组中指定的位置;这时候可以直接与数组中指定位置交换数据,但是可能会导致同值的数据的顺序发生改变,这就是所谓的“不稳定”。可以通过下图来理解所谓的“稳定”和“非稳定”。
//非稳定版本 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); //稳定版本 } }