直接選擇排序

直接選擇排序(Straight Select Sorting) 也是一種簡單的排序方法，它的基本思想是：第一次從R[0]~R[n-1]中選取最小值，與R[0]交換，第二次從R[1]~R[n-1]中選取最小值，與R[1]交換，....，第i次從R[i-1]~R[n-1]中選取最小值，與R[i-1]交換，.....，第n-1次從R[n-2]~R[n-1]中選取最小值，與R[n-2]交換，總共通過n-1次，得到一個按排序碼從小到大排列的有序序列。

基本思想

例如:給定n=8，數組R中的8個元素的排序碼為(8,3,2,1,7,4,6,5),則直接選擇排序的過程如下所示

由於百科不方便畫出關聯箭頭 所以用 n -- n 表示 ：

初始狀態 [ 8 3 2 1 7 4 6 5 ] 8 -- 1

第一次 [ 1 3 2 8 7 4 6 5 ] 3 -- 2

第二次 [ 1 2 3 8 7 4 6 5 ] 3 -- 3

第三次 [ 1 2 3 8 7 4 6 5 ] 8 -- 4

第四次 [ 1 2 3 4 7 8 6 5 ] 7 -- 5

第五次 [ 1 2 3 4 5 8 6 7 ] 8 -- 6

第六次 [ 1 2 3 4 5 6 8 7 ] 8 -- 7

第七次 [ 1 2 3 4 5 6 7 8 ] 排序完成

排序算法

C++ 實現：

C#實現：

實現

python3實現：

效率分析

在直接選擇排序中，共需要進行n-1次選擇和交換，每次選擇需要進行 n-i 次比較 (1<=i<=n-1),而每次交換最多需要3次移動，因此，總的比較次數C=(n*n - n)/2,

總的移動次數 3(n-1).由此可知，直接選擇排序的時間複雜度為 O(n ) ，所以當記錄占用位元組數較多時，通常比直接插入排序的執行速度快些。

由於在直接選擇排序中存在著不相鄰元素之間的互換，因此，直接選擇排序是一種不穩定的排序方法。