本文共 1929 字，大约阅读时间需要 6 分钟。

上一篇博客我们学习了插入排序之直接插入排序和希尔排序，。

这篇文章我们来学习选择排序。 常见的选择排序有直接选择排序和堆排序。选择排序的基本思想就是从每一趟（比如第i趟）从其之后的n-i个待排序数据中找到关键码最小的数据，作为有序数据的第i个元素。当n-2趟排完之后，只剩下一个待排序数据，就不用进行选择了。

1.直接选择排序

基本思想：比较+交换

1）首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置 2）再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。 3）重复第二步，直到所有元素均排序完毕。

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

空间复杂度：O(1)

动图展示如上。下面给出一个示例。原数组是{5，7，6，8，4，2，9，3，0，1}，第一次选择排序后{0，7，6，8，4，2，1，3，5，9}，先在数组中找到最大和最小的，然后进行交换，left和right向中间移动。 因为在交换的时候可能让两个相等的数发生位置变化，所以选择排序是不稳定的。

void  SelectSort(int a[],size_t n){    int left = 0;    int right = n - 1;    while (left < right)    {        int MinIndex = left;        int MaxIndex = right;        for (int i = left; i <= right; i++)        {            if (a[i] < a[left])                MinIndex = i;            if (a[i]>a[right])                MaxIndex = i;        }        swap(a[left], a[MinIndex]);        if (MaxIndex == left)            MaxIndex = MinIndex;        swap(a[MaxIndex], a[right]);        ++left;        --right;    }}

2.堆排序

我们常说的堆排序也是选择排序的一种，它是一种树形的排序方式，是对简单选择排序的一种改进。

基本思想：本质是一种数组对象。特别重要的一点性质：任意的叶子节点小于（或大于）它所有的父节点。对此，又分为大顶堆和小顶堆，大顶堆要求节点的元素都要大于其孩子，小顶堆要求节点元素都小于其左右孩子，两者对左右孩子的大小关系不做任何要求。

即对一个数组进行堆化，找出最大的数（默认升序），和尾部的数进行交换，重建堆……

重点：必须清楚是大堆还是小堆，数组堆化的时候从哪一个结点开始，重新调整堆时是从堆头开始调整。

时间复杂度： 每次调整堆都是log(N),N个数就是N*log(N)

我们可以知道，在堆排序时，每次将最后一个数与第一个数进行交换，所以堆排序是不稳定的。

void AdjustDown(int a[],int n,int root){    int child = 2 * root + 1;    while (child < n)    {        if (child + 1 < n && a[child] < a[child + 1])            ++child;        if (a[child]>a[root])        {            swap(a[child],a[root]);            root = child;            child = 2 * root + 1;        }        else              break;    }}void HeapSort(int a[],size_t n){    //调整成一个堆    for (int i = (n - 2) / 2; i >= 0; i--)    {        AdjustDown(a, n,i);    }    int end = n - 1;    while (end > 0)    {        swap(a[end], a[0]);        AdjustDown(a, end, 0);        end--;    }}

选择排序的基本思想都是一样的，先找到符合要求的数，再进行交换，直至完成整个数组排序，因此，选择排序都是不稳定的。