快速排序记录

第一个能用的版本

void Sort::_QSort(int start, int end) {
    if(start>=end) return;
    int key = sorted[start];
    int keyIndex = start;
    int i = start, j = end;
    while(i<j) {
        for(;sorted[j]>=key && i<j;j--);
        if(sorted[j]<key) {
            swap(sorted[keyIndex], sorted[j]);
            keyIndex = j;
        }
        for(;sorted[i]<=key && i<j;i++);
        if(sorted[i]>key) {
            swap(sorted[keyIndex], sorted[i]);
            keyIndex = i;
        }
    }
    _QSort(start, keyIndex-1);
    _QSort(keyIndex+1, end);
}

void Sort::QuickSort() {
    _QSort(0, sorted.size()-1);
}

void Sort::_QSort(int start, int end) {
    if(start>=end) return;
    int key = sorted[start];
    int keyIndex = start;
    int i = start, j = end;
    while(i<j) {
        for(;sorted[j]>=key && i<j;j--);
        swap(sorted[keyIndex], sorted[j]);
        keyIndex = j;
        for(;sorted[i]<=key && i<j;i++);
        swap(sorted[keyIndex], sorted[i]);
        keyIndex = i;
    }
    _QSort(i, keyIndex-1);
    _QSort(keyIndex+1, j);
}