1.前言
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
本章重点：
堆排序和选择排序和归并排序
2.选择排序
基本思路
left和right记录区间的左端和右端；
不断遍历数组，经过一次遍历选出区间中的最大值和最小值；
然后将最小值换到左端，最大值换到右端；
++left; --right; 当left < right时循环继续。
注意：交换元素时如果先后交换的下标恰好相同需要做出调整。
代码如下：
void SelectSrot(int *arr, int n){
assert(arr != NULL);
int begin = 0;
int end = n-1;
//begin,end向中间靠拢
while (begin < end)
{
int maxi = begin;
int mini = begin;
//一次循环找出一个最大值和一个最小值分别放到begin和end位置
for (int i = begin; i <= end; i++)
{
if (arr[i] < arr[mini])
{
mini = i;
}
if (arr[i] > arr[maxi])
{
maxi = i;
}
}
//因为先将maxi和end交换，所以当后换的mini==end 时原来end的值已经被换走了，转换一下
if (maxi == begin)
{
maxi = mini;
}
Swap(&arr[begin], &arr[mini]);
Swap(&arr[end], &arr[maxi]);
begin++;
end--;
}
}
- 直接选择排序的特性总结：
- 选择排序思路简单好理解，但是对有序序列无反应，复杂度恒为O(N^2)。效率低，实际中很少使用。
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：不稳定(有可能两个相等元素的相对顺序会发生变化)
- 数据敏感性：不敏感，不管有序无序都要进行多轮次的选择
2.堆排序
在写堆排序之前先写一个节点向上调整和节点向下调整
AdJustDown:
//向下调整，小的在上，大的在下
void AdjustDown(int *arr, int sz, int root)//父亲节点的下标
{
assert(arr!=nullptr);
int parent=root;
int child=2*parent+1;//左节点
while(child<sz)
{
//先判断谁小---找小
if(child+1<sz&&arr[child]<arr[child+1])
child++;
if(arr[child]<arr[parent])
{
swap(&arr[child],&arr[parent]);
parent=child;
child=2*parent+1;
}
else break;
}
}AdJustUp:向上调整
//向上调整---大的在顶部
void AdJustUp(int *arr,int sz,int root)//这里传来的是孩子节点
{
assert(arr!=nullptr);
int child=root;
int parent=(child-1)/2;
while(child<sz)
{
if(arr[child]<arr[parent])
{
swap(&arr[child],&arr[parent]);
child=parent;
parent=(child-1)/2;
}
else break;
}
}构建一个堆，一般来说都是从第一个非叶子节点开始构建堆。
void HeapSort(int* arr,int sz)
{
assert(arr!=nullptr);
for(int i=(sz-1-1)/2;i>=0;i--)
{
AdJustDown(arr,sz,i);
}
//大堆建立完了之后。开始排序
for(int end=sz-1;end>=0;end--)
{
swap(&arr[end],&arr[0]);//最大值调整到了最后一个，最小值调整到了第一个
AdJustDown(arr,sz,0);//再把最小值进行调整
}
}思路总结：
1.首先写一个向上调整或者向下调整函数
2.调整堆：如果是需要升序的话---那么就是大堆---大堆就是说大的在上
如果是需要降序的话--那么就是小堆---小堆就是说小的在上
3.利用堆删除的思想来进行排序
记录堆尾下标end；
交换堆顶(0)堆尾(end)元素——将最大值交换到序列尾。
向下调整，但此时的调整范围到end——恢复堆结构选出最大值
–end——进行下一轮选择交换。
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
堆排序的特性总结：
堆排序使用堆来选数，效率就高了很多。- 时间复杂度：O(N*logN)
- 空间复杂度：O(1)
- 稳定性：不稳定，由于使用了堆结构，无法保证稳定性数据
- 敏感性：不敏感，不管有序无序都要重新建堆排序
3.归并排序
归并排序就是找到一个基准值，大的在基准值的右，小的在基准值的左边。
然后开始递归-------当只有一个元素时就不需要了，然后返回上一层，再次进行排序即可。
具体步骤如下：
正式排序前需要创建与待排数组相同大小的数组tmp。
首先计算出中间位置的下标，将序列一分为二。
如果子区间元素个数大于1则向下递归先使左右子区间有序
然后将左右子区间归并到tmp数组
最后将数据考回原数组。
代码如下：
void _MergeSort(int *arr, int left, int right, int *tmp)
{
//注意递归的结束条件
if (left >= right)
{
return;
}
//计算出中间位置的下标
int mid = left + (right - left) / 2;
//划分左右区间
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
//先使左右两区间有序
_MergeSort(arr, begin1, end1, tmp);
_MergeSort(arr, begin2, end2, tmp);
//将左右两区间归并到tmp数组
//注意排序的区间不从0开始
int i = left;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
{
tmp[i++] = arr[begin1++];
}
else
{
tmp[i++] = arr[begin2++];
}
}
while (begin1 <= end1)
{
tmp[i++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = arr[begin2++];
}
//将排好的数据从tmp数组考回arr
for (int j = left; j <= right; j++)//注意这里一定是从left-right而不是从0-sz-1
//因为当递归进去之后，就不一定是0-sz-1了。也有可能是只有两个数：例 下标2-3
{
arr[j] = tmp[j];
}
}
void MergeSort(int *arr, int sz){
//递归排序过程中需使用额外空间
int *tmp = (int*)malloc(sizeof(int) * sz);
if (tmp == NULL)
{
perror("MergeSort");
exit(1);
}
_MergeSort(arr, 0, sz - 1, tmp);
//排序结束后记得释放额外空间
free(tmp);
tmp = NULL;
}
将数组一分为二，先使数组的左右区间有序，再将左右区间归并成一个有序数组。对比快速排序，归并排序与二叉树的后序遍历思想更为相似。
归并排序解决磁盘问题：
归并排序的特点：
1. 归并排序兼具高效、稳定、数据不敏感的特点；缺点在于需要O(N)的空间。常用于外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定
5. 数据敏感性：不敏感---即使是数据已经有序，也要进行排列（可以称这种排列为伪排列）。