快速排序C++实现

// Type your C++ code and click the "Run Code" button!
// Your code output will be shown on the left.
// Click on the "Show input" button to enter input data to be read (from stdin).

#include <iostream>
#include <algorithm>

using namespace std;

// print array  
void print_arr(int a[], int n) {  
    for(int i = 0; i < n; i++) cout<<a[i]<<" ";  
    cout<<endl;  
}  

int partition(int a[], int low, int high) {
    int pivot = a[low];
    while(low < high) {
        while(low < high && a[high] >= pivot) high --;
        a[low] = a[high];
        while(low < high && a[low] <= pivot) low ++;
        a[high] = a[low];
    }
    a[low] = pivot;
    return low;
}

void quick_sort(int a[], int l, int h) {
    if (l >= h) return;
    int pivot = partition(a, l, h);
    quick_sort(a, l, pivot-1);
    quick_sort(a, pivot+1, h);
}

// return the kth smallest item
/*
int quickSelect(int items[], int first, int last, int k) {
    int pivot = partition(items, first, last);
    if (k < pivot-first) {
        return quickSelect(items, first, pivot, k);
    } else if (k > pivot) {
        return quickSelect(items, pivot+1, last, k-pivot);
    } else {
        return items[k];
    }
}
*/

int main() {
    int a[] = {1, 3, 2, 4, 5, 6};
    
    print_arr(a, 6);
    quick_sort(a, 0, 5);
    print_arr(a, 6);
    
    return 0;
}