這幾乎是最簡單的排序方法...

核心思想

選擇排序的思想其實和冒泡排序有點類似，都是在一次排序后把最小的元素放到最前面，或者將最大值放在最后面。但是過程不同，冒泡排序是通過相鄰的比較和交換。而選擇排序是通過對整體的選擇，每一趟從前往后查找出無序區(qū)最小值，將最小值交換至無序區(qū)最前面的位置。

示例

第一輪過程: 初始化一個minIndex=0，i=0~9，依次將arr[i]與arr[minIndex]進行對比，如果arr[minIndex]的值較小則無操作，如果arr[i]的值較小，則將minIndex=i,意思是目前最小值的位置下標為i，直至這輪結(jié)束，minIndex的值則是該組數(shù)據(jù)無序區(qū)最小值的下標，將最小值交換到無序區(qū)最前面的位置，此時n=0的位置有序。

選擇排序-第一輪

第二輪過程 ：i=1~9 查找最小值，對比方式與第一輪一樣，找出最小值下標，將最小值交換至n=1的位置，第三輪i=2~9,最小值交換至n=2的位置。

整個循環(huán)過程：
<pre>
原始長度10
100 5 3 11 33 6 8 7 1 3
第1輪
1 5 3 11 33 6 8 7 100 3
第2輪
1 3 5 11 33 6 8 7 100 3
第3輪
1 3 3 11 33 6 8 7 100 5
第4輪
1 3 3 5 33 6 8 7 100 11
第5輪
1 3 3 5 6 33 8 7 100 11
第6輪
1 3 3 5 6 7 8 33 100 11
第7輪
1 3 3 5 6 7 8 33 100 11
第8輪
1 3 3 5 6 7 8 11 100 33
第9輪
1 3 3 5 6 7 8 11 33 100
</pre>

時間復雜度

選擇排序同樣需要兩輪循環(huán)才能完成排序。所以時間復雜度為O ( n^2)。

C語言代碼

#pragma mark - 選擇排序
void pickSort(int arr[] ,int len) {
    printf("原始長度%d\n",len);
    printfArr(arr, len);
    for (int i = 0; i < len-1; i++) {
        printf("第%d輪\n",i+1);
        int minLocation = i;
        for (int j = i; j < len-1; j++) {
            int preNum = arr[minLocation];
            int nexNum = arr[j+1];
            
            if (preNum>nexNum) {
                minLocation = j+1;
            }
        }
        if (minLocation != i) {
            int temp = arr[i];
            arr[i] = arr[minLocation];
            arr[minLocation] = temp;
        }
        printfArr(arr, len);
    }
}

結(jié)語

這個比冒泡簡單，你覺得呢？