快速排序 O(nlogn)

快速排序 调用方法 quickSort(a,0,n); θ(nlogn)

void quickSort (int a[], int low, int high) {
    if (high <= low ) {
        return;
    }

    int start = low;   // 哨兵
    int end = high;  // 哨兵
    int temp = a[low];  // 存基准数，这里以最左边的数位基准
    int t;          // 用于交换的临时变量

    while (start < end) {
       // 要先从右往左找（因为基准点在最左边）
        while (start < end && a[end] >= temp)
            end--;
        while (start < end && a[start] <= temp)
            start++;
        if (start < end) {    // 哨兵没有相遇
            t = a[start];
            a[start] = a[end];
            a[end] = t;
        }
    }

// 哨兵相遇(start == end)，将基准数temp归位
    a[low] = a[start];
    a[start] = temp;

    quickSort(a, low, start - 1);
    quickSort(a, start + 1, high);
}