快速排序：
快速排序是另一个分而治之排序算法。
我们将看到，这种确定性的，非随机化的快速排序的版本可能在对手输入中具有O（N2）的很差的时间复杂度，之后再继续随机化的和可用的版本。
疑问：“确定的，非随机化的”指的是什么？指的是枢纽点的选取。
快速排序是分而治之的算法：
划分步骤：选择一个项目 p（称为枢轴点）然后将 a[i..j] 的项目分为三部分：a [i..m-1]，a [m] 和 a[m + 1..j]。 a [i..m-1]（可能为空）包含小于 p 的项目。 a [m] 是枢轴点 p，例如：指数 m 是已排序数组 a 的排序顺序中 p 的正确位置。 a [m + 1..j]（可能为空）包含大于或等于 p 的项目。 然后，递归地对这两部分进行排序。
解决步骤：不要惊讶......我们什么都不做！
如果您将其与归并排序进行比较，您会发现快速排序的 D＆C 步骤与归并排序完全相反。
D&C: devide & conquer, 分 and 治。
重要的子程序，O(N)分区：
我们首先讨论其最重要的子程序：O（N）分区，然后解析这个快速排序算法。
要分区 a[i..j]，我们首先选择 a[i] 作为枢纽 p。其余项目（即a [i + 1..j]）分为3个区域：
S1 = a [i + 1..m]其中项目 < p，
S2 = a [m + 1..k-1]其中项目 ≥ p，且
未知的= a [k..j]，其中项目尚未分配给 S1 或 S2。
讨论：为什么我们选择 p = a [i]？ 还有其他选择吗？
更难的讨论：始终在S2上放置 == p的项目是好的吗？
分区排序 - 继续：
最初，S1 和 S2 区域都是空的，即除了指定的枢轴点 p 之外的所有项目都在未知区域中。
然后，对于未知区域中的每个项目 a [k]，我们将 a[k] 与 p 进行比较, 并决定两种情况中的一个：
如果 a [k]≥p，则将 a[k] 放入 S2 或
否则，将 a[k] 放入 S1 中。
接下来的两张幻灯片将会详细阐述了这两种情况。
最后，我们交换a[i]和 a[m] 来将枢纽 p 放在 S1 和 S2 的中间。
分区排序 - 当a[k] >= p的情况：
分区排序 - 当a[k] < p的情况：
分区排序 - c++实现：
int partition(int a[], int i, int j) {
int p = a[i]; // p 是枢纽
int m = i; // S1 和 S2 一开始是空的
for (int k = i+1; k <= j; k++) { // 探索未知的区域
if (a[k] < p) { // case 2
m++;
swap(a[k], a[m]); // C++ STL algorithm std::swap
} // 注意：在情况1的时候我们什么不做: a[k] >= p
}
swap(a[i], a[m]); // 最后一步, 用a[m]交换枢纽
return m; // 返回枢纽的指数, 用于快速排序（Quick Sort）
}
快速排序c++实现：
void quickSort(int a[], int low, int high) {
if (low < high) {
int m = partition(a, low, high); // O(N)
// a[low..high] ~> a[low..m–1], pivot, a[m+1..high]
quickSort(a, low, m-1); // 递归地将左子阵列排序
// a[m] = pivot 在分区后就被排序好了
quickSort(a, m+1, high); // 然后将右子阵列排序
}
}
快速排序：第一部分 分析：
首先，我们分析跑一次分区的成本。
在内部分区（a，i，j）中，只有一个for循环遍历（j-i）次。 由于j可以和 N-1一样大，i 可以低至0，所以分区的时间复杂度是O（N）。
类似于归并排序分析，快速排序的时间复杂度取决于分区（a，i，j）被调用的次数。
快速排序：第三部分 分析：（第二部分，略）
在这种最坏情况的输入场景（最坏场景指的是已排序序列）中，会发生以下情况：
第一个分区需要O（N）时间，将a分成0,1，N-1个项目，然后向右递归。
第二个花费O（N-1）时间，将a分成0,1，N-2个项目，然后再次向右递归...
直到最后，第N个分区将a分成0,1,1项，并且Quick Sort递归停止。
这是经典的N +（N-1）+（N-2）+ ... + 1模式，它是O（N2），类似于本幻灯片中的分析......
快速排序：最好的情况（极少）：
当分区总是将数组分成两个相等的一半时，就会发生快速排序的最佳情况，如归并排序。
当发生这种情况时，递归的深度只有O（log N）。
由于每个级别进行O（N）比较，时间复杂度为O（N log N）。
代码：
int partition(int arr[], int low, int high) { int mid_data = 0, tmp_data = 0; int mid_index = 0, index = 0; mid_data = arr[low]; mid_index = low; printf("---------- call partition----------\n"); for (index = low + 1; index <= high; index++) { if (arr[index] < mid_data) { mid_index++; printf("[index:%2d<-->%2d], data: %2d<-->%2d\n", mid_index, index, arr[mid_index], arr[index]); tmp_data = arr[index]; arr[index] = arr[mid_index]; arr[mid_index] = tmp_data; } } printf("[index:%2d<-->%2d], data: %2d<-->%2d\n", low, mid_index, arr[low], arr[mid_index]); tmp_data = arr[mid_index]; arr[mid_index] = arr[low]; arr[low] = tmp_data; return mid_index; } void QuickSort(int arr[], int low, int high) { if (low < high) { int mid = partition(arr, low, high); QuickSort(arr, low, mid-1); QuickSort(arr, mid+1, high); } return; }
