算法-选择排序

这几乎是最简单的排序方法...

核心思想

选择排序的思想其实和冒泡排序有点类似，都是在一次排序后把最小的元素放到最前面，或者将最大值放在最后面。但是过程不同，冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择，每一趟从前往后查找出无序区最小值，将最小值交换至无序区最前面的位置。

示例

第一轮过程: 初始化一个minIndex=0，i=0~9，依次将arr[i]与arr[minIndex]进行对比，如果arr[minIndex]的值较小则无操作，如果arr[i]的值较小，则将minIndex=i,意思是目前最小值的位置下标为i，直至这轮结束，minIndex的值则是该组数据无序区最小值的下标，将最小值交换到无序区最前面的位置，此时n=0的位置有序。

选择排序-第一轮

第二轮过程 ：i=1~9 查找最小值，对比方式与第一轮一样，找出最小值下标，将最小值交换至n=1的位置，第三轮i=2~9,最小值交换至n=2的位置。

整个循环过程：
<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>

时间复杂度

选择排序同样需要两轮循环才能完成排序。所以时间复杂度为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);
    }
}

结语

这个比冒泡简单，你觉得呢？