快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int Partition(int A[], int low, int high) {
    int pivot = A[low]; // 选择首元素作为基准
    while (low < high) {
        while (low < high && A[high] >= pivot) --high;
        A[low] = A[high]; // 比基准小的元素移到左端
        while (low < high && A[low] <= pivot) ++low;
        A[high] = A[low]; // 比基准大的元素移到右端
    }
    A[low] = pivot; // 基准元素放入最终位置
    return low;
}

void QuickSort(int A[], int low, int high) {
    if (low < high) {
        int pivotpos = Partition(A, low, high); // 划分序列
        QuickSort(A, low, pivotpos - 1); // 递归排序左子表
        QuickSort(A, pivotpos + 1, high); // 递归排序右子表
    }
}

快速选择

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int QuickSelect(int A[], int low, int high, int k) {
    if (low == high) return A[low]; // 基准情况
    int pivotPos = Partition(A, low, high); // 分区操作
    if (pivotPos == k) {
        return A[pivotPos];
    } else if (pivotPos > k) {
        return QuickSelect(A, low, pivotPos - 1, k); // 递归左半部分
    } else {
        return QuickSelect(A, pivotPos + 1, high, k); // 递归右半部分
    }
}
int Partition(int A[], int low, int high) {
    int pivot = A[low]; // 选择第一个元素为基准值
    while (low < high) {
        while (low < high && A[high] >= pivot) --high;
        A[low] = A[high]; // 将小于基准的元素移到左端
        while (low < high && A[low] <= pivot) ++low;
        A[high] = A[low]; // 将大于基准的元素移到右端
    }
    A[low] = pivot; // 基准值放入最终位置
    return low; // 返回基准值位置
}