C语言快速排序代码 算法 讲解

快速排序（Quick Sort）是一种基于分治思想的高效排序算法，是经典的排序算法之一。它的核心思想是选择一个元素作为基准（pivot），将序列分成两个子序列，其中一个子序列的所有元素都比基准小，另一个子序列的所有元素都比基准大，然后对这两个子序列分别递归地进行快速排序。

具体实现过程如下：

1. 选择一个元素作为基准（pivot）。

2. 将序列分成两个子序列，其中一个子序列的所有元素都比基准小，另一个子序列的所有元素都比基准大。可以采用双指针法实现，即使用两个指针i和j分别从序列的左端和右端开始扫描，当i指向的元素大于等于基准时，停止扫描；当j指向的元素小于等于基准时，停止扫描；然后交换i和j指向的元素。

3. 递归地对子序列进行快速排序。

下面是C语言实现的快速排序代码：

void quick_sort(int arr[], int left, int right)
{
    if (left >= right) return;  // 如果左指针大于等于右指针，直接返回

    int i = left, j = right, pivot = arr[left];  // 选择左端元素作为基准

    while (i < j)
    {
        while (i < j && arr[j] >= pivot) j--;  // 从右端开始扫描，找到第一个小于基准的元素
        if (i < j) arr[i++] = arr[j];  // 将该元素放到左端

        while (i < j && arr[i] < pivot) i++;  // 从左端开始扫描，找到第一个大于等于基准的元素
        if (i < j) arr[j--] = arr[i];  // 将该元素放到右端
    }

    arr[i] = pivot;  // 将基准放到最终位置

    quick_sort(arr, left, i - 1);  // 递归地对左子序列进行快速排序
    quick_sort(arr, i + 1, right);  // 递归地对右子序列进行快速排序
}

在主函数中调用该函数即可对数组进行快速排序：

int main()
{
    int arr[] = {5, 2, 8, 4, 7, 1, 9, 3, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    quick_sort(arr, 0, n - 1);

    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }

    return 0;
}

输出结果为：1 2 3 4 5 6 7 8 9。