快速排序

发表于 | 更新于: | | 阅读次数:
字数统计: 166 | 阅读时长 ≈ 1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void quickSort(vector<int>& array, int left, int right) {
    int i = left;
    int j = right;
    int temp = array[left];
    
    while (i != j) {
        while (i <j && temp <= array[j]) j --;
        if (i < j) array[i] = array[j];
        
        while (i < j && temp > array[i]) i ++;
        if (i < j) array[j] = array[i];
    }
    array[i] = temp;
    
    quickSort(array, left, i - 1);
    quickSort(array, i + 1, right);
}

分治思想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int partition(vector<int>& array, int left, int right) {
    int i = left;
    int j = right;
    int temp = array[left];
    
    while (i != j) {
        while (i <j && temp <= array[j]) j --;
        if (i < j) array[i] = array[j];
        
        while (i < j && temp > array[i]) i ++;
        if (i < j) array[j] = array[i];
    }
    array[i] = temp; 
    return i;
}
void quickSort(vector<int>& array, int left, int right) {
    if (left < right) {
        int dp = partition(array, left, right);
        quickSort(array, left, dp - 1);
        quickSort(array, dp + 1, right);
    }
}