# 快速排序 (Quick Sort) 说到快排，自然会想起它解决问题的思路——分治思想。它的主要实现也很好的提现了这个思想。 ```cpp /** * 快排 * @param int* arr 操作数组 * @param int low 左侧index * @param int high 右侧index * @return */ void qsort(int *arr, int low, int high) { // 中止条件 if (low >= high) { return; } int i = partition(arr, low, high); // 左侧快排 qsort(arr, low, i); // 右侧快排 qsort(arr, i + 1, high); } ``` 本次对其中的分区函数 `partition` 分析 # partition 到底做了什么 在 **一次** 执行周期内，将选定的 **一个** 数字（或者其他 Object）移动到在 `low`、`high` 范围内的合适位置，并返回移动后的位置。（索引号） 特别的，本例是固定选择位于 `low` 的数字（Object）移动。 # partition 的意义 经过一次执行后，原本位于左侧的数字（Object）已经移动到合适的位置上。那么，之后就以那个位置为分割点，分别对左侧、右侧部分重新执行 partition，如此递归直到所有数字（Object）有序为止。 简单来说就是：分区函数就是为了要找到分区点，而这个分区点必须是有意义的。（在此案例是，分区点的意义是该数字已经在合适的位置上了） # 思路 1. 随意取一个比较值 `A` ，本例是取第一个 2. 将比 `A` 小的元素放在 `A` 的左侧（低位），比 `A` 大的元素放在 `A` 的右侧 # 展开 2 的思路 1. 开始时，`low` 指向第一位（即最左边），`high` 指向最后一位（即最右边）。此时恒有 `low` < `high`。 2. 判断：`high` 指向的数值比 `A` 大（或者相等）吗？ 3. 如果 `2` 为真，`high` 自减（即右指针向左靠近，或者也可以说向 `low` 靠近）。 4. 重复`2`, `3`，直到 `2` 为假，或者 `high` 不再位于 `low` 的左侧。如果是后者，则有 `low` == `high` 5. 将 `low` （低位）的值用此刻 `high` 指向的值写入。 # 为什么要执行 5 ？ 在执行到 `5` 时，存在以下可能的两种情况 1. `high` 指向的数值在 `high` **向左靠近**期间内恒大于 `A`，那么在到达 `5` 的时刻，`high`=`low`，`5` 的操作相当于用 `low` 的值赋值到 `low` 上 2. `high` 指向的数值在某个时刻小于 `A`，此时 `5` 的操作相当于把这个小于 `A` 的数值复制 `low` 指向的位置 如果是情况 `1`，那么 `partition` 函数也就到此结束了，需要重新取一个不同的 `low` （低位）重新执行 `partition` # 继续 2 的思路 6. 判断：`low` 指向的数值比 `A` 小（或者相等）吗？ > 此刻，因为 `low` 指向的数值在 `5` 时已经由小于（或等于）`A`，因此 `6` 恒为真 7. 如果 `6` 为真，`low` 自增（即左指针向右靠近，或者也可以说向 `heigh` 靠近）。 8. 重复 `6`, `7`, 直到 `6` 为假，或者 `low` 不再位于 `high` 的左侧。如果是后者，则有 `low` == `high` 9. 将 `high` （高位）的值用此刻 `low` 指向的值写入。 ```cpp int partion(int *arr, int low, int high) { int pivot = arr[low]; while (low < high) { while (low < high && arr[high] >= pivot) { --high; } arr[low] = arr[high]; while (low < high && arr[low] <= pivot) { ++low; } arr[high] = arr[low]; } arr[low] = pivot; return low; } ``` # 参考 [快速排序partition过程常见的两种写法+快速排序非递归实现 - tenos - 博客园](https://www.cnblogs.com/TenosDoIt/p/3665038.html)