选择排序详解——直接选择排序+堆排序

选择排序

3.1 直接选择排序

我们先来看第一种选择排序，直接选择排序：

算法思想

先从待排序的数据元素中选出最大（或最小）的一个元素，存放在序列的起始位置，再选出次大的放到第二个位置，依次循环往复，直到全部待排序的数据元素排完 。

动图演示：

直接插入排序的思想呢非常简单，但是它的效率比较低，每遍历一次才选出一个数。

所以：

我们接下来实现一个优化一点的版本 怎么优化呢？ 我们遍历一遍其实可以选出两个数，最大的最小的我们都可以选出来，第一次选出最小的和最大的放到首尾两个位置（假设用begin和end标识，第二次选出次大的和次小的再放到倒数第二和正数第二的位置（begin++，end- -）......，就这样循环往复，直到所有数据排完。

代码实现

//直接选择排序
void SelectSort(int* arr, int n)
{
    assert(arr);
    int begin = 0;
    int end = n - 1;
    while (begin < end)
    {
        int maxi = begin;
        int mini = begin;
        for (int i = begin+1; i <= end; i++)
        {
            if (arr[i] > arr[maxi])
            {
                maxi = i;
            }
            if (arr[i] < arr[mini])
            {
                mini = i;
            }
        }
        swap(&arr[mini], &arr[begin]);
        swap(&arr[maxi], &arr[end]);
        begin++;
        end--;
    }
}

🆗，我们来测试一下： 确实排好了。

我们换一组数据再测试一下：

欸，这一次怎么不对了啊。

为什么会这样？ 🆗，其实我们刚才实现的还有一些bug，什么bug呢？ 每一次循环我们找到最大的和最小的之后，我们首先把最小值交换到了下标begin的位置，那有一种可能： 就是maxi和begin是同一个位置，这样的话交换之后，maxi的位置就变了，所以我们要加一个判断，如果maxi等于begin，那么交换之后最大值就跑到mini位置了，那就要为maxi重新赋值了。

所以正确的代码应该是这样的：

//直接选择排序
void SelectSort(int* arr, int n)
{
    assert(arr);
    int begin = 0;
    int end = n - 1;
    while (begin < end)
    {
        int maxi = begin;
        int mini = begin;
        for (int i = begin+1; i <= end; i++)
        {
            if (arr[i] > arr[maxi])
            {
                maxi = i;
            }
            if (arr[i] < arr[mini])
            {
                mini = i;
            }
        }
        swap(&arr[mini], &arr[begin]);
        if (maxi == begin)
            maxi = mini;
        swap(&arr[maxi], &arr[end]);
        begin++;
        end--;
    }
}

这下我们再来测试： 这下就对了。

直接选择排序特性总结

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用

2. 时间复杂度：O(N^2)

3. 空间复杂度：O(1) 

4. 稳定性：不稳定 这个排序我们自己理解的话很容易认为它是稳定的，但其实它是不稳定的，举个反例： 比如待排数据是这样的：8 9 8 5 5 假如是升序，选最小的数，选到一个5之后我们可以控制后面有相等的数我们不更新这个最小值，但是最小值交换到第一个位置，两个8的相对位置就变化了。 所以不稳定。

3.2 堆排序

堆排序呢，我们在之前二叉树的文章里已经进行了详细的讲解： 堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。 那在这里就不过多赘述了，大家有需要的话可以看我之前那篇讲解二叉树的文章——link

这里再简单总结一下堆排序：

1. 堆排序使用堆来选数，效率就高了很多。

2. 时间复杂度：O(N*log2N)

3. 空间复杂度：O(1)

4. 稳定性：不稳定 举个例子吧。 比如这样一组数据：1 1 1 1 1 建好堆之后最后一个元素和堆顶一交换，是不是就不行了。 当然有些数据可能在向下调整建堆的过程中就不稳定了。