详解快速排序
详解快速排序，使用 TypeScript 实现迭代版本的快速排序。
快速排序的原理
快速排序（Quicksort）是一种高效的排序算法，是由英国计算机科学家霍尔所发明。快速排序基于分治策略，按照以下步骤操作：
- 选择主元：从待排序的数组中选取一个元素，称为主元（pivot）。主元的选择策略有多种，如随机选择、选择第一个元素、最后一个元素、或者使用“三数取中”等方法。
- 划分：重新排列数组，使得所有小于主元的元素都在主元之前，所有大于主元的元素都在主元之后（与主元相等的值可以在任一端）。这个操作完成后，主元就处在数组的中间位置，这个过程叫做划分操作。
- 递归排序子序列：递归地将小于主元的元素和大于主元的元素进行快速排序。
以下是快速排序的伪代码：
1function quicksort(array)
2 if length(array) < 2
3 return array // 基准条件：空数组或者只有一个元素的数组是有序的
4 else
5 pivot := choose_pivot(array) // 选择主元
6 less := [element for element in array if element < pivot] // 小于主元的元素
7 equal := [element for element in array if element = pivot] // 等于主元的元素
8 greater := [element for element in array if element > pivot] // 大于主元的元素
9 return quicksort(less) + equal + quicksort(greater) // 将所有元素串联起来这个算法的时间复杂度在最好情况和平均情况下是O(N log N)，在最差情况下是O(N^2)。然而，通过合理选择主元，最差情况可以大幅度地减少出现的可能性。
需要注意的是，由于快速排序是一种原地排序算法，因此在实际实现时，通常会使用交换操作直接在原数组上进行操作，而不会创建新的数组来存储小于主元和大于主元的元素。这样可以提高空间效率，使得算法的空间复杂度达到O(log N)，这也是快速排序被广泛使用的一个重要原因。
主元策略
在快速排序算法中，选择主元（pivot）的策略对于算法的性能有着重要影响。理想的主元应该能将待排序数组大致等分为两部分，从而保证算法的时间复杂度接近于最优的O(N log N)。以下是两种常见的主元选择策略：
- 随机主元：在这个策略中，主元是从待排序数组中随机选择的。这可以大大降低算法性能退化到O(N^2)的可能性，因为即使输入数组是部分或完全有序的，也很少有可能每次都选到最坏的主元。随机选择主元的方法平均情况下的时间复杂度仍然为O(N log N)，并且对于大多数输入，其性能都比较良好。
- 三数取中：在这个策略中，我们选择首元素、中间元素和尾元素这三个元素的中值作为主元。这是一种折衷的策略，旨在避免在已排序或近似排序的数组上选择到极端的主元。相比于随机主元，三数取中的方法在已排序或近似排序的输入上表现更优，因为它更有可能选择到接近中位数的主元。然而，对于随机输入，其性能可能不如随机选择主元。
需要注意的是，无论选择哪种策略，都无法保证在所有情况下都选择到最优的主元。因此，在实践中，我们通常会根据待排序数组的具体特性以及性能需求来选择合适的策略。
一般我们遇到的写法 logN 是以多少为底的？
https://math.stackexchange.com/questions/293783/when-log-is-written-without-a-base-is-the-equation-normally-referring-to-log-ba
log(𝑥) refers to log2(𝑥) in computer science and information theory.
log(𝑥) refers to log𝑒(𝑥) or the natural logrithm in mathematical analysis, physics, chemistry, statistics, economics, and some engineering fields.
log(𝑥) refers to log10(𝑥) in various engineering fields, logarithm tables, and handheld calculators.
在计算机科学和工程中，若未特别注明，通常"logN"默认为以2为底的对数。然而，在数学和一些其他领域，"logN"常常表示以10为底的对数。而在自然科学中，"logN"经常表示以自然对数（以e为底）的对数。这主要取决于上下文和学科的约定。
如要明确表示，我们常常使用下标来注明对数的底数，例如"log₂N"表示以2为底的对数，"log₁₀N"表示以10为底的对数，而"lnN"或"logeN"表示以自然数e为底的对数。
TypeScript 实现迭代版本的快速排序
1/* This function takes last element as pivot,
2 places the pivot element at its correct
3 position in sorted array, and places all
4 smaller (smaller than pivot) to left of
5 pivot and all greater elements to right
6 of pivot */
7function partition(arr: number[], low: number, high: number) {
8 let temp;
9 const pivot = arr[high];
10
11 // index of smaller element
12 let i = low - 1;
13 for (let j = low; j <= high - 1; j++) {
14 // If current element is smaller
15 // than or equal to pivot
16 if (arr[j] <= pivot) {
17 i++;
18
19 // swap arr[i] and arr[j]
20 temp = arr[i];
21 arr[i] = arr[j];
22 arr[j] = temp;
23 }
24 }
25
26 // swap arr[i+1] and arr[high]
27 // (or pivot)
28
29 temp = arr[i + 1];
30 arr[i + 1] = arr[high];
31 arr[high] = temp;
32
33 return i + 1;
34}
35
36// Iterative Quick Sort
37export const QuickSortIterative = (arr: number[]) => {
38 let l = 0;
39 let h = arr.length - 1;
40 // Create an auxiliary stack
41 const stack = new Array(h - l + 1);
42 stack.fill(0);
43
44 // initialize top of stack
45 let top = -1;
46
47 // push initial values of l and h to
48 // stack
49 stack[++top] = l;
50 stack[++top] = h;
51
52 // Keep popping from stack while
53 // is not empty
54 while (top >= 0) {
55 // Pop h and l
56 h = stack[top--];
57 l = stack[top--];
58
59 // Set pivot element at its
60 // correct position in
61 // sorted array
62 const p = partition(arr, l, h);
63
64 // If there are elements on
65 // left side of pivot, then
66 // push left side to stack
67 if (p - 1 > l) {
68 stack[++top] = l;
69 stack[++top] = p - 1;
70 }
71
72 // If there are elements on
73 // right side of pivot, then
74 // push right side to stack
75 if (p + 1 < h) {
76 stack[++top] = p + 1;
77 stack[++top] = h;
78 }
79 }
80 return arr;
81};