排序（2）之选择排序
目录
前言
选择排序
1.直接选择排序
1.1基本思想
编辑
1.2 直接选择排序的特性
2.堆排序
3.测试
前言
继插入排序后，今天小编就给大家另一个模块，选择排序的学习，那么话不多说，我们直接进入正题。
选择排序
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;
}
