快速排序

快速排序

算法思想

快排的原理是：在数组中选取一个基准，将小于基准的元素放到基准的左边，将大于基准的元素放到基准的右边，递归重复这个过程。

代码

a[s] 作为基准元素：

C

void quicksort(int* a, int s, int t) {

    if (s >= t) {return;}
    // 选择a[s]作为基准
    int pivot = a[s];
    // 指针i, j
    int i = s, j = t;
    while (i < j) {
        while (i < j && a[j] >= pivot) {j--;}
        if (i == j) {break;}
        a[i] = a[j];
        i++;
        while (i < j && a[i] <= pivot>) {i++;}
        if (i == j) {break;}
        a[j] = a[i];
        j--;
    }
    a[i] = pivot;
    quicksort(a, s, i-1);
    quicksort(a, i+1, t);

}

随机生成基准元素：

C

void quicksort(int* a, int s, int t) {
    if (s >= t) {return;}
    // 选择a[s]作为基准
    int r = s + rand() % (t - s + 1);
    int povit = a[r];
    a[r] = a[s];
    // 指针i, j
    int i = s, j = t;
    while (i < j) {
        while (i < j && a[j] >= pivot) {j--;}
        if (i == j) {break;}
        a[i] = a[j];
        i++;
        while (i < j && a[i] <= pivot>) {i++;}
        if (i == j) {break;}
        a[j] = a[i];
        j--;
    }
    a[i] = pivot;
    quicksort(a, s, i-1);
    quicksort(a, i+1, t);
}

扩展

quickminK

求一个数组中前k小的元素并排序。

如果k很小，使用选择排序或者插入排序。

如果k比较大，可以使用快速排序。

C

void quickmink(int* a, int s, int t, int k) {

    if (s >= t || s >= k) {return;}
    // 选择a[s]作为基准
    int r = s + rand() % (t - s + 1);
    int povit = a[r];
    a[r] = a[s];
    // 指针i, j
    int i = s, j = t;
    while (i < j) {
        while (i < j && a[j] >= pivot) {j--;}
        if (i == j) {break;}
        a[i] = a[j];
        i++;
        while (i < j && a[i] <= pivot>) {i++;}
        if (i == j) {break;}
        a[j] = a[i];
        j--;
    }
    a[i] = pivot;
    quickmink(a, s, i-1, k);
    quickmink(a, i+1, t, k);

}

quickselect

求第k小的元素。

C

void quickselect(int* a, int s, int t, int k) {
    if (s > k - 1 || t < k - 1) {return;}
    // 选择a[s]作为基准
    int r = s + rand() % (t - s + 1);
    int povit = a[r];
    a[r] = a[s];
    // 指针i, j
    int i = s, j = t;
    while (i < j) {
        while (i < j && a[j] >= pivot) {j--;}
        if (i == j) {break;}
        a[i] = a[j];
        i++;
        while (i < j && a[i] <= pivot>) {i++;}
        if (i == j) {break;}
        a[j] = a[i];
        j--;
    }
    a[i] = pivot;
    quickselect(a, s, i-1, k);
    quickselect(a, i+1, t, k);
}