c++数据结构算法复习基础--11--高级排序算法-快速排序-归并排序-堆排序

高阶排序

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;
}

4、性能测试

注意，rand 函数所给的随机数 范围为 0~32767。
cout << RAND_MAX << endl; // 打印rand函数所给随机数的最大值
如果测试数据量规模过大，例如千万、亿。其中重复的元素将会非常多。
所以为了测试的准确性，在每个测试区间内，都随机一些数据。例如区间0~32767，32768–32768+32767 …。第二个区间，随机数再加一些基数。