愿你坚持不懈,努力进步,进阶成自己理想的人

—— 2017.09, 写给3年后的自己

快速排序算法

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

void swap(int& a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

int rand(int a, int b) {
    srand((unsigned)time(NULL));
    return a + rand() % (b-a+1);
}

int partition(int arr[], int length, int start, int end) {
    if(arr == NULL || length <= 0 || start < 0 || end >= length) throw "Invalid partition arguments";

    int index = rand(start, end);
    swap(arr[end], arr[index]);

    int small = start-1; // 前small个元素都比基准元素小
    for(index = start; index < end; ++index) {
        if(arr[index] < arr[end]) {
            if(++small != index) swap(arr[index], arr[small]);
        }
    }

    ++small;
    swap(arr[small], arr[end]);

    return small;
}

void qsort(int arr[], int length, int start, int end) {
    if(start == end) return;

    int index = partition(arr, length, start, end);

    // 进行左排序
    if(start < index) qsort(arr, length, start, index-1);
    // 进行右排序
    if(end > index) qsort(arr, length, index+1, end);
}

int main() {
    int arr[] = {3, 6, 2, 6, 7, 8};
    int length = sizeof(arr)/sizeof(int);
    qsort(arr, length, 0, length - 1);

    for(int i=0; i<length; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}