文章目录
复习梗概算法思想算法复杂度分析及稳定性如何优化？快速排序改进版代码C++快速排序个人青春版代码完整代码复习梗概
算法思想，别的排序名字直接就能让人联想到它的算法思想，唯独快速排序这个不能直接体现出算法思想，因为它太麻烦了图解脑图代码结构眼熟（算法学完思想不能忘，但是转换成代码容易忘，最方便的方式是记住代码的大概结构，比如循环，递归，判断这些，以及条件和他们的结构顺序，不是说这就是背代码，但这样确实有助于考场上一眼认出来相似的算法题，就是眼熟）最好时间复杂度与最坏时间复杂度取决于什么因素？？分析时间复杂度的方法为什么相等元素时也要调换位置，是为了什么？？优化方法有什么，从哪里入手？有几个函数组成？彼此作用是什么，结构是什么？算法思想
一句话概括：逐渐将所有元素都转换为轴点元素轴点：天选之点，比这个元素大的都要排在右边，小的都要排在左边细说步骤开始：首先选数组第一个元素为轴点，temp暂时保存轴点值定义begin和end指针，指向这段数组起点和终点，begin初始就是指向轴点的从end开始向左比较元素与轴点大小，比轴点大就不动，end–接着比； 小就直接转换到begin覆盖此时的begin位置元素（第一次覆盖的是轴点，我们已经保存了，不怕），begin++后移，然后下一次比较从begin开始从begin开始向右比较元素与轴点大小，比轴点小就不动，begin++接着比； 大就直接转换到end覆盖此时的end位置元素（此时end所指元素以及转换到begin之前的位置了，不怕），end–前移，然后下一次比较从end开始整体概括就是begin和end双向奔赴互相给对面找位置转换，符合右边比轴点大左边比轴点小的原则，最后相遇找到轴点位置的过程上述步骤循环begin和end相遇结束循环，记录此时位置为轴点位置，用轴点覆盖（由于上述步骤，此时begin和end相遇位置一定是下一个被覆盖的值，不怕）数组以轴点位置分为两段 ，分别再来一次上述步骤（递归）流程图来自腾讯网课，恋上数据结构与算法，李明杰老师
算法复杂度分析及稳定性
快速排序不稳定，怎么优化都没用影响快速排序的时间复杂度的因素：每次分割左右子序列是否平均！快速排序最好（平均）时间复杂度：O（nlogn）在最好情况下，每次分割左右子序列都是平均分割那么//算法时间复杂度分析，假如最开始的这个quiksout耗时T（n）void quikSort(vector<int> &array,int begin,int end){int pivotIndex = SearchAndSort(array,begin,end);上面语句中函数时间复杂度为O（n），因为寻找轴点和排序这个函数 过程就是遍历一边数组quikSort(array,begin,pivotIndex-1);因为平均分割，上面这个quiksort函数耗时就是T（n/2）quikSort(array,pivotIndex+1,end);因为平均分割，上面这个quiksort函数耗时就是T（n/2）}
经过上面的函数语句时间分析得到下面的等式经过数学手法得到最终时间复杂度为O（nlogn）同理，最坏时间复杂度为O（n2），比如数组每次轴点元素都是数组的最大值或最小值，导致每次分子序列都是1和n-1个
//算法时间复杂度分析，假如最开始的这个quiksout耗时T（n）void quikSort(vector<int> &array,int begin,int end){int pivotIndex = SearchAndSort(array,begin,end);上面语句中函数时间复杂度为O（n），因为寻找轴点和排序这个函数 过程就是遍历一边数组quikSort(array,begin,pivotIndex-1);因为不平均分割，子序列里没有元素直接返回，上面这个quiksort函数耗时就是T（1），可以忽略不计quikSort(array,pivotIndex+1,end);因为不平均分割，子序列里有除了首位轴点元素以外的所有元素，上面这个quiksort函数耗时就是T（n-1），以后就是n-2，n-3.。。到1，就是等差数列公式了}
空间复杂度：O（logn），应该与递归调用和系统栈有关系，以后会学
如何优化？
看了上面的时间复杂度分析，我们自然想到，优化就要从减少分割不平均的情况入手第一种优化方式：选择轴点过程不再是固定选择首位，而是随机选择，这样可以减少选到序列里最大或最小值作为轴点的情况，进而减少不平均分割第二种优化方式：当有元素与轴点元素相等时，也要进行转换覆盖，想象一下如果不进行，一个全是相同元素的数组进行快速排序，无疑是最坏级别的，所以这样可以促进两个子序列的平均，避免不平均可惜上面两种优化，都不能优化其不稳定的特征快速排序改进版代码C++
自己复刻的老师版本，代码结构尤其后面递归要眼熟
主要优化了代码结构，和循环那里
int SearchAndSort(vector<int> &array, int begin, int end){int pivotNum = array[begin];//思路是end--直到发生覆盖，然后进行begin++直到发生覆盖，又回到end--如此反复//很多时候两个if嵌套都可以改进成whilewhile (begin<end){while(begin<end){if(array[end]>pivotNum){//右侧值大于轴点值，不需要改动位置（覆盖begin当前元素），end--end--;}else{//右侧值小于轴点值array[begin] = array[end];begin++;break;//break只会打破一层循环，此时发生了覆盖，要掉头了}}while (begin<end){if(array[begin]<pivotNum){begin++;}else{array[end] = array[begin];end--;break;}}}array[end] = pivotNum;return end; //注意这里要返回end，因为判断元素是end-begin+1而begin有时存在-1的情况，会负负得正，而end即使是负的也不怕}void quikSort2nd(vector<int> &array,int begin,int end){if((end - begin +1)<2){return;}int pivotIndex = SearchAndSort(array,begin,end);//注意这里除了array都是值传递，不会影响主函数的begin和end值的，所以大可放心vectorPrint(array);quikSort2nd(array,begin,pivotIndex-1);quikSort2nd(array,pivotIndex+1,end);}
6 9 3 1 2 0 8 29 15 11 10快速排序改进版0 2 3 1 6 9 8 29 15 11 100 2 3 1 6 9 8 29 15 11 100 1 2 3 6 9 8 29 15 11 100 1 2 3 6 8 9 29 15 11 100 1 2 3 6 8 9 10 15 11 290 1 2 3 6 8 9 10 15 11 290 1 2 3 6 8 9 10 11 15 29算法用时：（微秒）[AlgoTime: 20004 us]
快速排序个人青春版代码
自己写的，献给年轻的自己
//快速排序：其实比较难想，整体概括就是begin和end双向奔赴互相给对面找位置，最后找到轴点位置的过程//自己看完思路写的快速排序，其实大体上和老师写的差不多，就是都写到一个里了，但是排查bug排查了两个小时都没找出问题出在哪void quikSort(vector<int> &array, int begin, int end){//没想到这个东西恶心了我两小时，end和begin分别代表数组头元素和尾元素下标//那么begin到end的元素数量就是end-begin+1而不是-1啊啊啊，这都能整错if ((end - begin + 1) < 2){return;}int tempBegin = begin;//临时存储begin的值，因为后面begin会变，我们还需要它代表下一个递归左数组的起点呢int tempEnd = end;//同上int pivot = array[begin];//临时存储轴点值，因为后面轴点这个位置会被覆盖int beginOrEnd = 1;//记录上次循环是end--了还是begin++了while (begin != end){if (beginOrEnd == 1)//如果上次循环动的是end--，或者第一次，那这次就从end开始//以end--为例子，end--有两种情况，一种array[end] > pivot不用动，接着比较，一种array[begin] > pivot，把当前end元素覆盖了，end--{if (array[end] < pivot)//第一次从end开始{array[begin] = array[end];begin++;beginOrEnd = 0;}else{end--;beginOrEnd = 1;}}else{if (array[begin] > pivot){array[end] = array[begin];end--;beginOrEnd = 1;}else{begin++;beginOrEnd = 0;}}}array[begin] = pivot;//把轴点值放到合适位置vectorPrint(array);quikSort(array, tempBegin, end - 1);quikSort(array, end + 1, tempEnd);}
6 9 3 1 2 0 8 29 15 11 10 快速排序基础版0 2 3 1 6 9 8 29 15 11 100 2 3 1 6 9 8 29 15 11 100 1 2 3 6 9 8 29 15 11 100 1 2 3 6 8 9 29 15 11 100 1 2 3 6 8 9 10 15 11 290 1 2 3 6 8 9 10 15 11 290 1 2 3 6 8 9 10 11 15 29 算法用时：（微秒）[AlgoTime: 20005 us]
完整代码
#include <iostream>#include <vector>#include "MeasureAlgoTime.hpp"using namespace std;void vectorPrint(vector<int> &array){for (int i = 0; i < array.size(); i++){cout << array[i] << ' ';}cout << endl;}//快速排序：其实比较难想，整体概括就是begin和end双向奔赴互相给对面找位置，最后找到轴点位置的过程//自己看完思路写的快速排序，其实大体上和老师写的差不多，就是都写到一个里了，但是排查bug排查了两个小时都没找出问题出在哪void quikSort(vector<int> &array, int begin, int end){//没想到这个东西恶心了我两小时，end和begin分别代表数组头元素和尾元素下标//那么begin到end的元素数量就是end-begin+1而不是-1啊啊啊，这都能整错if ((end - begin + 1) < 2){return;}int tempBegin = begin;//临时存储begin的值，因为后面begin会变，我们还需要它代表下一个递归左数组的起点呢int tempEnd = end;//同上int pivot = array[begin];//临时存储轴点值，因为后面轴点这个位置会被覆盖int beginOrEnd = 1;//记录上次循环是end--了还是begin++了while (begin != end){if (beginOrEnd == 1)//如果上次循环动的是end--，或者第一次，那这次就从end开始//以end--为例子，end--有两种情况，一种array[end] > pivot不用动，接着比较，一种array[begin] > pivot，把当前end元素覆盖了，end--{if (array[end] < pivot)//第一次从end开始{array[begin] = array[end];begin++;beginOrEnd = 0;}else{end--;beginOrEnd = 1;}}else{if (array[begin] > pivot){array[end] = array[begin];end--;beginOrEnd = 1;}else{begin++;beginOrEnd = 0;}}}array[begin] = pivot;//把轴点值放到合适位置vectorPrint(array);quikSort(array, tempBegin, end - 1);quikSort(array, end + 1, tempEnd);}int SearchAndSort(vector<int> &array, int begin, int end){int pivotNum = array[begin];//思路是end--直到发生覆盖，然后进行begin++直到发生覆盖，又回到end--如此反复//很多时候两个if嵌套都可以改进成whilewhile (begin<end){while(begin<end){if(array[end]>pivotNum){//右侧值大于轴点值，不需要改动位置（覆盖begin当前元素），end--end--;}else{//右侧值小于轴点值array[begin] = array[end];begin++;break;//break只会打破一层循环，此时发生了覆盖，要掉头了}}while (begin<end){if(array[begin]<pivotNum){begin++;}else{array[end] = array[begin];end--;break;}}}array[end] = pivotNum;return end; //注意这里要返回end，因为判断元素是end-begin+1而begin有时存在-1的情况，会负负得正，而end即使是负的也不怕}void quikSort2nd(vector<int> &array,int begin,int end){if((end - begin +1)<2){return;}int pivotIndex = SearchAndSort(array,begin,end);//注意这里除了array都是值传递，不会影响主函数的begin和end值的，所以大可放心vectorPrint(array);quikSort2nd(array,begin,pivotIndex-1);quikSort2nd(array,pivotIndex+1,end);}int main(){Tools::Time::AlgoTimeUs time1;Tools::Time::AlgoTimeUs time2;Tools::Time::AlgoTimeUs time3;vector<int> array;array = {6, 9, 3, 1, 2, 0, 8, 29, 15, 11, 10};vector<int> array2 = array;vector<int> array3 = array;time1.start();vectorPrint(array);cout << "快速排序基础版" << endl;quikSort(array, 0, (array.size() - 1));cout << "算法用时：（微秒）";time1.printElapsed();cout << ' ' << endl;time1.start();vectorPrint(array2);cout << "快速排序改进版" << endl;quikSort2nd(array2, 0, (array.size() - 1));cout << "算法用时：（微秒）";time1.printElapsed();cout << ' ' << endl;return 0;}
