快速排序的迭代实现
Published by powerfulyang on Feb 26, 2023
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};