排序算法的稳定性：在具有多个相同关键字的记录中，若经过排序这些记录的次序保持不变，说排序算法是稳定的。
插入排序O($n^2$)
直接插入排序
动画演示如图：
代码如下：
void Straight_Insertion_Sort(int a[],int length){ for (int i = 1;i < length;i++) { if (a[i]<a[i-1]) { int temp = a[i]; for (int j = i - 1;j >= 0;j--) { a[j + 1] = a[j]; if (a[j] < temp) { a[j + 1] = temp; break; } if (j == 0 && a[j] > temp) { a[j] = temp; } } } } }折半插入排序
主要分为查找和插入两个部分
图片演示：
代码如下：
void Binary_Insert_Sort(int a[],int length) { int low, high, mid; int i, j,temp; for ( i = 1;i < length;i++) { low = 0; high = i - 1; temp = a[i]; while (low<=high) { mid = (low + high) / 2; if (temp<a[mid]) { high = mid - 1; } else { low = mid + 1; } }//while for ( j = i - 1;j > high;j--) { a[j + 1] = a[j]; } a[j + 1] = temp; }//for(i)
冒泡排序O($n^2$)
思路：两两比较元素，顺序不同就交换
图解：
代码：
void Bubble_Sort(int a[],int length) {
for (int i = 0;i < length - 1;i++) {
for (int j = 0;j <length-i-1 ;j++) {
if (a[j]>a[j+1]) {
int temp = a[j];
a[j] = a[j +1];
a[j+1] = temp;
}
}
}
}选择排序O($n^2$)
思路：每一次从待排序的数据元素中选择最小（最大）的一个元素作为有序的元素。如果是升序排序，则每次选择最小值就行，这样已经排好序的部分都是生序排序选择排序是不稳定的，比如说（55231这种情况，两个5的相对顺序会变）
图解：
代码：
void Select_Sort(int a[],int length) {
for (int i = 0;i < length - 1;i++) {
int min_index = i;
for (int j = i+1;j < length;j++) {
if (a[min_index]>a[j]) {
min_index = j;
}
}//for j
if (i!=min_index) {
int temp = a[i];
a[i] = a[min_index];
a[min_index] = temp;
}
}//for i
}希尔排序——缩小增量排序O(nlogn)
思路：
希尔排序又叫缩小增量排序，使得待排序列从局部有序随着增量的缩小编程全局有序。当增量为1的时候就是插入排序，增量的选择最好是531这样间隔着的。
其实这个跟选择排序一样的道理，都是不稳定的比如下图7变成9的话，就是不稳定的
图解：
代码：
void Shell_Sort1(int a[], int length) {
//首先定义一个初始增量，一般就是数组长度除以2或者3
int gap = length / 2;
while (gap >= 1) {
for (int i = gap;i < length;i++) {
int temp = a[i];
int j = i;
while (j >= gap&&temp<a[j - gap]) {
a[j] = a[j - gap];
j = j - gap;
}//while
a[j] = temp;
}//for
gap=gap/2;
}//while
}
/*****************另一种写法， 好理解****************************/
void shellsort3(int a[], int n)
{
int i, j, gap;
for (gap = n / 2; gap > 0; gap /= 2)
for (i = gap; i < n; i++)
/*j>gap之后，j前面的可以重新比较依次保证j前面间隔gap的也是有序的*/
for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap)
Swap(a[j], a[j + gap]);
}快速排序O(nlogn)
思路：快排的核心叫做“基准值“，小于基准值的放在左边，大于基准值的放在右边。然后依次递归。基准值的选取随机的，一般选择数组的第一个或者数组的最后一个，然后有两个指针left和right
void QuickSort(int* a, int left, int right)
{
// 假设按照升序对array数组中[left, right)区间中的元素进行排序
if (right <= left)
return;
// 按照基准值对array数组的 [left, right)区间中的元素进行划分
//int keyi = PartSort1(a, left, right);
//int keyi = PartSort2(a, left, right);
int keyi = PartSort(a, left, right);
// 划分成功后以div为边界形成了左右两部分 [left, keyi-1) 和 [keyi+1, right)
// 递归排[left, keyi-1)
QuickSort(a, left, keyi - 1);
// 递归排[keyi+1, right)
QuickSort(a, keyi + 1, right);
}Hoare版本快排
- 首先，定义一个变量key，用于保存基准值的下标，初始值为left。
- 进入一个循环，循环条件是left < right，即左右指针没有相遇。
- 在循环中，首先从右边开始，找到第一个小于等于基准值的元素的下标，将right指针左移，直到找到符合条件的元素或者left和right相遇。
- 然后从左边开始，找到第一个大于基准值的元素的下标，将left指针右移，直到找到符合条件的元素或者left和right相遇。
- 如果left < right，说明找到了需要交换的元素，将a[left]和a[right]交换位置。
- 重复步骤3到步骤5，直到left和right相遇。
- 最后，将基准值a[key]和a[left]交换位置，将基准值放在正确的位置上。
- 返回分割点的下标left。
int PartSort(int* a, int left, int right)
{
//三数取中(优化)
//int keyi = NumBers(a, left, right);
//Swap(&a[keyi], &a[left]);
int key = left;
while (left < right)
{
while (left < right && a[left] <= a[right])
{
right--;
}
while (left < right && a[left] <= a[right])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[key]);
return left;
}挖坑法
- 定义一个变量key，用于保存基准值，初始值为a[left]。
- 定义一个变量hole，用于保存空洞的位置，初始值为left。
- 进入一个循环，循环条件是left < right，即左右指针没有相遇。
- 在循环中，首先从右边开始，找到第一个小于基准值的元素的下标，将right指针左移，直到找到符合条件的元素或者left和right相遇。
- 将a[right]的值赋给a[hole]，将空洞的位置移动到right。
- 然后从左边开始，找到第一个大于基准值的元素的下标，将left指针右移，直到找到符合条件的元素或者left和right相遇。
- 将a[left]的值赋给a[hole]，将空洞的位置移动到left。
- 重复步骤4到步骤7，直到left和right相遇。
- 最后，将基准值key放入空洞的位置a[hole]，将基准值放在正确的位置上。
- 返回空洞的位置hole。
int PartSort(int* a, int left, int right)
{
//三数取中优化
//int keyi = NumBers(a, left, right);
//Swap(&a[keyi], &a[left]);
int key = a[left];
int hole = left;//为第一个坑
while (left < right)
{
while (left < right && key <= a[right])
{
--right;
}
a[hole] = a[right];
hole = right;
while (left < right && a[left] <= key)
{
++left;
}
a[hole] = a[left];
hole = left;
}
a[hole] = key;
return hole;
}堆排序O(nlogn)
思路：堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。堆排序分为两步：首先将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。随后第二步将其与末尾元素进行交换，此时末尾就为最大值。然后将这个堆结构映射到数组中后，就会变成升序状态了。（即升序—大根堆）
当数组元素映射成为堆时：
- 父结点索引：(i-1)/2
- +左孩子索引：2*i+1
- 左孩子索引：2*i+2
图解：
基本思想：
- 首先将待排序的数组构造成一个大根堆，此时，整个数组的最大值就是堆结构的顶端
- 将顶端的数与末尾的数交换，此时，末尾的数为最大值，剩余待排序数组个数为n-1
- 将剩余的n-1个数再构造成大根堆，再将顶端数与n-1位置的数交换，如此反复执行，便能得到有序数组
代码：
//index是第一个非叶子节点的下标（根节点）
//递归的方式构建
void Build_Heap(int a[],int length,int index){
int left = 2 * index + 1; //index的左子节点
int right = 2 * index + 2;//index的右子节点
int maxNode = index; //默认当前节点是最大值，当前节点index
if (left<length&&a[left]>a[maxNode]) {
maxNode = left;
}
if (right<length&&a[right]>a[maxNode]) {
maxNode = right;
}
if (maxNode!=index) {
int temp = a[maxNode];
a[maxNode] = a[index];
a[index] = temp;
Build_Heap(a,length,maxNode);
}
}
void Heap_Sort(int a[],int length) {
// 构建大根堆（从最后一个非叶子节点向上）
//注意，最后一个非叶子节点为(length / 2) - 1
for (int i = (length / 2) - 1;i >= 0;i--) {
Build_Heap(a, length, i);
}
for (int i = length - 1;i >= 1;i--) {
//交换刚建好的大顶堆的堆顶和堆末尾节点的元素值，
int temp = a[i];
a[i] = a[0];
a[0] = temp;
//交换过得值不变，剩下的重新排序成大顶堆
Build_Heap(a,i,0);
}
}归并排序(nlogn)
思路：分治思想，将若干个已经排好序的子序合成有序的序列。
图解：
代码：
//分治思想，先逐步分解成最小(递归)再合并
//归并
void Merge(int a[],int low,int mid,int high) {
int i = low;
int j = mid + 1;
int k = 0;
int *temp = new int[high - low + 1];
while (i<=mid&&j<=high) {
if (a[i]<=a[j]) {
temp[k++] = a[i++];
}
else {
temp[k++] = a[j++];
}
}//while (i<mid&&j<=high)
while (i<=mid) {
temp[k++] = a[i++];
}
while (j<=high) {
temp[k++] = a[j++];
}
for (i = low, k = 0;i <= high;i++, k++) {
a[i] = temp[k];
}
delete[] temp;
}
//递归分开
void Merge_Sort(int a[], int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
Merge_Sort(a, low, mid);
Merge_Sort(a, mid + 1, high);
cout << "mid=" << mid <<" " <<a[mid]<< endl;
cout << "low=" << low << " " << a[low] << endl;
cout << "high=" << high << " " << a[high] << endl;
cout << endl;
//递归之后再合并
Merge(a, low, mid, high);
}
}代码看不懂没关系，参考链接
计数排序O(n+k)
思路：
将待排序的数据存放到额外开辟的空间中。首先找出元素的最大最小值，然后统计每个元素i出现的次数，然后放入数组i中，数组中存放的是值为i的元素出现的个数。额外数组中第i个元素是待排序数组中值为i的元素的个数。因为要求输入的数有确定范围，同时只能对整数进行排序，有场景限制。
图解：
代码：
void Count_Sort(int a[],int length) {
//得到待排序的最大值
int max = a[0];
int i=0;
while ( i<length-1) {
max = (a[i] > a[i + 1]) ? a[i] : a[i + 1];
i++;
}
int *countArray = new int[max + 1]{0};
int *temp = new int[length];
for (int i = 0;i < length;i++) {
countArray[a[i]]++;
}
//!!!这一步的思想特别重要，在非比较排序中
for (int i = 1;i < max+1;i++) {
countArray[i] += countArray[i - 1];
}
//反向遍历
for (int i = length - 1;i >= 0;i--) {
temp[countArray[a[i]]-1] = a[i];
countArray[a[i]]--;
}
for (int i = 0;i < length;i++) {
a[i] = temp[i];
}
delete[] countArray;
delete[] temp;
}基数排序O(n*k)
思路：基数也就表明桶的个数是定死的，就是10个。基数排序的思想是，从个位依次开始排序，首先按照个位的大小排序，将改变的序列按照十位开始排序，然后一次往后……
图解：
代码：
int Get_Max_Digits(int a[],int length) {
int max = a[0];
int i = 0;
while (i<length-1) {
max = (a[i] > a[i + 1]) ? a[i] : a[i + 1];
i++;
}
int b = 0;//最大值的位数
while (max>0) {
max = max / 10;
b++;
}
return b;
}
//切记！桶子只能是十个，是定死的
void Radix_Sort(int b[],int length) {
int d = Get_Max_Digits(b, length);//得到最大值的位数
int * temp = new int[length];//开辟一个和原数组相同的临时数组
//根据最大值的位数进行排序次数循环
int radix = 1;
for (int i = 0;i < d;i++) {
//每次把数据装入桶子前先清空count
int count [10] = { 0 }; //计数器 每次循环都清零
for (int j = 0;j < length;j++) {
//统计尾数为0-9的个数，一次是个十百千....位
int tail_number = (b[j]/radix)%10;
count[tail_number]++;//每个桶子里面的个数
}
//桶中的每一个数的位置一次分配到temp数组中，先找到位置
for (int j = 1;j < 10;j++) {
count[j] += count[j - 1];
}
//分配到temp中排序后的位置
for (int j = length - 1;j >= 0;j--) {
int tail_number = (b[j] / radix) % 10;
temp[count[tail_number] - 1] = b[j];
count[tail_number]--;
}
//赋值
for (int j = 0;j < length;j++) {
b[j] = temp[j];
}
radix *= 10;
}//for(int i)
delete[] temp;
}桶排序O(n+k)
思路：基数排序和计数排序都是桶思想的应用。桶排序是最基本的
首先要得到整个待排序数组的最大值和最小值，然后设置桶的个数k，这样可以得到每个桶可以放的数的区间。
然后遍历待排序的数组，将相关区间内的数放到对应的桶中，这样桶内在排序，就使得整个序列相对有序
图解：
代码：
void bucketSort(int arr[], int len) {
// 确定最大值和最小值
int max = INT_MIN; int min = INT_MAX;
for (int i = 0; i < len; i++) {
if (arr[i] > max) max = arr[i];
if (arr[i] < min) min = arr[i];
}
// 生成桶数组
// 设置最小的值为索引0，每个桶间隔为1
int bucketLen = max - min + 1;
// 初始化桶
int bucket[bucketLen];
for (int i = 0; i < bucketLen; i++) bucket[i] = 0;
// 放入桶中
int index = 0;
for (int i = 0; i < len; i++) {
index = arr[i] - min;
bucket[index] += 1;
}
// 替换原序列
int start = 0;
for (int i = 0; i < bucketLen; i++) {
for (int j = start; j < start + bucket[i]; j++) {
arr[j] = min + i;
}
start += bucket[i];
}
}线性对数级排序算法详解（重要！）
快速排序
快排基本概念
快速排序用的是分治的思想，即通过选取一个pivot将数组分成两个子数组A和B，子数组A中的元素均小于等于pivot，子数组B中的元素均大于等于pivot中的元素。这个时候对于两个子数组A和B而言，每一个子数组又是一个数组需要选取一个pivot进行排序，这就是递归的思想。
因此对于快速排序来说主要由两部分组成：第一部分是获取pivot的
partition函数和进行快排递归的quicksort函数//这个函数主要是求pivot的 int partition(int *a, int left, int right){ //首先要随机选取一个pivot，这样做是为了根据pivot分成两个子数组数组。一下三种选择方式均可以 int pivot = a[left]; int pivot = a[right]; int pivot = a[left + (right - left) / 2];//这样做是为了防止数组越界 int pivot_index = left/right/left + (right - left) / 2 //两个指针移动，当同时指到一个元素时候就退出循环 //切记，必须从右边开始找！！！！ while(left < right){ while(a[right] >= pivot && left < right){ right--; } while(a[left] <= pivot && left < right){ left++; } if(left < right){ swap(a[left], a[right]); } } //这一步是为了将选取的pivot值放在中间，保证左边的子数组均比pivot小，右边的子数组均比pivot大 //这一步也是交换元素,交换选取pivot的索引和left的索引所对应的值 a[povit_index] = a[left]; a[left] = povit; return left; /*优化的写法：： int pivot = a[left]; while(left<right){ while(left<right&&a[right]<=pivot)right--; a[left] = a[right]; while(left<right&&a[left]>=pivot)left++; a[right] = a[left]; } a[left] = pivot; return left; */ } void quicksort(int *a, int left, int right){ //边界条件判断 if(left >= right){ return; } int pivot = partition(); quicksort(a, left, pivot - 1); quicksort(a, pivot +1, right); }总结：对上面代码，写的时候有几个地方需要注意：
- 在写内循环的时候，一定要先从右边开始写！！切记！！
- 当子数组中有小于pivot的时候和有大于pivot的时候，这个时候交换是正常的，将大小对调位置。但是，，我们最后退出大循环也要交换一次，这次交换是为了划分两个子数组，一个比pivot小，一个比pivot大。
性能分析
对于每一个数组，数值中的每一个元素都和一个定值进行比较，这样表明内循环很简洁。
时间复杂度
平均情况 最坏情况 最好情况 $O(nlog_2n)$ $O(n^2)$ $O(nlog_2n)$ 对于快速排序算法来说最理想的情况时partition函数能做到最平衡的划分，即每次选取的pivot值都能将数组对半分，这样划分到最后使得每个部分只包含一个或者零个元素。但是缺点也很明显，即在划分函数partition极度不平衡的时候效率会很低。比如说第一次选取的pivot是最小元素，第二次选取的pivot是第二小的元素等等，这样会导致一个大数组切分n-1次。
空间复杂度
平均情况 最坏情况 最好情况 $O(log_2n)$ $O(n)$ $O(log_2(n+1))$ 快速排序用到了递归，可以发现最好情况或者平均情况，将待排序数组每次对半分是最好的，这样的话就是logn，但是最坏的情况就是12345这种类型，基本上每次都要调栈，调大概n-1次。
稳定性
想一种情况，比如递增排序，右边有两个相同元素均小于pivot，这个时候调换到左边后相对位置会发生变化。所以是不稳定的。
改进算法
切换到插入排序
对于小数组来说，插入排序要比快速排序效率高，因为当数组比较小的时候还是会递归。所以当递归划分的子数组较小的时候可以使用插入排序来进行。或者直接用宏排序来写。
- 选取pivot的时候更优。一种选取方法是取前三个值的平均值，这样保证pivot比较均匀从统计学概率上来讲。或者选取中位数。
归并排序
归并排序基本概念
刚才讲了快速排序，这次讲解归并排序，主要思考他们两个思想有什么不同。
归并排序也是采用分治的思想实现的，分即将大问题分成一些小问题递归或者迭代求解，治则是指将分阶段得到的解决答案缝缝补补的合并在一起，这样就将大问题小问题话。
其实分治算法的思想用一张图就可以概括清楚：
可以看到分的过程是均分，这样的话分和治的过程都像是一个二叉树形状，那么求最底下一层即叶子节点，就是logn。
接下来主要分析治的阶段：
治的阶段本质上要解决的问题是将两个已经有序的子序列合并成一个有序序列
从上图中可以看到治的思想是对于两个子数组而言的，用两个指针的思想。看图就行了，不想细说了。
代码实现
代码分为两部分，merge和mergesort
void merge(vector<int>& vec, vector<int>& tmp1, vector<int>& tmp2){ int len1 = tmp1.size(); int len2 = tmp2.size(); int p1 = 0; int p2 = 0; while(p1 < len1 && p2 < len2){ if(tmp1[p1] <tmp2[p2]){ vec.push_back(tmp1[p1++]); }else{ vec.push_back(tmp2[p2++]); } } while(p1 <len1){ vec.push_back(tmp1[p1++]); } while(p2 < len2){ vec.push_back(tmp2[p2++]); } } void mergesort(vector<int>& vec){ if(vec.size() <= 1){ return; } auto mid = vec.begin() + vec.size()/2; vector<int> tmp1(vec.begin(), mid); vector<int> tmp2(mid, vec.end()); mergesort(tmp1); mergesort(tmp2); vec.clear(); merge(vec, tmp1, tmp2); }
性能分析
从上述算法示意图可以看出，在分的过程中类似于完全二叉树的，因此可以利用二叉树的特性的思想性能都不会太差。在分的时候算法的时间复杂度是lgN，而在治的时候由于需要指针一次比对，因此时间复杂度是O(N)，因此总体时间复杂度是O(NlgN)。
归并排序最吸引人的性质是他能够将任意长度为N的数组排序所需要的时间和NlgN成正比(注：任何基于比较的算法的时间复杂度都是lg(N!)到NlgN的)，但缺点也很明显，在治的过程中需要额外的空间和N成正比。
归并排序分为自顶向下和自底向上两种模式。上图中我们看到的是最容易理解的即自顶向下的方式。当然，自底向上形式的归并排序比较适合链表这种数据结构，因为将链表按照长度为1的子链进行排序的时候，然后按照长度为2的子链进行排序的时候，按照长度为4的子链进行排序的时候，这样做不用创建新的链表节点就能将链表进行排序。
归并排序是一种渐进最优的基于比较排序的算法。因为归并排序在最坏的情况下的比较次数和任意基于比较的排序算法所需的最少比较次数都是NlgN。
下列表格是快排和归并排序在时间复杂度上的比较：
稳定性
归并排序是稳定排序。
堆排序
堆排序的基本概念
首先要明确的是堆是一种树形结构，这种树形结构有两个重要特征：
- 堆是一个完全二叉树
- 堆中每一个节点的值都大于或等于其子树中每个节点的值
其实堆排序是由优先队列这个概念而来的，将优先队列变成一种排序方法也很简单，即将所有元素插入一个查找最小元素或最大元素的优先队列中，然后在重复调用删除最小元素或最大元素的操作将他们排序即可
堆排序可以分为两个阶段：
堆的构造阶段。不借助额外空间，将数组原地建成一个堆。
如果用指针来表示堆有序的二叉树，需要三个指针，两个子节点和他的父节点
如果用指针来表示堆有序的完全二叉树，则需要两个指针就行，因为根节点固定，其子节点也就固定了
但一般用数组表示也很方便，因为堆有序的完全二叉树在数组中时层级表示的：（第一个元素索引为0的时候）索引为k的节点，其父节点为
floor[(k-1)/2]，两个子节点的索引分别为2k+1和2k+2建堆的时候有两种思路：
- 第一种是一次插入一个元素然后组成一个堆。这里我们都用最大堆来表示。可以想一下，假如堆中有一个元素了，那么第二个元素就会在第一个元素的下面，从下往上依次排序，这就叫做从下往上堆化。这样的话不高效，需要从左往右把数组遍历一遍才行。（这种也是最基本的构建堆的方案吧，但是肯定不用，效率太低了）
第二种是这样的。对于一个n长度数组准备构建堆，我们从j=(n-1)/2的地方开始组建我们只需要扫描数组中一半的元素，因此第一半的那个索引正好对应两个根节点。这个链接说的很详细
比如下图i=4开始构建，正常的思路是i=0开始，但是这样我们得遍历整个数组，这是没必要的。因为堆是一种完全二叉树，所以我们只需要遍历一半就能知道所有的数组值，所以i=4是从i=n/2-1得来的
下沉排序阶段或上升排序阶段。从下往上的堆化叫做下沉又叫做sink()，而从下往上的堆化叫做上升又叫做swim()。
到这个阶段说明大顶堆或者小顶堆已经构建好了，可以排序了。我们把堆顶元素删除（这里模拟大顶堆），然后从数组的尾部补一个数，重新sink()排序就OK了。这样每次删除一个值就会从新排一次堆，知道按照从小到到的顺序让数组有序。
堆排序的分析
首先要知道几个命题：
创建堆的过程中N个元素至少需要2N次比较以及少于N次的交换。
将N个元素排序，堆排序只需要少于2NlgN+2N次比较。其中2N来自于N的构造。
时间复杂度
如果待排序中有N个数，遍历一趟的时间复杂度是O(N)。由于完全二叉树的提醒，遍历的次数就是树的深度，在lg(N+1)到lg(2N)之间，因此时间复杂度为O(NlgN)
稳定性
堆排序是不稳定算法。在交换数据的时候比较的是父节点和子节点之间的数据，如果存在两个值相等的兄弟节点，他们之间的顺序也可能在排序之后发生变化。
堆排序的一些额外的拓展
要知道，堆排序是唯一同时能够最优的利用时间和空间的排序方法，最坏的情况下也能保证线性对数的时间复杂性和恒定的空间
但是实际开发中，快排要比堆排序的性能好，有以下几点：
- 堆排序数据访问的方式没有快排合并排序那么友好。对于快排和合并排序来说我们的数据时顺序访问的，而对于堆排序来说我们是跳着访问的，无法实现局部顺序访问，因此无法利用缓存。
- 对于同样的数据，在堆排序过程中数据交换的次数要多于快排。对于基于比较的算法来说，排序的过程基本由两部分组成即比较和交换。堆排序第一步是建堆，因此可能会打乱数据原有的顺序造成数据有序度降低，进而增加很多比较次数。
但是，堆排序在空间利用十分紧张的地方比如嵌入式系统或者低成本的移动设备中很流行。
代码实现
代码有如下几部分：
heap_build建堆heap_sort堆排序，其中堆排序中调用建堆的API- 在堆排序函数中，每次要交换堆顶值和最后一个值，也就是数组的第一个和数组的最后一个，这样就可以升序排序
在构建堆的时候我们可以有递归和非递归的方式
void heap_bulid(vector<int>& vec, int root, int len) int left_child = root*2 + 1； int righ_child = root*2 + 2； int max_root = root; if(left_child < len && vec[left_child] > vec[max_root]){ max_root = left; } if(right_child < len && vec[right_child] > vec[max_root]){ max_root = right; } //如果最大值的节点不是原先的父节点，表示需要 if(max_root != root){ swap(vec[root], vec[max_root]); heap_bulid(vec, max_root, len); } } void heap_sort(vector<int>& vec){ //从右到左sink()方式构造堆，右指的不是最右边，而是从中间向左逼近 int len = vec.size(); //从最后一个节点的父节点开始调整 for(int i = len / 2 - 1; i >=0; i++){ heap_bulid(vec, i, len); } //构建完后开始排序 for(int j = len - 1; j > 0; j--){ swap(vec[0], vec[j]); //交换完后从新建堆,这个堆的长度就要减去被移除(堆顶的那个)的最大元素之后的长度，所以长度不断变化，必须参数要带上长度 heap_build(vec, 0, j); } }- 了解优先队列。
跟堆有关的题目
问：编写算法，从10亿个浮点数当中，选出其中最大的10000个。
答：典型的Top K问题，用堆是最典型的思路。建10000个数的小顶堆，然后将10亿个数依次读取，大于堆顶，则替换堆顶，做一次堆调整。结束之后，小顶堆中存放的数即为所求。
问：设计一个数据结构，其中包含两个函数，1.插入一个数字，2.获得中数。并估计时间复杂度。
使用大顶堆和小顶堆存储。答：使用大顶堆存储较小的一半数字，使用小顶堆存储较大的一半数字。插入数字时，在O(logn)时间内将该数字插入到对应的堆当中，并适当移动根节点以保持两个堆数字相等（或相差1）。获取中数时，在O(1)时间内找到中数。
为什么都在用快排而不是归并，堆？
问：我们知道，快排平均复杂度为nlogn，最坏时间复杂度为$n^2$，而归并排序最坏才是nlogn。那么为什么还是用快排多，用归并少呢？
我觉得原因有以下几个：
- 首先了解O的含义，即O(nlgon)的O。大O符号又称为渐进符号，在数学上表示一个函数的渐进行为的符号，描述一个函数数量级的渐进下界，不考虑首项系数和低阶项。比如说有一个规模n的算法花费时间$T(n)=n^2+2n+c$，可以看到当n增大的时候$n^2$开始占据主导地位，因此$O(n)=n^2$。在实际的生产生活中我们所用的n并没有达到那么大的规模，因此这个2n+c这个点是不可以忽略的。
- 快速排序一般是原地排序，不需要创建任何的辅助数组来保存临时变量。而归并排序需要用到两个额外的数组进行存储，同时将数组合并成为一个也会花费点时间。
就常数项来说，快排< 归并 < 堆
问：什么场景下用归并比用快排好？
当对连链表结构进行排序的时候，归并排序比快排高效。因为链表的存储空间时分散的，必须到每个节点的地址再连接起来，这就导致快排依靠数组的优势不存在了。同时归并使用链表结构的话，直接连接就行，不需要额外的辅助空间。
优先队列
概念
在做堆排序的时候才知道这个堆排序的思想是从优先队列里面来的。
优先队列是一种抽象类型的数据结构，他的特征是：
- 队列中的每个元素都有各自的优先级，优先级高的先得到服务或者先处理
支持删除优先级高的元素，插入新元素
来看一看线性结构和堆来取优先级最高的元素的时间复杂度比较：
数据结构 入队 出队 普通线性结构 O(1) O(n) 顺序线性结构 O(n) O(1) 堆 O(lgn) O(lgn) 可以看到当时用堆这种数据结构的时候是比较高效的。
优先队列和堆的区别
这里面堆特指二叉堆。
二叉堆只是有点队列实现的一种方式。除此之外优先队列还有二项堆,配对堆,左偏树,斐波那契堆,平衡树，线段树，甚至是二进制分组的vector来实现一个优先队列等等。
代码实现
class Priority_queue { public: Priority_queue(int max_num) { int *a = new int[max_num]; a = { 0 }; } ~Priority_queue() { delete[] a; } void Insert(int num) ; bool delete_max(); void build_max_heap(int *a, int length); int max_num(); void sort(); private: int capacity; int len; int *a; }; void Priority_queue::build_max_heap(int *a, int length) { } int Priority_queue::max_num() { } bool Priority_queue::delete_max() { } void Priority_queue::Insert(int num) { } void Priority_queue::sort() { }