快速排序文章目录快速排序1. 算法思想2. 双边循环法3. 单边循环法4. 额外补充 分治5. 复杂度分析5.1 最坏情况5.2 最好情况5.3 平均情况6. 稳定性分析7. 测试函数8. 头文件部分9. 实现9.1 双边循环法9.2 单边循环法10.测试案例main函数输出结果1. 算法思想快速排序⾸先选⼀个犄点可以认为是要放到排序后数组正确位置的元素pivot然后将数组按照选取的基准 pivot 进⾏划分⽽选取 pivot 的⽅式⼜有很多种所以快速排序具有很多版本总是选择第⼀个元素作为基准 pivot以这个举例总是选择最后⼀个元素作为犄点随机的选择⼀个元素作为犄点选择最中间的元素作为犄点快速排序的关键是划分partion()。每⼀趟划分我们就可以将作为 pivot 的值 x 放到排序数组的正确位置并且将所有⽐ x ⼩的放到 x 的左边所有⽐ x ⼤的元素放到 x 的右边。⽽且划分操作的时间复杂度是线性的即On量级下面我们介绍两种找**犄点(pivot)**的方法双边循环法单边循环法2. 双边循环法首先选择数组的第一个元素38当作犄点 我们要确定right指针右边的元素都比犄点大left指针左边的都比犄点小第一步移动right指针pivot指向的元素和right指针指向的元素进行比较此时right指针指向的元素小于pivot指向的元素right指针停下开始移动left指针移动left指针 left指针指向的元素和pivot指向的元素比较此时left指针指向的元素大于pivot指向的元素left指针停下交换left指针和right指针的值继续执行上述过程移动right指针移动left指针此时left指针和right指针相碰此时也就找到了最开始选择的pivot的正确位置也就是此时相碰的位置交换 左右指针相碰的位置 和 pivot 指向位置的值此时第⼀趟快速排序结束啦我们确定了最开始选择的pivot的正确位置接下就是分别对38左侧⽐38⼩的元素 [13,27] 与右侧⽐38⼤的元素进⾏快速排序过程和第⼀趟排序过程⼀样此处不再赘述 也就是下面这样另外提一嘴必须得是right先找 (留个悬念)3. 单边循环法首先选择数组的第一个元素38当作犄点指针i用来不断向后遍历 mark用来找到pivot的正确位置发现13比38小了mark指针往后走一步再与i交换位置 (值交换)i指针继续向后遍历 此时27比38小mark指针往后走一步再与i交换位置 (值交换)i指针继续向后遍历 遍历完了pivot指针和mark指针交换位置 (值交换)此时第⼀趟快速排序结束啦我们确定了最开始选择的pivot的正确位置接下就是分别对38左侧⽐38⼩的元素 [27,13] 与右侧⽐38⼤的元素 [97,76,65,49,49] 进⾏快速排序过程和第⼀趟排序过程⼀样此处不再赘述 也就是下面这样4. 额外补充 分治⼀趟快速排序结束了。就是将数组按照pivot分成了⼩于等于pivot的⼀组和⼤于pivot的⼀组可是分治的明显么好像不明显快速排序和归并排序(后面将会更新) ⼀样均属于分治算法分治与递归就是⼀个孪⽣兄弟提到了分治怎能缺少递归呢递归三要素中最核⼼的就是确定⼀个函数的功能⽽我们经过上⾯对⼀趟快速排序的介绍可以发现之后的每⼀趟快速排序事实上和第⼀趟是⼀样的也就意味着反复调⽤同⼀个函数存在即快速排序的过程中蕴含了递归思想这也是分治的⼀个佐证但是我们也可以有更清晰的解释且看下图⾸先根据原始数组 [1,8,3,9,4,5,4,7] 将数组划分为⼩于等于 7 的数组 [1,3,4,5,4] 和[8,9] 然后将 [1,3,4,5,4] 根据 4 划分为 [1,3,4] 和 [5] 将 [1,3,4] 根据 4 划分为[1,3] 将 [1,3] 根据 3 划分为 [1] 将 [8,9] 根据 9 划分为 [8] 这个过程不就是⼆分吗 (这里我们选择最后一个元素作为 pivot)的确如此只不过对于这个数组⽽⾔选择最末尾的元素作为 pivot 得到的树的⾼度并不是我们期望的logn log8 3 ⽽是 4说到这⾥我们顺带说⼀下快速排序的缺点对于⼀个有序数组 [1,3,4,4,5,7,8,9] ⽽⾔如果每次选择最后⼀个元素作为 pivot 就会得到下⾯⼀幅图⽽这时树的⾼度变成了n 也就意味着快速排序退化成了⼀颗单链这不是我们希望看到的。但是我们每⼀次选择最中间的元素作为 pivot ⼜会怎么样呢如果将数组 [1,8,3,9,4,5,4,7] 重新调整顺序使得快速排序的的分治过程如上图所示看着图就能写出来了当然答案可能有很多个最简单的⼀个就是 [1,4,3,5,8,9,7,4]5. 复杂度分析快速排序的时间通常表示为T(n) T(k) T(n - k 1) n其中 T(k) 和 T(n - k 1) 分别表示递归调⽤⽽最后⼀项n表示 将最后⼀个元素作为pivot进⾏划分 的处理过程k 表示⽐ pivot ⼩的元素的数⽬⽽快速排序的时间复杂度取决于输⼊的数组和划分策略所以需要从三个⽅⾯分析5.1 最坏情况我们每⼀次选择最⼤的元素或者最⼩的元素作为 pivot选择做末尾的元素作为 pivot最坏情况就是输⼊的待排序数组为有序数组以升序为例此时 k n - 1 那么T(n) T(n - 1) T(0) n ,即T(n) T(n-1)n所以最坏情况下的时间复杂度为O(n^2) 量级下面来个例子设对有序数组 [1,3,4,4,5,7,8,9] 进⾏快速排序每次选择最末尾的元素作为 pivot那么就会得到下图所示的情况也就说需要选择 n个 pivot并且以每⼀个 pivot 进⾏划分需要O(n)的时间那么总的时间就是O(n^2)量级5.2 最好情况当划分过程中每⼀次都能选择最中间的元素作为基准 pivot 那么快速排序的时间复杂度就等于T(n) T(n/2)T(n/2)n其中T(n)表示快速排序的时间复杂度T(n/2) 表示划分出的两个⼦数组排好序所⽤的时间 n表示 将最后⼀个元素作为pivot进⾏划分 函数的执⾏时间根据主定理Master Theorem快速排序最好情况下的时间复杂度为 O(nlogn).当然我们也可以换⼀个⻆度来算⽐如对数组 [1,8,3,9,4,5,4,7] ⽽⾔我们希望得到的是下⾯⼀幅图这个树的⾼度就是 O(logn)也就是选择 pivot 需要O(logn) 次⽽根据每⼀个 pivot 我们需要 O(n)的时间执⾏划分函数所以总的时间复杂度为O(nlogn)量级5.3 平均情况对于平均时间复杂度分析⽽⾔我们需要考虑数组的所有可能的排列并计算出对每⼀个排列所需要的时间然后求平均但是实在太复杂了。我们可以考虑⼀个⼀般的假设⽐如对于⼀个数组⽽⾔ n/10的元素每次⽐选择的 pivot ⼩⽽ 9n/10的元素⽐ pivot ⼤那么快速排序的时间复杂为T(n) T(n/10) T(9n/10) n.根据主定理快速排序的时间复杂度依旧是 O(nlogn), 也就意味着只要只要每⼀次不是选择最⼤或者最⼩的元素作为 pivot 时间复杂度都在O(nlogn) 量级快速排序的平均时间复杂度为O(nlogn)量级6. 稳定性分析快速排序是不稳定的我们把双边循环那里的图稍微往下画一点 只用右边那一部分到这其实就可以了两个49的位置发生了变化就说明快速排序是不稳定的了7. 测试函数这些函数也是之前写的排序算法里用到的在前面的排序那里都提到过 看懂即可typedefintkeyType;typedefstruct{keyType key;// 查找表中每个数据元素的关键值void*data;// 数据的其他区域}Element;typedefstruct{Element*data;// 存放查找表中数据元素的首地址intlength;// 查找表的元素个数}SortTable;enumsortStatus{success,failed};voidswapElement(Element*a,Element*b);// 交换元素a和元素bSortTable*generateRandomArray(intn,intlow,inthigh);// 产生随机数范围[low,high]SortTable*generateLinearArray(intn,intswapTimes);// 参数顺序空间随机交换swapTimes次 //轻微乱序 整体接近有序SortTable*copySortTable(SortTable*old);// 拷贝和old一样值的排序表voidreleaseSortTable(SortTable*table);// 排序算法函数的别名typedefvoid(*sortHandler)(SortTable*);// 测试sortName的排序算法voidtestSort(constchar*sortName,sortHandler sort,SortTable*table);/* 交换a和b的元素值 */voidswapElement(Element*a,Element*b){Element tmp;memcpy(tmp,a,sizeof(Element));memcpy(a,b,sizeof(Element));memcpy(b,tmp,sizeof(Element));}/* 产生n个随机数的排序表值的范围是[low, high] */SortTable*generateRandomArray(intn,intlow,inthigh){SortTable*tablemalloc(sizeof(SortTable));if(tableNULL){fprintf(stderr,sort table malloc failed!\n);returnNULL;}table-lengthn;table-data(Element*)malloc(sizeof(Element)*n);if(table-dataNULL){fprintf(stderr,element malloc failed!\n);free(table);returnNULL;}srand(time(NULL)1);for(inti0;in;i){table-data[i].key(rand()%(high-low1))low;table-data[i].dataNULL;}returntable;}/* 产生n个随机交换swapTimes次的有序顺序表 *///轻微乱序 整体接近有序SortTable*generateLinearArray(intn,intswapTimes){SortTable*tablemalloc(sizeof(SortTable));if(tableNULL){fprintf(stderr,sort table malloc failed!\n);returnNULL;}table-datamalloc(sizeof(Element)*n);if(table-dataNULL){fprintf(stderr,data malloc failed!\n);free(table);returnNULL;}table-lengthn;for(inti0;in;i){table-data[i].keyi;table-data[i].dataNULL;}// 在已经有序的排序表中交换swapTimes次srand(time(NULL)2);for(inti0;iswapTimes;i){intpos1rand()%n;intpos2rand()%n;swapElement(table-data[pos1],table-data[pos2]);}returntable;}/* 拷贝一个排序表使用同样的数据进行不同排序算法的测试 */SortTable*copySortTable(SortTable*old){SortTable*table(SortTable*)malloc(sizeof(SortTable));table-lengthold-length;table-datamalloc(sizeof(Element)*old-length);for(inti0;iold-length;i){table-data[i].keyold-data[i].key;table-data[i].dataold-data[i].data;}returntable;}/* 释放table */voidreleaseSortTable(SortTable*table){if(table){if(table-data){free(table-data);}free(table);}}// 检查排序表里的数据是否是从小到大排序staticenumsortStatuscheckData(constSortTable*table){for(inti0;itable-length-1;i){if(table-data[i].keytable-data[i1].key){printf(Check Sort Data Failed: %d : %d\n,table-data[i].key,table-data[i1].key);returnfailed;}}returnsuccess;}/* 测试sortName的排序算法算法通过sort传递函数名数据以table传入 */voidtestSort(constchar*sortName,sortHandler sort,SortTable*table){clock_tstartclock();sort(table);clock_tendclock();if(checkData(table)failed){printf(%s failed!\n,sortName);return;}printf(%s cost time: %fs.\n,sortName,(double)(end-start)/CLOCKS_PER_SEC);}8. 头文件部分//快排//双边循环法voidquickSortV1(SortTable*table);//单边循环法voidquickSortV2(SortTable*table);9. 实现9.1 双边循环法staticintpartitionDouble(SortTable*table,intstartIndex,intendIndex){//犄点 左指针 右指针intpivotstartIndex;intleftqidian startIndex;intrightendIndex;//随机将startIndex和后续的一个随机索引指向的元素进行交换while(left!right){//right指针的值大于pivot指针的while(leftrighttable-data[right].keytable-data[pivot].key){right--;}//left指针的值小于pivot指针的while(leftrighttable-data[left].keytable-data[pivot].key){left;}/*执行到这right指针指向的元素小于pivot指向的元素 left指针的指向的元素大于pivot指向的元素 交换left指针和right指针指向的元素*/if(leftright){swapElement(table-data[right],table-data[left]);}}//while 循环出来 left和right指向同一个位置 交换pivot位置和left(right)位置的值swapElement(table-data[pivot],table-data[left]);//返回正确的pivot的位置returnleft;}//用递归思想实现[start,end]区间的排序staticvoidquickSort1(SortTable*table,intstartIndex,intendIndex){if(startIndexendIndex){return;}//找到犄点intpivotpartitionDouble(table,startIndex,endIndex);//递归调用//左quickSort1(table,startIndex,pivot-1);//右quickSort1(table,pivot1,endIndex);}voidquickSortV1(SortTable*table){//递归调用quickSort1(table,0,table-length-1);//用的闭区间}9.2 单边循环法/*这个注释就不写了 其实看懂上面我们画的图这个很好理解的*/staticintpartitionSingle(SortTable*table,intstartIndex,intendIndex){keyType tmpValuetable-data[startIndex].key;intmarkstartIndex;for(intistartIndex1;iendIndex;i){if(table-data[i].keytmpValue){mark;swapElement(table-data[i],table-data[mark]);}}swapElement(table-data[startIndex],table-data[mark]);returnmark;}staticvoidquickSort2(SortTable*table,intstartIndex,intendIndex){if(startIndexendIndex){return;}intpivotpartitionSingle(table,startIndex,endIndex);quickSort2(table,startIndex,pivot-1);quickSort2(table,pivot1,endIndex);}voidquickSortV2(SortTable*table){quickSort2(table,0,table-length-1);}10.测试案例main函数voidtest03(){intn10000;// table1: n个随机数的排序表值的范围是[0, 5000]// table2: 拷贝table1中的内容// table3: 拷贝table1中的内容SortTable*table1generateRandomArray(n,0,05000);SortTable*table2copySortTable(table1);SortTable*table3copySortTable(table1);testSort(bubbleSortV3,bubbleSortV3,table1);testSort(Quick SortV1,quickSortV1,table2);testSort(Quick SortV2,quickSortV2,table3);releaseSortTable(table1);releaseSortTable(table2);}输出结果bubbleSortV3 cost time:0.443000s.Quick SortV1 cost time:0.001000s.Quick SortV2 cost time:0.002000s.多次测试所得耗时数值不会完全相同 会受很多因素影响这里就贴个三组数据感兴趣可以自己测试下嘻嘻嘻嘻快速排序部分到此结束堆排序 静候更新(有错误欢迎指出) (疑问也是)❤️❤️持续更新中…