高阶排序
1、快速排序
冒泡排序的升级算法
每次选择一个基准数，把小于基准数的放到基准数的左边，把大于基准数的放到基准数的右边，采用 “ 分治算法 ”处理剩余元素，直到整个序列变为有序序列。
最好和平均的复杂度：
时间复杂度：O(n)*O(logn) = O(nlogn)
空间复杂度：O(logn) 递归的深度所占用的栈内存
最坏的情况（有序的元素）：元素有几个，其深度就有几个，此时时间复杂度为 O(n^2) , 空间复杂度为O(n)
思路
实例理解
对于数组arr[] = {46,8,76,10,38,7,68,32,65,53};进行快速排序。
循环的条件 L< R
1、选取基准数 val = arr[L]; // val = 46
2、从R开始往前找第一个 <val 的数字，放到L的地方。（这里不用担心数据被覆盖，因为val已经将值保存）， L++ 。
3、从L开始，往后找第一个 >val 的数字，放到R的地方， R-- 。
4、重复上面的过程，直到循环结束（循环条件为 L<R)
运行到循环结束
此时，将val的值写入 arr[L] 最终一趟下来的结果为
一趟下来，此时，arr[L] 左边的值全部小于val–46,左边全部大于val–46。
此时，继续对两边的数据继续快排。
最终结果为：
代码实现
//快排分割处理函数
int Partation(int arr[], int left, int right)
{//记录基准数int val = arr[left];//进行一次快排分割处理 O(n)*O(logn) = O(nlogn) 空间复杂度：O(logn) 递归的深度所占用的栈内存while (left < right){while (left < right && arr[right] > val){right--;}if (left < right){arr[left] = arr[right];left++;}while (left < right && arr[left] < val){left++;}if (left < right){arr[right] = arr[left];right--;}}//left == right 的位置，就是放基准数的位置arr[left] = val;return left;
}//快排的递归接口
void QuickSort(int arr[], int begin, int end)
{if (begin >= end)//快排递归结束的条件{return;}//在[begin,end]区间的元素进行一次快排分割处理int pos = Partation(arr,begin,end);//对基准数的左边和右边的序列，再分别进行快排QuickSort(arr,begin,pos-1);QuickSort(arr,pos+1,end);}//快速排序
void QuickSort(int arr[], int size)//为了区别自带的快速排序函数
{return QuickSort(arr,0,size-1);
}int main()
{int arr[10];srand(time(NULL));for (int i = 0; i < 10; i++){arr[i] = rand() % 100 + 1;}for (int v : arr){cout << v << " ";}cout << endl;QuickSort(arr, sizeof(arr) / sizeof(arr[0]));for (int v : arr){cout << v << " ";}cout << endl;return 0;
}
测试
快速排序的算法优化、效率提升
1）对于小段趋于有序的序列采用插入排序
2）三数取中法。旨在挑选合适的基准数，防止快排退化成冒泡排序。
3）随机数法
特点
快速排序是个不稳定的排序算法
当数据趋于有序，或者已经有序了，快速排序的效率是很差的，但是快速排序的效率是最好的。
快排算法优化一：
1、随着快速排序算法执行，数据越来越趋于有序，在一定范围内，可以采用插入排序代替快速排序
相关代码：
//针对快排优化设计的插入排序
void InsertSort(int arr[], int begin,int end)
{for (int i = begin; i <= end; i++)//O(n){int val = arr[i];int j = i - 1;for (; j >= 0; j--) //O(n){if (arr[j] <= val){break;}arr[j + 1] = arr[j];}//val -> j+1arr[j + 1] = val;}
}
void QuickSort(int arr[], int begin, int end)
{if (begin >= end)//快排递归结束的条件{return;}//优化一：当[begin,end] 序列的元素个数小到指定数量，采用插入排序if (end - begin <= 50)//这里的范围视情况而定{InsertSort(arr,begin,end);return;}//在[begin,end]区间的元素进行一次快排分割处理int pos = Partation(arr,begin,end);//对基准数的左边和右边的序列，再分别进行快排QuickSort(arr,begin,pos-1);QuickSort(arr,pos+1,end);}
快排算法优化二：选择基准数的优化，采用“三数取中”法
采用“三数取中”法，找合适的基准数。
mid = (L+R)/2;
2、归并排序
也采用 “ 分治思想 ”，先进行序列划分，再进行元素的有序合并。
时间复杂度：O(n logn)
空间复杂度：O(logn)+O(n) — 取大的 — O(n)
核心思想
类比于递归思想，核心在于递和归。
递—将数据规模不断的减小，减小到结果已知的规模。
归—通过已知的规模反推而上，不断解决上一层规模的问题，最终累计出原始数据 的结果。
所以归并排序的思想：在归的过程中，进行的数据合并，达到排序的效果。
难点
上述思想衍生出的问题和难点：
1）递到什么程度，才开始归？
2）在归的过程中，如何进行数据合并？
对数数据规模需要一个前后指针，一个起始下标，一个末尾下标。进行二路归并，需要中间值，int mid = (L+R)/2;
递的过程：
将数据分两半，
归并的过程：
数据合并，也就是叶子节点网根节点回退。
重新开辟一个空间，将两个有序的叶子节点合并递归到上一层，不断重复，直到归并到根节点，此时数据处理完毕。
代码实现
//归并过程函数
void Merge(int arr[], int l, int m, int r)
{int* p = new int[r-l+1];int idx = 0;int i = l;int j = m + 1;while (i <= m && j <= r){if (arr[i] <= arr[j]){p[idx++] = arr[i++];}else{p[idx++] = arr[j++];}}while (i <= m){p[idx++] = arr[i++];}while (j <= r){p[idx++] = arr[j++];}//再把合并好的大段有序的结果，拷贝到原始arr[数组[l,r]区间内for (i = l, j = 0; i <= r; i++, j++){arr[i] = p[j];}delete[]p;}//归并排序递归接口
void MergeSort(int arr[], int begin, int end)
{//递归结束的条件if (begin >= end){return;}int mid = (begin + end) / 2;//先递MergeSort(arr,begin,mid);MergeSort(arr,mid+1,end);//再归并 [begin,mid] [mid+1,end] -- 把两个小段有序的序列，合并成一个大段的有序序列Merge(arr,begin,mid,end);
}//归并排序
void MergeSort(int arr[], int size)
{return MergeSort(arr, 0, size - 1);
}
测试
int main()
{int arr[10];srand(time(NULL));for (int i = 0; i < 10; i++){arr[i] = rand() % 100 + 1;}for (int v : arr){cout << v << " ";}cout << endl;MergeSort(arr, sizeof(arr) / sizeof(arr[0]));for (int v : arr){cout << v << " ";}cout << endl;return 0;
}
3、堆排序
二叉堆
二叉堆就是一颗完全二叉树，范围两种典型的堆，分别是大根堆和小根堆
基于二叉堆的基础，规定了当前节点和两个孩子节点值的大小关系。
满足 0 <= i <= (n-1)/2 , n 代表最后一个元素的下标。
如果 arr[i] <= arr[2 * i + 1] && arr[i] <= arr[2*i + 2] ,就是小根堆。
如果 arr[i] >= arr[2 * i + 1] && arr[i] >= arr[2*i + 2] ,就是大根堆。
二叉堆，实际上（物理上）还是用数组存储的元素，只是逻辑上，将其看成有一个人口根节点，
每个节点都有两个孩子，没有孩子的最下一层，称之为叶子节点，这样的二叉树结构，称之为完全二叉树。
完全二叉树：
完全二叉树相比于二叉树，最后一层的叶子节点都是靠左排列，
优点是在存储二叉树节点的时候，比较省数组内存空间。
最后一层的叶子节点都是靠左排列的，每一层的节点都是满的。
最下层节点，必须从左往右都有，中间空一个都不算。
如何将数组存储的元素，逻辑上看成完全二叉树？当前节点和两个孩子节点有什么关系？
在数组中，满足下图关系的节点，在逻辑上看成二叉树当前节点和其左右节点。
如何获得第一个非叶子节点的下标？
(n-1)/2
堆的上浮和下层调整（添加删除元素）
入堆（大根堆入堆示例）
数组的元素添加，在数组末尾添加元素。
相对应的，逻辑上，在二叉树的最下层如图所示位置，添加新元素。
但此时，破坏了此时完全二叉树的逻辑，需要进行调整。、
因为是大根堆，所以要对数据进行上浮调整。
这里新的元素10大于父节点5，进行交换。
交换过后，发现还是比父节点大，继续交换。
如下图所示，元素上浮到根节点，上浮结束。
注意，人堆不是入到堆顶，是入到小于父节点的位置。
出堆（大根堆出堆示例）
大根堆出堆，出堆顶元素。
优先级队列实现的时候，假设值越大，优先级越大，这里为大根堆，出元素，就先出堆顶元素。
当然也可以规定，值越小，优先级越小。
出堆操作
将堆顶元素取出。
将最后的数据放到堆顶，该值相对是偏小的。
从零号元素开始，往下调整，继续下层调整操作
比较节点两个孩子节点，将孩子节点中较大值，覆盖，进行下层操作。
以此类推，直到元素无孩子节点，或者孩子节点都小于该元素。
将val覆盖该位置的值。
基于堆的优先级队列代码实现
类似于C++库中的priority_queue，其底层也是数组，只不过没有自己写数组。如果自己写数组，就成为容器了，而不是容器适配器，其只是对底层容器（vector）进行适配。
//优先级队列实现 priority_queue(vector) -- push pop top empty size
class PriorityQueue
{
public://模板定义一个函数对象using Comp = function<bool(int,int)>;//这里默认大根堆PriorityQueue(int cap = 20, Comp comp = greater<int>()):size_(0), cap_(cap), comp_(comp){que_ = new int[cap_];}//PriorityQueue(Comp comp = greater<int>())PriorityQueue(Comp comp):size_(0), cap_(20), comp_(comp){que_ = new int[cap_];}~PriorityQueue(){delete[] que_;que_ = nullptr;}
public://入堆操作 O(log n) O(1)void push(int val){//判断扩容if (size_ == cap_){int* p = new int[2 * cap_];memcpy(p,que_,cap_*sizeof(int));delete[]que_;que_ = p;cap_ *= 2;}if (size_ == 0){//只有一个元素，不用进行堆的上浮调整que_[size_] = val;}else{//堆里面有多个元素，需要进行上浮调整siftUp(size_,val);}size_++;}//出堆操作void pop(){if (size_ == 0)throw "container is empty!";size_--;if (size_ > 0){// 删除堆顶元素，还有剩余的元素，要进行堆的下沉调整siftDown(0,que_[size_]);}}bool empty() const { return size_ == 0; }int top()const{if (size_ == 0)throw "container is empty!";return que_[0];}int size() const { return size_; }
private://入堆上浮调整void siftUp(int i, int val){while (i > 0)//最多计算到根节点（0号位）{int father = (i - 1) / 2;if (comp_(val, que_[father])){que_[i] = que_[father];i = father;}else{break;}}//把val放到i的位置que_[i] = val;}//出堆下沉调整void siftDown(int i, int val){//i下沉不能超过最后一个有孩子的节点//while (i <= (size_ - 1 - 1) / 2)while (i < size_ / 2){int child = 2 * i + 1;//第i个节点的左孩子if (child + 1 < size_ && comp_(que_[child+1],que_[child])){//如果i节点右孩子的值大于左孩子，child记录右孩子的下标child = child + 1;}if (comp_(que_[child], val)){que_[i] = que_[child];i = child;}else{break;//已经满足堆的性质，提前结束}}que_[i] = val;}
private:int* que_; // 指向动态扩容的数组int size_; // 数组元素的个数int cap_; // 数组的总内存空间大小Comp comp_; //比较器对象};
测试
int main()
{PriorityQueue que;//基于大根堆实现的优先级队列PriorityQueue que1([](int a, int b) {return a < b; });//基于小根堆实现的优先级队列srand(time(NULL));for (int i = 0; i < 10; i++){que.push(rand()%100);que1.push(rand() % 100);}while (!que.empty()){cout << que.top() << " ";que.pop();}cout << endl;while (!que1.empty()){cout << que1.top() << " ";que1.pop();}cout << endl;
}
堆排序代码实现
堆排序的实现，需要借助于大根堆或者小根队的性质。如果需要从小到大排序，需要借助于大根堆。反之，借助小根堆。
思路
对于下图所示无序原始序列，将其这些在数组里存放的元素，逻辑上看作一个二叉堆。
1、从第一个非叶子节点开始，把二叉堆调整成一个大根堆
其中，第一个非叶子节点的小标为 ( n - 1 )/2,如图所示为数字8
从第 ( n - 1 )/2号位元素开始，到堆元素（0），进行下沉操作。
2、把堆顶元素和当前末尾元素进行交换，从零号位继续开始进行部分的堆的下沉
上一趟取得的剩余元素的最大值，将其置于末尾，该元素处理完毕。
下一趟就不管该值，对剩下的元素继续进行下沉操作
3、重复操作二，不断获取剩余元素最大值，并将其下沉
代码实现
//堆的下沉调整
void siftDown(int arr[], int i, int size)
{int val = arr[i];//记录一下要调整的值//while(i <= (size-1-1)/2)while (i < size / 2){int child = 2 * i + 1;if (child + 1 < size && arr[child + 1] > arr[child]){child = child + 1;}if (arr[child] > val){arr[i] = arr[child];i = child; //i 继续指向其孩子，继续调整，直到最后一个有孩子节点的节点}else{break;}}arr[i] = val;
}//堆排序
void HeapSort(int arr[], int size)
{int n = size - 1;//从第一个非叶子节点for (int i = (n - 1) / 2; i >= 0; i--){siftDown(arr,i,size);}//将堆顶元素和当前末尾元素进行交换，从堆顶再一次进行下沉操作for (int i = n; i > 0; i--){int tmp = arr[0];arr[0] = arr[i];arr[i] = tmp;siftDown(arr,0,i); //第三个参数，参与调整的元素的个数，没处理一次，减一}
}测试
int main()
{int arr[10];srand(time(NULL));for (int i = 0; i < 10; i++){arr[i] = rand() % 100 + 1;}for (int v : arr){cout << v << " ";}cout << endl;HeapSort(arr, sizeof(arr) / sizeof(arr[0]));for (int v : arr){cout << v << " ";}cout << endl;return 0;
}
