快速排序的迭代实现

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};