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数组考回arrfor (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. 数据敏感性：不敏感---即使是数据已经有序，也要进行排列（可以称这种排列为伪排列）。