C语言中快速排序法怎么排

什么是快速排序法

快速排序法是一种常见的排序算法，它的基本思想是将一个未排序的数组分成两部分，其中一部分的每个元素都小于另一部分的元素，然后对这两部分分别进行排序，直到整个数组都有序。

快速排序法在平均情况下是一种高效的算法，时间复杂度为O(nlogn)。但在最坏情况下，时间复杂度为O(n^2)，即当数组已经有序或几乎有序时，快速排序法的效率较低。

快速排序法的原理

快速排序法的原理基于分治法，它的基本思想是：

选取一个元素作为基准值（pivot）

将比基准值小的元素放在基准值的左边，比基准值大的元素放在基准值的右边

对基准值左右两边的子序列递归地进行快速排序

具体的实现步骤如下：

从数组中选取一个元素作为基准值

  int Partition(int arr[], int low, int high)
  {
      int pivot = arr[low];
      while (low < high)
      {
          while (low < high && arr[high] >= pivot)// 从后向前找到第一个小于pivot的位置
              high--;
          arr[low] = arr[high];
          while (low < high && arr[low] <= pivot)// 从前向后找到第一个大于pivot的位置
              low++;
          arr[high] = arr[low];
      }
      arr[low] = pivot;
      return low;
  }

在上述代码中，我们选取数组的第一个元素作为基准值pivot。Partition函数是分割数组的函数，它的返回值low是分割点的位置。在这个函数中，使用两个指针low和high，从数组的两端开始搜索，找到第一个比基准值小的元素和第一个比基准值大的元素，并将它们交换位置，直到low和high相遇为止。

将数组分割成左右两个子序列，分别进行递归排序

  void QuickSort(int arr[], int low, int high)
  {
      if (low < high)
      {
          int pivotIndex = Partition(arr, low, high);
          QuickSort(arr, low, pivotIndex - 1);
          QuickSort(arr, pivotIndex + 1, high);
      }
  }

在递归过程中，如果子序列的长度小于2，则可以认为这个子序列已经有序。

快速排序法的实现

下面演示如何用C语言实现快速排序法：

#include <stdio.h>
int Partition(int arr[], int low, int high)
{
    int pivot = arr[low];
    while (low < high)
    {
        while (low < high && arr[high] >= pivot)
            high--;
        arr[low] = arr[high];
        while (low < high && arr[low] <= pivot)
            low++;
        arr[high] = arr[low];
    }
    arr[low] = pivot;
    return low;
}
void QuickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        int pivotIndex = Partition(arr, low, high);
        QuickSort(arr, low, pivotIndex - 1);
        QuickSort(arr, pivotIndex + 1, high);
    }
}
int main()
{
    int arr[] = { 6, 3, 1, 8, 9, 2, 4, 7, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Before sorting: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    QuickSort(arr, 0, n - 1);
    printf("After sorting: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

在上述代码中，我们用一个长度为9的数组作为示例输入，调用QuickSort函数对数组进行排序。程序输出如下：

Before sorting: 6 3 1 8 9 2 4 7 5 
After sorting: 1 2 3 4 5 6 7 8 9

快速排序法的优化

随机化选取基准值

快速排序法的最坏时间复杂度出现在基准值的选取不合理的情况下。为了避免这种情况，可以通过随机化选取基准值来避免最坏情况的出现。具体做法是，从数组中随机选取一个元素作为基准值。

int RandomizedPartition(int arr[], int low, int high)
{
    int i = rand() % (high - low + 1) + low;
    int pivot = arr[i];
    while (low < high)
    {
        while (low < high && arr[high] >= pivot)
            high--;
        arr[low] = arr[high];
        while (low < high && arr[low] <= pivot)
            low++;
        arr[high] = arr[low];
    }
    arr[low] = pivot;
    return low;
}
void RandomizedQuickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        int pivotIndex = RandomizedPartition(arr, low, high);
        RandomizedQuickSort(arr, low, pivotIndex - 1);
        RandomizedQuickSort(arr, pivotIndex + 1, high);
    }
}

对小规模子数组使用插入排序

快速排序法在小规模子数组中的性能并不比插入排序好。因此，在快速排序法的实现中，当子数组的长度小于某个阈值时，可以采用插入排序的方法对子数组进行排序。

void InsertionSort(int arr[], int low, int high)
{
    for (int i = low + 1; i <= high; i++)
    {
        int key = arr[i];
        int j = i - 1;
        while (j >= low && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}
void ImprovedQuickSort(int arr[], int low, int high)
{
    if (high - low + 1 < 10)
    {
        InsertionSort(arr, low, high);
        return;
    }
    int pivotIndex = RandomizedPartition(arr, low, high);
    ImprovedQuickSort(arr, low, pivotIndex - 1);
    ImprovedQuickSort(arr, pivotIndex + 1, high);
}

总结

快速排序法是一种常见的排序算法，它的时间复杂度为O(nlogn)。快速排序法的基本思想是利用分治法，选取一个基准值，将数组分成两个子序列，分别进行排序。然后递归对子序列进行排序，直到整个数组有序。快速排序法有一些优化策略，如随机化选取基准值以避免最坏情况的出现，对小规模子数组使用插入排序以提高性能。