快速排序 原创 排序算法 2021年7月14日 07:00 夏至未至 1064 当前内容 3570 字，在路上，马上到，马上到 快速排序，纵观各类技术博客，关于快速排序，方法很多，各有千秋，但是，我拙见： 快速排序需要用递归，二分，分治的思想去操作，那么在这其中，就需要找一个基准，通过这个基准，把序列分开，达到可以用分治的思想取解决的目的； 能看到这里的，基本对快排都有个了解，不多说，盗了几个图看看，更方便记忆：  动态图只能理解个意思，主要还是理解第一张图，说的很明白了，结合代码，分析： ```cpp #pragma once //方法一： void swap(int* a, int left, int right) { int temp = a[left]; a[left] = a[right]; a[right] = temp; } int partitionNumOne(int* a, int left, int right) { //The selected benchmark example :left int markKey = a[left]; int mark = left; while (left < right) { while (left < right && a[right] >= markKey) right--; while (left < right && a[left] <= markKey) left++; swap(a, left, right); } swap(a,mark,left); return left; //or right because left == right } void QuickSortNumOne(int* a, int left, int right) { if (left >= right) return; int position = partitionNumOne(a, left, right); QuickSortNumOne(a, left, position - 1); QuickSortNumOne(a, position + 1, right); } void SortNumOne(int* a,int size) { assert(a); QuickSortNumOne(a, 0, size - 1); } //方法二： int part(int* a, int left, int right) { int markKey = a[left]; while (left < right) { while (left < right && a[right] >= markKey) right--; a[left] = a[right]; //小的直接覆盖左边 while (left < right && a[left] <= markKey) left++; a[right] = a[left]; } a[left] = markKey; return left; } void QuickSortNumTwo(int* a, int left, int right) { if (left >= right) return; int pos = part(a,left,right); QuickSortNumTwo(a,left,pos-1); QuickSortNumTwo(a,pos+1,right); } void SortNumTwo(int* a, int size) { assert(a); QuickSortNumTwo(a,0,size-1); } //方法三： //计算中间那个位置 一边都大于他 一边都小于他 int Partition(int *a, int left, int right) { int key = a[right]; int begin = left; int end = right - 1; while (begin < end) { //key是自己选 while (a[begin] < key && begin < end) //也就是说 key左边的都比key小 右边的都比key大 { ++begin; } while (a[end] > key && end > begin)//处理右边 { --end; } //但凡上边任何一个循环跳出来，都是因为遇到条件 下面判断 if (begin < end) { swap(a[begin], a[end]); } } if (a[begin] < key) { return right; } else { swap(a[begin], a[right]); return begin; } } void QuickSortOne(int *a, int left, int right) { assert(a); if (left <= right) { int tmp = Partition(a, left, right); //单趟排序 QuickSortOne(a, left, tmp - 1); QuickSortOne(a, tmp + 1, right); } } //方法四： void QsortMedianOfThree(int* a, int low, int high) { if (low >= high) return; //递归出口 PartitionMedianOfThree(a, low, high); //三数取中 int partition = Partition(a, low, high); //将 >= x 的元素交换到右边区域，将 <= x 的元素交换到左边区域 QsortMedianOfThree(a, low, partition - 1); QsortMedianOfThree(a, partition + 1, high); } // 三数取中确定基准元，将确定好的基准元与第一个数交换，无返回值 void PartitionMedianOfThree(int* a, int low, int high) { int mid = low + (high + -low) / 2; if (a[mid] > a[high]) { swap(a, mid, high); } if (a[low] > a[high]) { swap(a, low, high); } if (a[mid] > a[low]) { wap(a, mid, low); } //将中间大小的数与第一个数交换 } ``` 三种方法，都测试通过，前两种都是按图中方案写的代码，第二种方法优化了一点，不同第一种方法的地方是，第二种不用交换，直接覆盖，节省了时间； 之后：快速排序是不稳定的，其时间平均时间复杂度是O(nlgn)。 附一张图：  本文标题： 快速排序 本文作者： 夏至未至 发布时间： 2021年7月14日 07:00 最近更新： 2021年7月28日 07:03 原文链接： 许可协议： 署名-非商业性-禁止演绎 4.0 国际(CC BY-NC-ND 4.0) 请按协议转载并保留原文链接及作者 上一个 浅显易懂的桶排序 下一个 归并排序 当前文章评论暂未开放,请移步至留言处留言。
