C语言快速排序详解

【1】快速排序核心思想

　　核心思想是分而治之，每一轮排序都会选出一个基准，一轮排序完成后，所有比基准小的数一定在左边，比基准大的数一定在右边，在分别通过同样的方法对左右两边的数组进行排序，不断划分，最后完成整个数组的排序。它的效率相比冒泡排序的双重for循环有所提升。时间复杂度（logn）

【2】快速排序图解

【3】快速排序代码详解

#include <stdio.h>
#define N 10

// 函数声明
void quickSort(int arr[], int left, int right);

int main() {
    // 标准的输入输出不需要缓存，直接输出
    setbuf(stdout, NULL);

    int arr[N] = {4, 3, 8, 2, 1, 7, 5, 6, 9, 0};

    quickSort(arr, 0, N - 1);

    printf("数组升序排列：");
    for (int i = 0; i < N; ++i) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

/**
 * 快速排序
 */ 
void quickSort(int arr[], int left, int right) {
    if (left >= right) {
        return;
    }
    int l = left, r = right;
    int base = arr[left];
    while (l < r) {
        // 依次从右边判断元素是否比基准大，如果比基准大：右边指针往前走
        while (l < r && arr[r] >= base) {
            r--;
        }
        // 出并列的while循环：从右边比较时已经遇到比基准小的值【替换左边的值】
        arr[l] = arr[r];
        // 依次从左边判断元素是否比基准小，如果比基准小：左边指针往后走
        while (l < r && arr[l] <= base) {
            l++;
        }
        // 出并列的while循环：从左边比较时已经遇到比基准大的值【替换右边的值】
        arr[r] = arr[l];
    }
    // 出并列的while循环：当前这一趟已经比较完毕，比基准大的在基准下标的右边，比基准小的在基准下标的左边
    arr[r] = base;
    // 递归排序左边
    quickSort(arr, left, r - 1);
    // 递归排序右边
    quickSort(arr, r + 1, right);
}

【4】快速排序执行结果