C语言中快速排序法如何排

快速排序算法介绍

快速排序是一种常用的排序算法，利用分治的思想来实现。该算法的基本思想是，选取一个元素作为基准值，将数组划分为两个子数组，使得左边的子数组所有元素均小于基准值，右边的子数组所有元素均大于基准值，然后对左右子数组分别递归地应用快速排序算法，直到每个子数组只包含一个元素或为空。

快速排序算法代码实现

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
    }
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
  
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

代码说明

上述代码中的quickSort()函数是快速排序的入口函数，它接受一个整数数组、数组的起始索引和结束索引作为参数。在该函数中，首先判断区间是否有效（起始索引小于结束索引），然后选择一个基准值，并调用partition()函数将数组划分为两个子数组。然后对左右子数组分别进行递归调用quickSort()函数。递归的结束条件是每个子数组只包含一个元素或为空。

partition()函数用于将数组划分为两个子数组。在该函数中，首先选取最后一个元素作为基准值，同时设置一个指针i，初始值为起始索引-1。然后使用一个循环遍历数组中的元素，如果元素小于基准值，则将指针i右移一位，并交换元素arr[i]和arr[j]的位置。循环结束后，将基准值与arr[i+1]交换位置，并返回i+1作为下一次划分的基准值位置。

swap()函数用于交换两个整数变量的值，它接受两个指针作为参数，并使用一个临时变量temp来实现交换。

总结

快速排序算法是一种高效的排序算法，其时间复杂度为O(nlogn)。通过选择合适的基准值和递归调用，快速排序能够在最坏情况下也能达到很好的性能。通过对数组的划分和分治思想的应用，快速排序将数组逐步排序，直到最终完成整个排序过程。