C 语言实现快速排序
2021-07-206.9k 阅读
快速排序算法概述
快速排序（Quick Sort）是一种高效的排序算法，由英国计算机科学家托尼·霍尔（Tony Hoare）在1959年提出，并于1961年发表。它采用了分治（Divide and Conquer）的策略，通过将一个大问题分解为若干个小问题，分别解决这些小问题，然后将小问题的解合并起来得到原问题的解。
快速排序的基本思想是：在待排序的数组中选择一个基准元素（pivot），通过一趟排序将待排序数组分为两部分，使得左边部分的元素都小于等于基准元素，右边部分的元素都大于等于基准元素。然后分别对左右两部分递归地进行快速排序，最终使得整个数组有序。
C语言实现快速排序的基本步骤
选择基准元素
选择基准元素是快速排序的关键步骤之一。常见的选择基准元素的方法有：
- 固定位置选择：通常选择数组的第一个元素或最后一个元素作为基准元素。例如，选择第一个元素作为基准元素：
int pivot = arr[left];
- 随机选择：从数组中随机选择一个元素作为基准元素。这种方法可以避免在某些特殊情况下（如数组已经有序）快速排序的时间复杂度退化到O(n²)。在C语言中，可以使用
rand()函数结合srand()函数来实现随机选择：
#include <stdlib.h>
#include <time.h>
// 随机选择基准元素
int randomPivot(int arr[], int left, int right) {
srand(time(NULL));
int index = left + rand() % (right - left + 1);
return arr[index];
}
- 三数取中：取数组的第一个元素、中间元素和最后一个元素，比较这三个元素的大小，选择中间值作为基准元素。这种方法可以在一定程度上避免选择到最大或最小元素作为基准元素，从而提高算法的平均性能。实现代码如下：
// 三数取中选择基准元素
int medianOfThree(int arr[], int left, int right) {
int mid = left + (right - left) / 2;
if ((arr[left] <= arr[mid] && arr[mid] <= arr[right]) || (arr[right] <= arr[mid] && arr[mid] <= arr[left])) {
return arr[mid];
} else if ((arr[mid] <= arr[left] && arr[left] <= arr[right]) || (arr[right] <= arr[left] && arr[left] <= arr[mid])) {
return arr[left];
} else {
return arr[right];
}
}
划分操作
划分操作是将数组分为左右两部分的核心步骤。在这一步中，我们需要将小于等于基准元素的元素移动到数组的左边，大于等于基准元素的元素移动到数组的右边。常见的划分方法有以下两种：
- 单边循环法：从数组的两端开始，设置两个指针
left和right。首先从right指针开始，向左移动right指针，直到找到一个小于基准元素的元素；然后从left指针开始，向右移动left指针，直到找到一个大于基准元素的元素。如果left指针小于right指针，则交换这两个元素，继续上述过程，直到left指针大于等于right指针。最后，将基准元素与left指针指向的元素交换，这样就完成了一次划分。代码实现如下：
// 单边循环法划分
int partitionSingleLoop(int arr[], int left, int right, int pivot) {
int index = left - 1;
for (int j = left; j <= right; j++) {
if (arr[j] <= pivot) {
index++;
int temp = arr[index];
arr[index] = arr[j];
arr[j] = temp;
}
}
return index;
}
- 双边循环法：同样从数组的两端开始，设置两个指针
left和right。首先，将基准元素与数组的第一个元素交换。然后，从left指针的下一个位置开始，向右移动left指针，直到找到一个大于基准元素的元素；从right指针开始，向左移动right指针，直到找到一个小于基准元素的元素。如果left指针小于right指针，则交换这两个元素，继续上述过程，直到left指针大于等于right指针。最后，将基准元素与right指针指向的元素交换，完成划分。代码实现如下：
// 双边循环法划分
int partitionDoubleLoop(int arr[], int left, int right) {
int pivot = arr[left];
while (left < right) {
while (left < right && arr[right] >= pivot) {
right--;
}
arr[left] = arr[right];
while (left < right && arr[left] <= pivot) {
left++;
}
arr[right] = arr[left];
}
arr[left] = pivot;
return left;
}
递归调用
在完成一次划分后，数组被分为左右两部分。接下来，分别对左右两部分递归地调用快速排序算法，直到子数组的长度小于等于1，此时子数组已经有序。递归调用的代码如下：
// 快速排序递归函数
void quickSort(int arr[], int left, int right) {
if (left >= right) {
return;
}
int pivotIndex = partitionDoubleLoop(arr, left, right);
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
完整的C语言代码示例
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// 双边循环法划分
int partitionDoubleLoop(int arr[], int left, int right) {
int pivot = arr[left];
while (left < right) {
while (left < right && arr[right] >= pivot) {
right--;
}
arr[left] = arr[right];
while (left < right && arr[left] <= pivot) {
left++;
}
arr[right] = arr[left];
}
arr[left] = pivot;
return left;
}
// 快速排序递归函数
void quickSort(int arr[], int left, int right) {
if (left >= right) {
return;
}
int pivotIndex = partitionDoubleLoop(arr, left, right);
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
int main() {
int arr[] = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("排序后的数组: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
快速排序的时间复杂度和空间复杂度
时间复杂度
- 平均情况：快速排序的平均时间复杂度为O(n log n)。这是因为在平均情况下，每次划分都能将数组大致分为两个长度相等的子数组，递归深度为log n，每层的操作次数为n，所以总的时间复杂度为O(n log n)。
- 最坏情况：当每次选择的基准元素都是数组中的最大或最小元素时，快速排序的时间复杂度会退化到O(n²)。例如，当数组已经有序，选择第一个元素作为基准元素时，每次划分都只能将数组分为一个长度为1和一个长度为n - 1的子数组，递归深度为n，每层的操作次数为n，所以时间复杂度为O(n²)。通过选择合适的基准元素（如随机选择或三数取中），可以有效地避免最坏情况的发生。
空间复杂度
- 递归栈空间：快速排序的空间复杂度主要取决于递归调用的深度。在平均情况下，递归深度为log n，所以空间复杂度为O(log n)。在最坏情况下，递归深度为n，空间复杂度为O(n)。
- 辅助空间：在上述实现中，我们没有使用额外的辅助空间，所以辅助空间复杂度为O(1)。如果在划分过程中使用了额外的数组来存储临时结果，那么空间复杂度会相应增加。
快速排序的优化
优化基准元素的选择
如前文所述，选择合适的基准元素可以提高快速排序的性能。随机选择基准元素或三数取中方法可以有效地避免最坏情况的发生，使得快速排序在大多数情况下都能保持较高的性能。
小规模数组的处理
当子数组的规模较小时，递归调用的开销可能会超过排序本身的开销。对于小规模数组，可以使用插入排序等简单的排序算法来代替快速排序。在实际应用中，可以设置一个阈值（如16），当子数组的长度小于等于这个阈值时，使用插入排序。代码实现如下：
// 插入排序
void insertionSort(int arr[], int left, int right) {
for (int i = left + 1; i <= right; i++) {
int key = arr[i];
int j = i - 1;
while (j >= left && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
// 优化后的快速排序递归函数
void optimizedQuickSort(int arr[], int left, int right) {
if (left >= right) {
return;
}
if (right - left + 1 <= 16) {
insertionSort(arr, left, right);
return;
}
int pivotIndex = partitionDoubleLoop(arr, left, right);
optimizedQuickSort(arr, left, pivotIndex - 1);
optimizedQuickSort(arr, pivotIndex + 1, right);
}
尾递归优化
在上述实现中，快速排序使用了递归调用。递归调用会消耗栈空间，当递归深度较大时，可能会导致栈溢出。尾递归优化是一种将递归调用转换为迭代的技术，使得递归调用在函数的最后一步进行，从而避免栈溢出的问题。对于快速排序，可以通过使用一个栈来模拟递归调用，实现尾递归优化。代码实现如下：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// 双边循环法划分
int partitionDoubleLoop(int arr[], int left, int right) {
int pivot = arr[left];
while (left < right) {
while (left < right && arr[right] >= pivot) {
right--;
}
arr[left] = arr[right];
while (left < right && arr[left] <= pivot) {
left++;
}
arr[right] = arr[left];
}
arr[left] = pivot;
return left;
}
// 尾递归优化的快速排序
void tailRecursiveQuickSort(int arr[], int left, int right) {
int stack[right - left + 1];
int top = -1;
stack[++top] = left;
stack[++top] = right;
while (top >= 0) {
int r = stack[top--];
int l = stack[top--];
int pivotIndex = partitionDoubleLoop(arr, l, r);
if (pivotIndex - 1 > l) {
stack[++top] = l;
stack[++top] = pivotIndex - 1;
}
if (pivotIndex + 1 < r) {
stack[++top] = pivotIndex + 1;
stack[++top] = r;
}
}
}
int main() {
int arr[] = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
int n = sizeof(arr) / sizeof(arr[0]);
tailRecursiveQuickSort(arr, 0, n - 1);
printf("排序后的数组: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
快速排序在实际应用中的注意事项
- 数据规模：快速排序在数据规模较大时表现出较高的性能，但对于小规模数据，插入排序等简单排序算法可能更合适。在实际应用中，需要根据数据规模来选择合适的排序算法。
- 数据分布：如果数据分布具有一定的特点（如大部分数据已经有序），选择合适的基准元素可以避免快速排序性能的退化。例如，在面对有序数据时，随机选择或三数取中方法可以显著提高快速排序的性能。
- 稳定性：快速排序是一种不稳定的排序算法，即相同元素的相对顺序在排序后可能会改变。如果应用场景对稳定性有要求，则需要选择其他稳定的排序算法，如归并排序或冒泡排序。
通过深入理解快速排序的原理、C语言实现方法、性能特点以及优化策略，开发者可以在实际编程中灵活运用快速排序算法，提高程序的运行效率。