排序算法（二）选择排序

算法原理

选择排序的原理是，在每一轮中，从未排序的部分挑选出最小（最大）的数放到正确的位置。例如在一个长度为 N 的数组中，第一趟选择出最小的数放在数组的最前面，然后第二趟从未排序的部分中选择从最小的数放在已排序的部分的末端，然后以此循环下去直到将每个数都放到了对应的位置就完成了排序。示意图如下：

代码实现

int* SelectSort(int* arr, int length){
    int i = 0, j = 0;
    int min = 0;
    for(i = 0; i < length; i++){
        min = i;
        for(j = i; j < length; j++){
            min = (arr[j] > arr[min]) ? min : j;
        }   //取得最小元素的下标
        swap(arr[min], arr[i]); //将取得的最小元素放在正确位置
    }
    return arr;  //此时的arr已经是一个升序数组了
}

分析

首先，选择排序并不是一个稳定的算法。在碰到1、5、1这种大小数夹杂的情况，在遍历的过程中显然会选择后遍历到的1的下标，而两个1的顺序就会因此改变。
选择排序的效率也比较低，平均时间复杂度为$O(n2)$,空间复杂度为$O(1)$。

优化思路

选择算法的优化思路是，在每一次循环中，在找出最小值的同时，也找出最大值。也就是说一次循环确定了两个数的位置。那么时间复杂度就成了之前的一半，但仍然是个$O(n)$的算法

• 本文作者： Kylin
• 本文链接： https://kylinnnnn.github.io/2022/01/28/排序算法（二）选择排序/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！