快速排序
1. 快速排序的思想
快速排序是一种分治的排序算法，是对于冒泡排序的改进算法，在C语言标准库中的函数qsort()的实现就是快速排序。（下述快速排序都是最后要求值按从小到大排序）
快速排序的核心思想在于：
每次都选择主元，然后利用主元进行划分，使得左边的元素都小于主元，右边的元素都大于主元，然后对左右两边的元素进行相同原理的递归排序。
快速排序的难点在于：
- 如何选择主元
- 如何进行划分
- 如何进行递归排序
- 边界处理
2. 快速排序的实现
2.1 《算法导论》中的实现
普通的快速排序：
PARTITION(A, p, r) // 划分，p为数组的第一个元素，r为数组的最后一个元素
x = A[r] // 选取最后一个元素作为主元
i = p - 1 // i为指针，指向第一个元素的前一个元素
for j = p to r - 1 // j为指针，指向第一个元素，到倒数第二个元素，因为最后一个元素是主元
if A[j] <= x // 如果j当前元素小于主元
i = i + 1 // i指针向后移动一位
exchange A[i] with A[j] // 交换A[i]与A[j]
exchange A[i + 1] with A[r] //
return i + 1
QUICKSORT(A, p, r) // p为数组的第一个元素，r为数组的最后一个元素
if p < r // 当划分到只有一个元素的时候，不需要进行排序
q = PARTITION(A, p, r) // 划分，q为主元的位置
QUICKSORT(A, p, q - 1) // 对左边的元素进行排序
QUICKSORT(A, q + 1, r) // 对右边的元素进行排序
上面的这段注释是我自己加
随机化的快速排序：
RANDOMIZED-PARTITION(A, p, r)
i = RANDOM(p, r) // 随机选取一个元素
exchange A[r] with A[i] // 交换A[r]与A[i]，这样就可以将随机选取的元素作为主元
return PARTITION(A, p, r) // PARTITION是上面的划分函数
RANDOMIZED-QUICKSORT(A, p, r)
if p < r
q = RANDOMIZED-PARTITION(A, p, r)
RANDOMIZED-QUICKSORT(A, p, q - 1)
RANDOMIZED-QUICKSORT(A, q + 1, r)
2.2 陈越老师的《数据结构（第2版）》中的实现
ElementType Median3(ElementType A[], int Left, int Right)
{
int Center = (Left + Right) / 2;
if (A[Left] > A[Center])
Swap(&A[Left], &A[Center]);
if (A[Left] > A[Right])
Swap(&A[Left], &A[Right]);
if (A[Center] > A[Right])
Swap(&A[Center], &A[Right]);
/* 此时A[Left] <= A[Center] <= A[Right] */
Swap(&A[Center], &A[Right - 1]); /* 将基准Pivot藏到右边*/
return A[Right - 1]; /* 返回基准Pivot */
}
void Qsort(ElementType A[], int Left, int Right)
{
/* 核心递归函数 */
int Pivot, Cutoff, Low, High;
if (Cutoff <= Right - Left) /* 如果序列元素充分多，进入快排 */
{
Pivot = Median3(A, Left, Right); /* 选基准 */
Low = Left;
High = Right - 1;
while (1) /*将序列中比基准小的移到基准左边，大的移到右边*/
{
while (A[++Low] < Pivot)
;
while (A[--High] > Pivot)
;
if (Low < High)
Swap(&A[Low], &A[High]);
else
break;
}
Swap(&A[Low], &A[Right - 1]); /* 将基准换到正确的位置 */
Qsort(A, Left, Low - 1); /* 递归解决左边 */
Qsort(A, Low + 1, Right); /* 递归解决右边 */
}
else
InsertionSort(A + Left, Right - Left + 1); /* 元素太少，用简单排序 */
}
void QuickSort(ElementType A[], int N)
{
/* 统一接口 */
Qsort(A, 0, N - 1);
}
2.3 严蔚敏老师的《数据结构（C语言版）》中的实现
int Partition(SqList &L, int low, int high)
{
// 交换顺序表L中子表r[low..high]的记录，枢轴记录到位，并返回其所在位置
// 此时在它之前（后）的记录均不大（小）于它
L.r[0] = L.r[low]; // 用子表的第一个记录作枢轴记录
int pivotkey = L.r[low].key; // 枢轴记录关键字
while (low < high) // 从表的两端交替地向中间扫描
{
while (low < high && L.r[high].key >= pivotkey)
--high;
L.r[low] = L.r[high]; // 将比枢轴记录小的记录移到低端
while (low < high && L.r[low].key <= pivotkey)
++low;
L.r[high] = L.r[low]; // 将比枢轴记录大的记录移到高端
}
L.r[low] = L.r[0]; // 枢轴记录到位
return low; // 返回枢轴位置
}
void QSort(SqList &L, int low, int high)
{
// 对顺序表L中的子序列L.r[low..high]作快速排序
if (low < high) // 长度大于1
{
int pivotloc = Partition(L, low, high); // 将L.r[low..high]一分为二，算出枢轴值pivotloc
QSort(L, low, pivotloc - 1); // 对低子表递归排序, pivotloc是枢轴位置
QSort(L, pivotloc + 1, high); // 对高子表递归排序
}
}
void QuickSort(SqList &L)
{
// 对顺序表L作快速排序
QSort(L, 1, L.length);
}
2.4 个人常用的模版
void ExChange(int *a, int *b) // 交换两个数
{
int t = *a;
*a = *b;
*b = t;
}
int Partition(int *a, int l, int h) // 划分函数
{
int i = l - 1, j = h + 1; // i, j 为左右指针, 由于后面使用do while循环，首先会对i，j进行运算，所以i, j的初始值要分别为l - 1, h + 1
int x = a[(l + h) / 2]; // 选取基准数，这里选取中间数，也可以随机选取,用来应对加强数据
while(i < j)
{
do i++; while(a[i] < x); // 从左往右找到第一个大于等于基准数的数
do j--; while(a[j] > x); // 从右往左找到第一个小于等于基准数的数
if(i < j) ExChange(&a[i], &a[j]); // 交换两个数, 这个位置可以直接使用swap函数
}
return j;
}
void QuickSort(int *a, int l, int h) // 快速排序
{
if(l >= h) return; // 递归边界
int q = Partition(a, l, h); // 划分
QuickSort(a, l, q); // 递归左边
QuickSort(a, q + 1, h); // 递归右边
}
个人推荐上述代码，比较好记，但是可能难理解
3. 快速排序代码上的分析
有关于代码细节的分析，推荐这篇文章 《AcWing 785. 快速排序算法的证明与边界分析》，我个人记得快速排序的代码模版，就是来自这篇文章。
下面我关于我在学习快速排序的过程中，对于快速排序的一些理解。
在《算法导论》、陈越老师的《数据结构（第2版）》中，选取了最后一个元素作为主元。在严蔚敏老师的《数据结构（C语言版）》、《算法图解》、《算法（第4版）》中，选取的是第一个元素作为主元。因此，主元的选择是可以变化的，但是需要注意的是，在某些数据里，主元的选择直接影响了最后的程序的处理时间。比如785. 快速排序 - AcWing题库 里的数据就不能简单选取第一个元素作为主元，否则会超时。个人认为，主元的选择应该随机。
就我已给出的几组代码而言，在《算法导论》、陈越老师的《数据结构（第2版）》和严蔚敏老师的《数据结构（C语言版）中都是选取的一个主元，并在排序完成后主元不变。但是在 2.4 个人常用的模版 里给出的代码里选取的主元在本轮排序的最后可能出现主元变换的情况，但是这并不影响排序，因为主元划分数组是在本轮排序后进行，我们只需要保证最后我们挑出来的主元符合要求（即划分后，主元的左边都是小于主元的，主元的右边都是大于主元的）即可。
下面我摘抄一段《算法导论》中对于快速排序的完整描述：
快速排序的三步分治过程：
分解：数组 \(A[p...r]\) 被划分为两个（可能为空）的子数组 \(A[p...q-1]\) 和 \(A[q+1...r]\) ，使得 \(A[p...q-1]\) 中的每一个元素都小于等于 \(A[q]\) ，而 \(A[q]\) 也小于等于 \(A[q+1...r]\) 中的每个元素。其中，计算下标q也是划分过程的一部分。
解决：通过递归调用快速排序，对子数组 \(A[p...q-1]\) 和 \(A[q+1...r]\) 进行排序。
合并：因为子数组都是原址排序的，所以不需要合并操作：数组 \(A[p...r]\) 已经有序。
可以注意的是《算法导论》并没有规定主元的选取是固定的，或者有次序的。在我刚接触快速排序的时候认为，主元的选取应该是固定的，并且应该先选主元然后再进行排序。但是后来发现其实我们整个过程只需要保证最后主元的位置是正确的，而不需要保证主元的位置是固定的。因此，我们可以在排序的过程中，随机选取主元，然后将主元放到正确的位置上，这样就可以保证主元的位置是正确的，而不需要保证主元的位置是固定的。在算法实现适当的情况下，可以先进行适当排序，只要返回满足要求的主元的位置即可。比如 2.4 模版 中的代码，就是先进行了一次排序，然后返回了主元的位置，这样就可以保证主元的位置是正确的，而不需要保证主元的位置是固定的。