C语言如何实现快速排序？

C语言如何实现快速排序？

快速排序是一种高效的排序算法，它采用分治的思想，将一个大问题分成若干个小问题来解决。在每次分治中，选择一个基准值，把序列划分成两个子序列，其中一个子序列的元素都比基准值小，另一个子序列的元素都比基准值大。然后对这两个子序列递归地进行排序，直到整个序列有序为止。

以下是C语言中实现快速排序的基本步骤：

1. 选择基准值：首先从序列中选择一个基准值，通常选择第一个或最后一个元素。
2. 划分子序列：通过一次遍历，将序列中所有比基准值小的元素放在左边，比基准值大的元素放在右边。
3. 递归排序：对左右两个子序列递归调用快速排序函数，直到子序列长度为1或0。
4. 合并结果：将排好序的两个子序列合并起来，得到最终的有序序列。

以下是C语言中实现快速排序的示例代码：

void quickSort(int arr[], int left, int right) {
    if (left >= right) { // 如果子序列长度为1或0，则已经有序
        return;
    }
    int pivot = arr[left]; // 选择第一个元素作为基准值
    int i = left + 1, j = right;
    while (i <= j) { // 划分子序列
        while (arr[i] < pivot && i <= right) {
            i++;
        }
        while (arr[j] > pivot && j >= left + 1) {
            j--;
        }
        if (i <= j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }
    arr[left] = arr[j]; // 将基准值放到正确的位置
    arr[j] = pivot;
    quickSort(arr, left, j - 1); // 递归排序左子序列
    quickSort(arr, j + 1, right); // 递归排序右子序列
}

快速排序的时间复杂度为O(nlogn)，具有较高的排序速度和较低的空间复杂度，因此被广泛应用于各种应用场景中。