29 选择排序.md

#数据结构 #算法 #C

[87] 简单选择排序

选择排序（Selection sort），是一种简单直观的排序算法。它的工作原理如下：

• 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
• 然后，再从剩余未排序元素中继续寻找最小（大）元素，
• 然后放到已排序序列的末尾。
• 以此类推，直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多(n-1)次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

其中，选择排序又分为简单选择排序和堆排序。不作特殊说明，以下称简单选择排序为选择排序。

1. 算法思想

每⼀趟在待排序元素中选取关键字最小的元素加⼊有序子序列。

2. 算法过程

n个记录的直接选择排序可经过(n-1)趟直接选择排序得到有序结果。 具体算法描述如下：

• 初始状态：无序区为 $R[1…n]$ ，有序区为空；
• 第 $i$ 趟排序: $(i=1,2,3…n-1)$ 开始时，当前有序区和无序区分别为 $R[1…i-1]$ 和 $R(i…n)$。
• 该趟排序，从当前无序区中选出关键字最小的记录 $R[k]$ ，将它与无序区的第1个记录 $R$ 交换，使 $R[1…i]$ 和 $R[i+1…n]$ 分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
• $n-1$ 趟结束，数组有序化了。

以数组A{49,38,65,97,76,13,27,49}为例，对n个元素的简单选择排序需要 n-1 趟处理。

3. 算法实现

void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp; 
}

void SelectSort(int array[], int n)
{
    // 一共进行 n-1 趟, i 指代待排序的元素开头位置
    for (int i = 0; i < n - 1; i++){
        // 记录最小元素位置
        int min = i;
        // 在 array[i, n-1]中找最小的元素
        for (int j = i + 1; j < n; j++){
            // 更新最小的元素
            if (array[j] < array[min]){
                min = j;
            }
        }

        if (min != i){
            swap(array[i], array[min]);
        }
    }
}

4. 算法性能

⽆论有序、逆序、还是乱序，⼀定需要 n-1 趟处理，总共需要对比关键字次数目：
$$(n-1) + (n-2)+ … + 1 = \frac{n(n-1)}{2}$$

元素交换次数 < $n-1$

• 时间复杂度 = $O(N^2)$
• 空间复杂度 = $O(1)$

选择排序是不稳定的排序。