短链生成网站_重庆网站开发_如何写市场调研报告_网络推广培训班

前言：

本章节将详细讲解排序算法中的快速排序，这里写的是C语言版本   

快速排序是Hoare于1962年提出的⼀种⼆叉树结构的交换排序⽅法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两⼦序列，左⼦序列中所有元素均⼩于基准值，右⼦序列中所有元素均⼤于基准值，然后最左右⼦序列重复该过程，直到所有元素都排列在相应位置上为止。

一、递归版本

1.1 hoare版本

算法思路 ：

1.创建左右指针，确定基准值

2.从右向左找出⽐基准值⼩的数据，从左向右找出⽐基准值⼤的数据，左右指针数据交换，进⼊下次循环

void swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}void QuickSort1(int* a,int left,int right)
{//若只有一个元素，或者没有元素，直接返回if (left >= right)return;int keyi = left;int begin = left;int end = right;while (begin < end){while (begin < end && a[end] >= a[keyi]){end--;}while (begin < end && a[begin] <= a[keyi]){begin++;}swap(&a[begin], &a[end]);}swap(&a[begin], &a[keyi]);keyi = begin;//[left , keyi-1] [keyi+1 , right]//递归子区间QuickSort1(a, left, keyi - 1);QuickSort1(a, keyi+1, right);}

问题1：为什么left 和 right指定的数据和key值相等时不能交换？

 

问题2：为什么跳出循环后right位置的值⼀定不⼤于key？

我先说规律：左边作为基准值，右边先走，相遇位置一定比key的值小，反之也成立！

具体的图我就不画了，你们按这个去推导，无非就这两种情况

OK，第一个版本的递归就写完了，其实还能优化，但是我想先把3个版本都写完在写快排的优化吧！

1.2 挖坑法

算法思路：

创建左右指针。⾸先从右向左找出⽐基准⼩的数据，找到后⽴即放⼊左边坑中，当前位置变为新的"坑"，然后从左向右找出⽐基准⼤的数据，找到后⽴即放⼊右边坑中，当前位置变为新的"坑"，结束循环后将最开始存储的分界值放⼊当前的"坑"中，返回当前"坑"下标（即分界值下标）

void QuickSort2(int* a, int left, int right )
{if (left >= right)return;int hole = left;int key = a[left];int begin = left;int end = right;while (begin < end){//右边找小while (begin < end && a[end] >= key)end--;a[hole] = a[end];hole = end;//左边找大while (begin < end && a[begin] <=key)begin++;a[hole] = a[begin];hole = begin;}a[hole] =key;//[left,hole-1] [hole+1, right]QuickSort2(a,left,hole-1);QuickSort2(a, hole+1,right);}

1.3 lomuto前后指针版本

创建前后指针，从左往右找⽐基准值⼩的进⾏交换，使得⼩的都排在基准值的左边。

void QuickSort3(int*a,int left ,int right)
{if (left >= right)return;int cur = left + 1;int prev = left;int keyi = left;while (cur <= right){if (a[cur] < a[keyi]){++prev;swap(&a[cur], &a[prev]);++cur;}if (a[cur] >= a[keyi]){++cur;}}swap(&a[keyi], &a[prev]);keyi = prev;QuickSort3(a, left, keyi - 1);QuickSort3(a, keyi + 1, right);
}

 二、快排优化

2.1 时间复杂度的计算

    2.1.1 理想状态

    理想状态中的快排是个满二叉树,树的高度是log以2为底的N（这是二叉树的结论，我就直接用来用了），然后第一行的个数是n，第二行是n-1,第n行时n-key的个数，但是由于树的高度是log以2为底的N,所以最后一行是N-（首项为1，公比为2 ，项数为log以2为底N的对数的等比数列的和），由于log这个为低阶项，所以近似认为每行为N个元素，所以理想状态的时间复杂度为N*logN

2.1.2 有序状态

    这种情况下是等差数列，时间复杂度是N^2

2.1.3 大量重复数据

基准值选取与划分问题

    快速排序通过选定基准值，将数组划分为两部分。理想状况下，每次划分能让两部分规模大致相等，递归树近似满二叉树，高度为O(logn) ，时间复杂度为O(nlogn) 。但大量重复数据时，基准值若恰好是重复值，或重复数据分布不均，易使划分极度不平衡 。比如大部分元素都等于基准值，都被划分到同一侧，导致一侧子数组规模很大，另一侧很小，递归树退化为链表状，递归深度从O(logn) 变为O(n) 。

冗余操作

    传统快速排序对于重复元素，依旧会不断比较和交换 。例如，已有很多相等元素，还反复判断它们与基准值的大小关系并交换位置，这些操作对排序结果无实质帮助，却耗费大量时间，使得操作次数大幅增加。当数据规模为n 时，随着上述无意义操作增多，整体操作次数接近N^2 量级，时间复杂度近似为O(n2) 。

    总结：

            两边划分的越均匀，效率越优！！！

   2.2 优化

    2.2.1 随机选key 

	//随机选keyint randi = left + (rand() % (right - left));//%(right-left)让随机数始终在这正确区间内，加上left是因为每个区间的开始是leftswap(&a[left], &a[randi]);int keyi = left;

    2.2.2 三数取中

int GetMidNumi(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}else // a[left] > a[mid]{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]){return left;}else{return right;}}
}

    以上两种优化都是为了解决有序的情况！！！

2.2.3 三路划分

    专门为了解决大量重复元素的算法:

    (先不写，后续会进行补充)

三、非递归版本

//非递归辅助接口
int PartSort(int* a ,int left,int right)
{int cur = left + 1;int prev = left;//三数取中int mid = GetMidNumi(a, left, right);swap(&a[left], &a[mid]);//随机选key//int randi = left + (rand() % (right - left));//%(right-left)让随机数始终在这正确区间内，加上left是因为每个区间的开始是left//swap(&a[left], &a[randi]);int keyi = left;while (cur <= right){if (a[cur] < a[keyi]){++prev;swap(&a[cur], &a[prev]);++cur;}if (a[cur] >= a[keyi]){++cur;}}swap(&a[keyi], &a[prev]);keyi = prev;return keyi;}//快排非递归
void QuickSortNonR(int* a, int left, int right)
{stack st;STInit(&st);//栈的初始化STPush(&st, right);//入栈STPush(&st, left);while (!STEmpty(&st)){int begin = STTop(&st);取栈顶元素STPop(&st);int end = STTop(&st);STPop(&st);int keyi = PartSort(a, begin, end);// [begin,keyi-1] keyi [keyi+1, end]if (keyi + 1 < end){STPush(&st, end);STPush(&st, keyi + 1);}if (begin < keyi - 1){STPush(&st, keyi - 1);STPush(&st, begin);}}STDestroy(&st);//栈的销毁
}

    用栈进行辅助，上面我是直接用写好的栈的接口的，你们可以自己写个栈，基本思路就是：

3.1  划分操作

    与递归版快排一样，先实现数组的划分函数。通过选定一个基准元素（可以用三数取中、随机选取等策略优化），将数组分为两部分，使得左边部分元素小于等于基准，右边部分元素大于等于基准，并返回基准元素的最终位置。

    

3.2  利用栈模拟递归

    初始化栈：创建一个栈结构（可以是顺序栈或链式栈），用于存储待排序子数组的左右边界。

    入栈操作：将原始待排序数组的左右边界下标压入栈中，代表整个数组作为第一个待处理的子问题。

    循环处理：当栈不为空时，不断从栈中弹出左右边界，获取当前要处理的子数组范围。对该子数组进行划分操作，得到基准元素的位置。然后将基准元素左右两侧非空的子数组边界（如果存在）压入栈中。这一步相当于递归版中对基准元素左右子数组分别进行递归调用，只不过这里用栈来管理待处理的子数组，而非递归调用。

    结束条件：当栈为空时，意味着所有子数组都已处理完毕，排序完成。