快速排序

思路

• 快排第一件事就是找基准值z

• 普通快排一般以第一个为基准值

• 利用两个指针（x, y）扫描：x从左往右；y从右往左，直到x>=y结束扫描

• 一般先从右往左边找到比基准值z小的数，num[x++] = num[y];

• 然后x从左往右扫描找到比基准值z大的数，num[y–] = num[x];

• 交替扫描，直到x>=y结束扫描；最后num[x==y] = z;

• 对于普通快速排序，数据越无序越好

代码演示

主要函数

void quick_sort(int *num, int l, int r) {
    //数据越乱越好 
    if (l > r) return ;
    int x = l, y = r, z = num[x];
    while (x < y) {
        while (x < y && num[y] > z) y--;
        if (x < y) num[x++] = num[y];
        while (x < y && num[x] < z) x++;
        if (x < y) num[y--] = num[x];
    }
    num[x] = z;
    quick_sort(num, l, x - 1);
    quick_sort(num, x + 1, r);
    return ;
}

测试

#include <stdio.h>
#include <stdlib.h>

//O(n*log(n))
/*
1、选择基数（默认第一个元素为基准值）
 
*/ 

void quick_sort(int *num, int l, int r) {
    //数据越乱越好 
    if (l > r) return ;
    int x = l, y = r, z = num[x];
    while (x < y) {
        while (x < y && num[y] > z) y--;
        if (x < y) num[x++] = num[y];
        while (x < y && num[x] < z) x++;
        if (x < y) num[y--] = num[x];
    }
    num[x] = z;
    quick_sort(num, l, x - 1);
    quick_sort(num, x + 1, r);
    return ;
}

int main() {
    #define n 20
    int num[n];
    for (int i = 0; i < n; i++) {
        num[i] = rand() % n * 20;
    }
    for (int i = 0; i < n; i++) {
        i && printf(", ");
        printf("%d", num[i]);
    }
    quick_sort(num, 0, n - 1);
    printf("\n");
    for (int i = 0; i < n; i++) {
        i && printf(", ");
        printf("%d", num[i]);
    }
    return 0;
}