前言
继插入排序后，今天小编就给大家另一个模块，选择排序的学习，那么话不多说，我们直接进入正题。
选择排序
1.直接选择排序
1.1基本思想
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
这里我们以升序为例给大家看看其运作过程：
在实现直接插入排序过程中，我们需要使用到交换内容的函数
void swap(int* p, int* q) { int temp = * p; * p = * q; * q = temp; }
这里大家直接看代码：
void Selectsort(int* arr, int n) { int left = 0; int right = n - 1; while (left < right) { int minxi = left; int maxxi = left; for (int i = left+1; i < right+1; i++) { if (arr[i] < arr[minxi]) { minxi = i; } if (arr[i] > arr[maxxi]) { maxxi = i; } } swap(&arr[left],&arr[minxi]); if (left == maxxi) { maxxi = minxi; } swap(&arr[right],&arr[maxxi]); left++; right--; } }
这里我们是选出两个值，一个最小值，一个最大值，这里我们把最小值，放在序列前面，最大值放在序列后面，这里我给大家细细讲解一下：
对于这个判断条件，是这里有一个特殊情况需要我们处理
这里我给大家举例说明：
1.2 直接选择排序的特性
1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
说明：对于直接排序的时间复杂度，最坏的情况下和最后的情况的时间复杂度都是一致的都是O(N^2)，由于直接选择排序我们无论在什么情况每次都是选择最大值，最小值，知道所有元素排序完毕，但是在这个过程中我们并不能判断它是否已经有序，所以该最好已经最坏情况下都是O(N^2)。
3. 空间复杂度：O(1)
4. 稳定性：不稳定
2.堆排序
2.1基本思想
堆排序 (Heapsort) 是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是 通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
对于堆的介绍，以及下面小编要用到的向下调整思想，小编已经写了一篇文章有关于堆这个结构的完整介绍（堆介绍).
那么为什么我们排升序的时候要用大堆，降序用小堆呢？对于堆这个结构我们每次能得到的就是一个数组中的最大值，最小值，那么对于升序，我们就可以每次选出最大值，然后我们只需要让最大值和最后一个值进行内容交换，然后在下一次的过程中，我们就不让这个最大值参与堆的这个结构中，然后再选出来的值，就是我们的第二大值，重复操作后就能实现我们的需要的排序功能。
具体过程如下：
那么转换成代码如下：
void AdjustDown(int* a, int n, int parent) { int child = parent * 2 + 1; while (child < n) { // 选出左右孩子中大的那一个 if (child + 1 < n && a[child + 1] > a[child]) { ++child; } if (a[child] > a[parent]) { swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } //升序排序 void HeapSort(int* a, int n) { //向下建堆 for (int i = n / 2 - 1; i >= 0; i--) { AdjustDwon(a, n, i); } //堆排序 for (int i = n-1; i>0;i-- ) { swap(&a[0], &a[i]); AdjustDwon(a, i, 0); } }
首先我们要先保证我们的数组成为一个堆的结构，那么我们就需要让其向下建堆（或者向上建堆，但是向下建堆的时间复杂度小于向上建堆的，所以我们这里使用更优的向下建堆，两者的区别我会在之后给大家详细介绍）。
这里向下建堆的过程是：
对于向下建堆我们首先就是从下往上建堆，保证下面是堆的结构后，再不断地往上建堆，所以我们就要从最后一个孩子的父节点开始往上建堆（叶子节点已经符合了堆这个结构），所以我们起始值就是i=n/2-1.
对于堆排序，相信大家已经明白了一个大概，我们只需要控制我们选出来的最大值，不再次参与建堆这个过程即可。
3.测试
这里我们对我们排序功能进行测试：
堆排序：
int main() { int arr[10] = { 1,23,44,55,67,56,87,76,88,98 }; int len = sizeof(arr) / sizeof(int); for (int i = 0; i < len; i++) { printf("%d ", arr[i]); } return 0; }
直接选择排序：
int main() { int arr[10] = { 1,23,44,55,67,56,87,76,88,98 }; int len = sizeof(arr) / sizeof(int); Selectsort(arr, len); for (int i = 0; i < len; i++) { printf("%d ", arr[i]); } return 0; }
