【C语言】快速排序

wander

快速排序是一种高效的基于比较的排序算法，C语言是快速排序的实现语言之一。在本文中，我们将详细介绍C语言实现快速排序的步骤以及代码，并分析其时间复杂度。
实现步骤

快速排序的实现分为两个主要步骤：选择基准元素和分割序列。

选择基准元素


选择基准元素是快速排序的关键步骤。基准元素的选择会直接影响算法的效率。一般情况下，我们可以选取待排序序列的第一个元素作为基准元素，但这种方式可能会导致最坏情况的出现，即待排序序列已经有序或近乎有序，此时时间复杂度将退化为O(n^2)。

为了避免最坏情况的出现，我们可以采用一些随机化的方法来选择基准元素，例如随机选取一个元素作为基准元素，或者从待排序序列中随机选择三个元素，取它们的中位数作为基准元素。

分割序列


在选择基准元素之后，我们需要将待排序序列分割成两个子序列。具体而言，我们可以维护两个指针，一个指向待排序序列的头部，一个指向序列的尾部。然后分别从两端开始扫描序列，当找到一个元素比基准元素大（或小）时，就将其与另一个元素交换位置。重复这个过程，直到两个指针相遇为止。此时，我们可以将基准元素和相遇位置上的元素交换位置，然后将序列分成左右两部分，左边的部分的所有元素都小于等于基准元素，右边的部分的所有元素都大于等于基准元素。

递归排序
接下来，我们可以递归地对左右两个子序列进行快速排序，直到序列有序为止。

C语言实现


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

• #include <stdio.h>
• void swap(int *a, int *b) {
•     int temp = *a;
•     *a = *b;
•     *b = temp;
• }
• int partition(int arr[], int low, int high) {
•     int pivot = arr[low];
•     int i = low, j = high;
•     while (i < j) {
•         while (i < j && arr[j >= pivot) j--;
•         while (i < j && arr[i <= pivot) i++;
•         if (i < j) {
•             swap(&arr[i], &arr[j]);
•         }
•     }
•     swap(&arr[low], &arr[i]);
•     return i;
• }
• void quicksort(int arr[], int low, int high) {
•     if (low < high) {
•         int pi = partition(arr, low, high);
•         quicksort(arr, low, pi - 1);
•         quicksort(arr, pi + 1, high);
•     }
• }
• void printArray(int arr[], int size) {
•     int i;
•     for (i = 0; i < size; i++) printf("%d ", arr[i]);
•     printf("\n");
• }
• int main() {
•     int arr[] = {10, 7, 8, 9, 1, 5};
•     int n = sizeof(arr) / sizeof(arr[0]);
•     quicksort(arr, 0, n - 1);
•     printf("Sorted array: ");
•     printArray(arr, n);
•     return 0;
• }
  

在这个代码中，我们首先定义了一个函数 swap，用于交换两个元素的值。然后，我们定义了一个函数 partition，该函数用于将待排序序列分割成两个子序列，并返回基准元素的位置。最后，我们定义了一个函数quicksort，该函数用于递归地对左右两个子序列进行快速排序。

在 quicksort 函数中，我们首先判断待排序序列是否为空，如果不为空，就调用 partition 函数将序列分割成两个子序列，然后递归地对左右两个子序列进行排序。在主函数中，我们定义了一个整数数组，并对其进行快速排序，最后输出排序后的数组。

时间复杂度分析


快速排序的时间复杂度取决于基准元素的选择方式。在最坏情况下，基准元素被选择为序列中的最小（或最大）元素，此时每次分割只能减少一个元素，需要进行 n 次分割才能完成排序，时间复杂度为 O(n^2)。在最好情况下，基准元素被选择为序列的中位数，此时每次分割将序列平均分成两部分，需要进行 log n 次分割才能完成排序，时间复杂度为 O(n log n)。

由于快速排序采用分治的思想，每次将序列分割成两个子序列进行排序，因此快速排序的时间复杂度为 O(n log n)。快速排序的空间复杂度主要取决于递归调用的层数，即分割的次数，最坏情况下需要进行 n 次分割，因此空间复杂度为 O(n)。

需要注意的是，在实际应用中，快速排序可能存在一些问题，比如当待排序序列中存在大量重复元素时，快速排序的效率会变得很低。为了解决这个问题，可以使用三路快速排序（即将序列分成小于、等于和大于基准元素三个部分进行排序），或者使用其他的排序算法。

总结


快速排序是一种高效的排序算法，它采用分治的思想，每次将序列分割成两个子序列进行排序，时间复杂度为 O(n log n)，空间复杂度为 O(n)。

快速排序的实现相对简单，但需要注意一些细节，比如基准元素的选择方式和数组越界的问题。在实际应用中，快速排序可能存在一些问题，需要结合具体情况选择合适的排序算法。