依次类推什么意思,依次类推和以此类推哪个正确

说明：因为array[i] > 基准值6，则需要将array[j] = array[i], 即将i索引处的值9 赋值到j索引指向的位置。

填上基准值

说明： i==j了，说明本轮结束了，将基准值回填，这样经过了一轮的比较，我们就得到了第一个元组的正确位置，通过6将整个集合分成了两个部分，一个是左边的子集，全部小于6，一个是右边的子集全部大于6，如下：

通过上图我们得到了 左边子集 基准元组 右边子集，然后我们分别对左边子集再执行类似的操作，右边子集再进行类似的操作，就完成了整个数组的排序。

左边子集的元素范围是 【 开始索引，i-1】 右边子集的范围是【i 1,结尾索引】

// 分区 int partion(int a[], int l, int r) { int tmp = a[l]; while (l < r) { // 从后对前判断元素是否大于基准值，大于则r 指针对前移动 while (a[r] > tmp && l < r) { r--; } // 小于则赋值给首个元素，即将值移动到前面 // 如果l==r 则相当于a[0] = a[0] 无影响 a[l] = a[r]; // 从前对后判断是否小于基准值，小于等于对后移动 while (a[l] <= tmp && l < r) { l ; } // 将值移动到后面 a[r] = a[l]; } a[r] = tmp; return r; } void qsort(int a[], int left, int right) { if (left < right) { int mid = partion(a, left, right); // 对前面的子集进行排序 qsort(a, left, mid - 1); // 对右边的子集进行排序 qsort(a, mid 1, right); } }

虽然代码没做任何其他优化，好处是便于理解也足够简单。

复杂度重点在于按照基准值的分区，其他的只是递归计算而已，因为分区的时候我们用的两个指针的技术条件是i == j,扫描了整个数组空间，所以分区函数的时间复杂度是O(n),所以总的时间复杂度为： O(n) = n T(L) T(R) 然后T(L)和T(R) 又可以做递归分解,我们按照树的形式将时间分解如下：

如上图所示，整个算法的耗时，就是每层耗时，而每层耗时的时间即是分区函数的时间:

第一层: n个元素，分区所占时间为n;

第二层:L子集分区时间为L，R子集分区时间为R，那第二层整体的分区所占时间为L R,而L R = n- 1 所以第二层耗时看作是n-1.

第三层:LL LR RL RR = L-1 R -1 即n-3， 依次类推： O(n) = n n-1 n-3 ....看这个是不是等差数列，不，别上当，再计算一层看看：

第四层：LLL LLR LRL LRR RLL RLR RRL RRR = LL -1 LR -1 RL-1 RR -1 = (LL LR)-2 (RL RR)-2 = L -1 -2 R-1 -2 = L R -6 = n - 7 看到了吧，这种树如果是完全二叉树，每层耗时递减得很快，完全二叉树的数量： 2的h次方（h为树高度）减去1，指数级别的增加；

完全二叉树的高度最低为log2n ，n为节点数，按照刚刚每次计算的耗时，如果n很大，每层接近耗时为n，则总耗时为树的高度* 每层耗时 = nlog2n，即时间复杂度为O(nlog2n)这是最好的情况，如果特殊情况，本身是倒序的，那么树就变成链表，就是nn最坏的时间复杂度为O(n^2)。

快速排序算法除了可以排序外，还可以方便找第k大的元素，因为我们每次快排都找到了第一个元组的正确位置index，如果我们要找的第k大元素的k 小于index，那么我们就在小于基准值的集合里面去继续找第k大元素，如果第k大元素大于index，那么第k大元素在大于基准值的集合去找，但是不是找第k元素了，而是找第k-index的元素，这样每次我们都能过滤掉一个集合，性能显然很快。

单边递归优化 分区后，继续对左右两边排序，我们可以把一边在本轮直接处理了，所以叫单边优化：

quick_sort(arr, l, x - 1); // 对左子集排序 quick_sort(arr, x 1 , r); // 对右子集排序

可以做成：

void quick_sort(int *arr, int l, int r) { while (l < r) { // 分区 int ind = partition(arr, l, r); // 对大于基准值的右子集正常调用递归函数 quick_sort(arr, ind 1, r); // 用本层处理左侧的排序 r = ind - 1; } return ; }

减少了递归的层次，提升了性能。

三点取中法 如果基准值选择得好，那么整个递归排序展开就是完全二叉树，性能最好，所以基准值选择很重要，有种优化是选择开头元素，结束元素，中间元素三个元素中，中间那个，当然上面的代码就不适用了，很大程度上避免选择基准值的问题。

分区函数优化 分区的时候我们每次只是将其中i处和j处的值其中一个赋值给另外一个，如果我们只要满足条件就做移动，直到i和j都不满足的时候，交换两者的值，减少赋值过程，这样性能更快。