归并排序&快速排序

[wakisun]

归并排序

void merge(vector<int> &v, int l1, int r1, int l2, int r2) {
    vector<int> temp;
    int i = l1, j = l2;
    while(i <= r1 && j <= r2) {
        if (v[i] <= v[j]) {
            temp.push_back(v[i++]);
        } else {
            temp.push_back(v[j++]);
        }
    }
    
    while(i <= r1) {
        temp.push_back(v[i++]);
    }
    
    while(j <= r2) {
        temp.push_back(v[j++]);
    }
    
    int pos = l1;
    for(int k=0; k<temp.size(); k++) {
        v[pos++] = temp[k];
    }

}

void merge_sort(vector<int> &v, int start, int end) {
    if (start >= end) {
        return;
    }
    
    int mid = (start + end) >> 1;
    merge_sort(v,start, mid);
    merge_sort(v, mid+1, end);
    merge(v, start, mid, mid+1, end);
}

快速排序

void quick_sort(vector<int> &v, int start, int end) {
    if (start >= end) {
        return;
    }
    
    int l = start, r = end;
    while(l < r) {
        while(l < r && v[r] >= v[start]) {
            r--;
        }
        
        while(l < r && v[l] <= v[start]) {
            l++;
        }
        
        if (l < r) {
            swap(v[l], v[r]);
        }
    }
    
    swap(v[start], v[l]);
    quick_sort(v, start, l-1);
    quick_sort(v, l+1, end);
}