### 快速排序的递归和非递归实现

#include <iostream>

using namespace std;

int partition(int arr[], int low, int high) {
/**
* This function takes last element as pivot,
* places the pivot element at its correct position
* in sorted  array, and places all smaller
* (smaller than pivot) to left of pivot and
* all greater elements to right of pivot
*/
int small_index = low - 1;
// If current element is smaller than pivot
for (int i = low; i < high; i++)
if (arr[high] > arr[i])
swap(arr[++small_index], arr[i]); // increment index of smaller element and swap
swap(arr[++small_index], arr[high]);
return small_index;
}

void quickSortRecursive(int arr[], int low, int high) {
if (low < high) {
/* pi is partitioning index, arr[p] is now
at right place */
int p = partition(arr, low, high);
// Separately sort elements before
// partition and after partition
quickSortRecursive(arr, low, p - 1);
quickSortRecursive(arr, p + 1, high);
}
}

void quickSort(int arr[], int low, int high) {
// Create an auxiliary stack
int stack[high - low + 1];

// initialize top of stack
int top = -1;

// push initial values of l and h to stack
stack[++top] = low;
stack[++top] = high;

// Keep popping from stack while is not empty
while (top >= 0) {
// Pop high and low
high = stack[top--];
low = stack[top--];

// Set pivot element at its correct position in sorted array
int p = partition(arr, low, high);

// If there are elements on left side of pivot, then push left side to stack
if (p - 1 > low) {
stack[++top] = low;
stack[++top] = p - 1;
}

// If there are elements on right side of pivot, then push right side to stack
if (p + 1 < high) {
stack[++top] = p + 1;
stack[++top] = high;
}
}
}

int main() {
int arr[] = {3, 2, 1, 4, 5, 6, 7, 0, 9, 8};
quickSort(arr, 0, 9);
for (int i:arr) {
cout << i << endl;
}
return 0;
}