石家庄做网站建设的公司排名,网络设计概念,wordpress 添加过滤器,网站建站网站微信公众号开发目录 一、基本思想
二、动图演示#xff08;hoare版#xff09;
三、思路分析#xff08;图文#xff09;
四、代码实现#xff08;hoare版#xff09;
五、易错提醒
六、相遇场景分析
6.1 ❥ 相遇位置一定比key要小的原因
6.2 ❥ 右边为key#xff0c;左边先走 …目录 一、基本思想
二、动图演示hoare版
三、思路分析图文
四、代码实现hoare版
五、易错提醒
六、相遇场景分析
6.1 ❥ 相遇位置一定比key要小的原因
6.2 ❥ 右边为key左边先走
6.3 ❥ 一边为key另一边先走的原因
七、时间复杂度分析
八、快排的优化
8.1 ❥ key值的选取
8.1.1 随机数选key
8.1.2 三数取中
8.2 ❥ 小区间优化
九、挖坑法
9.1 ❥ 动图演示
9.2 ❥ 思路详解
9.3 ❥ 代码实现
十、前后指针法
10.1 ❥ 动图演示
10.2 ❥ 思路详解
10.3 ❥ 代码实现 一、基本思想
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。
其基本思想为
任取待排序元素序列中的某元素作为基准值按照该排序将待排序集合分割成两个子序列左子序列中所有元素均小于基准值右子序列中的所有元素均大于基准值然后分别对左右两部分重复上述操作直到将无序序列排列成有序序列。 二、动图演示hoare版 三、思路分析图文
以下以升序为例 简言之就是先进行单趟的排序单趟排完之后key已经放在它合适的位置上分割出了一个左区间和右区间然后进行递归排序当左右区间都有序时那么就整体有序。 四、代码实现hoare版
void swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}//hoare版
void QuickSort(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; //将begin下标位置赋给keyi//分割出左右区间// [left, keyi-1] keyi [keyi1, right]//整体排序 递归QuickSort(a, left, keyi - 1);QuickSort(a, keyi1,right);} 五、易错提醒
我们看如下一段代码
void QuickSort(int* a, int left, int right)
{if (left right){return;}int keyi left;int begin left;int end right;while (begin end){while (a[end] a[keyi]){end--;}while (a[begin] a[keyi]){begin;}swap(a[begin], a[end]);}swap(a[begin], a[keyi]);keyi begin;QuickSort(a, left, keyi - 1);QuickSort(a, keyi 1, right);
}上述代码是有问题存在的
通过调试可知第二个while遇到相遇要停止这里while少了相遇停止条件否则可能会一直死循环下去 为何要创建begin和end 通过上述思路分析易知区间的每次分割left都需要指向原始序列第一个元素的位置right指向原始序列最后一个元素的位置所以这里专门定义一个begin和end 而不是用left和right去 --就是为了便于分割区间。 六、相遇场景分析 6.1 ❥ 相遇位置一定比key要小的原因
我们发现每次L与R相遇时与key进行交换时L的值都小于key这是为什么呢
这里对他们相遇的场景进行分析
相遇时无非两种场景要么R遇见L要么L遇见R
L遇R R先走找小停下来。 R停下条件是遇见比key小的值R停的位置一定比key小L没有找到大的遇见R停下 所以说L遇R它们相遇的位置就是R的位置 R遇L R先走找小没有找到比key小的直接跟L相遇了。 L停留的位置是上一轮交换的位置 上一轮交换把比key小的值换到了L的位置 6.2 ❥ 右边为key左边先走
我们发现上面相遇场景都是左边做key如果右边做key让左边先走呢
右边做key时相遇位置一定比key要大
如下图所示 结论 左边做key右边先走可以保证相遇位置一定比key小右边做key左边先走可以保证相遇位置一定比key大 6.3 ❥ 一边为key另一边先走的原因
有人肯定会疑惑为什么要一边做key另一边先走不可以做key的一边先走吗
可以验证一下 上图是让key在左边且左边先走在8相遇然后与key5进行交换
交换完后5换到了数组下标为5的位置并没有换到他所对应的正确位置且左区间的8比5大。
我们知道快排是当一趟排完之后左区间都比key小右区间都比key大且key刚好在正确位置上这样才可以继续分左右区间进行递归排序。
因此不可以做key的一边先走 结论一边做key只能让另一边先走 七、时间复杂度分析 在比较理想的情况下快排的递归结构接近完全二叉树所以层数为logn层每一层排序次数近似为n即单趟的时间复杂度为n 故时间复杂度为O(nlogn) 但是在有序场景下使用快排会性能会下降时间复杂度为O(N^2)
如下图所示 当key在左边时右边R找小就会找不到然后一直往左走直到在key处相遇然后自己跟自己交换结束一趟的排序。分割出左右区间。此处没有左区间只存在右区间就这样依次类推......那么总共执行的次数就会是一个等差数列即时间复杂度为O(N^2)它的效率就会大幅度降低。 八、快排的优化 经过时间复杂度的分析发现当前的快排算法还是存在一些缺陷的那就是在有序场景下使用快排会性能会下降此外还有可能导致栈溢出。为什么在有序场景下会发生栈溢出因为每走一层就是一个递归这里递归的深度太深会有栈溢出的风险。所以快排在此还是有较为明显的缺陷的面对这些缺陷我们在此应怎么解决呢我们知道时间复杂度为O(nlogn)的前提是每次区间的划分都是二分也就是每次选择交换的key都是接近中间位置的值哪怕不那么接近二分但整体深度是logn就可以所以key值的选取非常关键如果固定的选择最左边下标为0的值就有可能选到最小的值然后出现效率退化栈溢出的风险那如何选key才能避免有序的情况下效率退化呢下面提供了两种选取key值的方式 8.1 ❥ key值的选取
8.1.1 随机数选key 如果想要输出给定范围[a,b]内的随机数需要使用rand()%(b-a1)a缺陷可能刚刚好选到最大或者最小值 代码如下
void rand_key(int* a, int left, int right)
{int randi left (rand() % (right - left 1));swap(a[left], a[randi]);
} 8.1.2 三数取中 所谓三数取中就是从最左边最右边最中间三个位置选择中间的值不大不小的值作为key赋值给key 代码如下
int GetMidi(int* a, int left, int right)
{int midi (left right) / 2;if (a[left] a[right]){if (a[left] a[midi]) // rlm{return left;}else if(a[midi]a[right]) //mrl{return right;}else //rml{return midi;}}else{if (a[right]a[midi]) //lrm{return right;}else if (a[midi]a[left]) //mlr{return left;}else //lmr{return midi;}}
} 注意 这里是选出的中间值还应跟最左边的值进行交换还应该让最左边的值作为key 8.2 ❥ 小区间优化
为何要有小区间优化 当将一组待排序列进行快排递归到只剩下5个值时我们还要进行选key分割左右区间等操作让5个值有序此刻使用递归调用花费代价太大最后一层递归调用就要占整体递归调用的50%这就引入了小区间优化的方式。 小区间优化目的 当待排区间长度小于等于某个阈值时不再递归分割排序减少递归调用的深度和对栈空间的使用避免过度分割导致的效率下降可以在处理小规模数据时获得更好的性能从而提高整体排序算法的效率。 思路分析 这里选择直接插入排序首先希尔排序适合数据量较大时使用这里不适合使用。直接插入排序在同是O(N^2)的情况下它的速度要更快因为通常情况下它是达不到O(N^2)只有在完全有序的情况下才能达到O(N^2)所以同级情况下它要比其它排序更快一点它的实践意义也在于此。当然引入小区间优化会使得效率低下增加了算法的复杂度。 代码如下
//直接插入算法
void InsertSort(int* a, int n)
{for (int i 0; i n - 1; i){int end i;int tmp a[end 1];while (end 0){if (tmp a[end]) {a[end 1] a[end];end--;}else{break;}}a[end 1] tmp;}
}//交换算法
void swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}//三数取中
int GetMidi(int* a, int left, int right)
{int midi (left right) / 2;if (a[left] a[right]){if (a[left] a[midi]) {return left;}else if (a[midi] a[right]) {return right;}else {return midi;}}else{if (a[right] a[midi]) {return right;}else if (a[midi] a[left]) {return left;}else {return midi;}}
}//hoare版
void QuickSort(int* a, int left, int right) //参数为数组下标
{if (left right){return;}// 小区间优化不再递归分割排序减少递归的次数if ((right - left 1) 10){InsertSort(a left, right - left 1);}else{//三数取中int midi GetMidi(a, left, right);swap(a[left], a[midi]);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;QuickSort(a, left, keyi - 1);QuickSort(a, keyi 1, right);}
} 九、挖坑法
这里的挖坑法是以单趟排序的思路优化出的挖坑法。
该方法没有效率的提升因为单趟排序效率无提升空间至少都得遍历一遍
但理解起来更简单因为它们相遇的位置是坑所以不用分析左边做key右边先走的问题也不用分析相遇位置比key小的原因 9.1 ❥ 动图演示 9.2 ❥ 思路详解 将序列的第一个元素作为基准值存放在临时变量key中此时的第一个坑位形成L指向第一个元素R指向最后一个元素R开始向前移动R--找比key小的值找到后将R指向的值填入L的坑位此时R形成一个坑位然后L开始向后移动L找比key大的值找到后将L指向的值填入R的坑位此时L形成一个坑位R和L交错移动形成新的坑位直到R与L相遇此时将key值填入L和R共同所指向的坑位单趟排序完成然后分割左右区间进行递归排序最后排成一个有序序列 9.3 ❥ 代码实现
//挖坑法
void QuickSort1(int*a,int left,int right)
{//递归结束条件 if (left right){return;}int key a[left];int begin left;int end right;//单趟排序while (begin end){while (beginenda[end] key){end--;}a[begin] a[end]; //甩给右区间坑while (beginenda[begin] key){begin;}a[end] a[begin]; //甩给左区间坑}a[begin] key; //将key填入相遇的坑//进行递归排序QuickSort1(a, left, begin - 1);QuickSort1(a, begin 1, right);}十、前后指针法
前后指针法只是单趟逻辑改变整体递归思路并没有改变。
该方法没有效率的提升。 10.1 ❥ 动图演示 10.2 ❥ 思路详解 将key指向序列的第一个元素设为基准值prev指向key的位置cur指向prev的下一个位置对cur进行判断 如果curkey则cur 如果curkeyprev交换cur和prev所指向的值然后cur 再对cur进行判断直到cur到序列的最后一个元素的下一个位置交换prev与key的值此时单趟排序完成然后分割左右区间进行递归排序最后排成一个有序序列 10.3 ❥ 代码实现
void swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}//前后指针法
void QuickSort2(int* a, int left, int right)
{if (left right){return;}//单趟排序int keyi left;int prev left;int cur left 1;while (curright){if (a[cur] a[keyi]) //cur的值比keyi的值小{prev;if (prev ! cur) //判断prev与cur是否指向同一位置{swap(a[prev], a[cur]);}}cur;}swap(a[prev], a[keyi]);QuickSort2(a, left, prev - 1);QuickSort2(a, prev 1, right);}
