1. 简介
快速排序（Quick Sort）是一种常见的排序算法，采用分治的思想。这篇文章将详细介绍如何用C语言实现快速排序算法，并给出相应的代码示例。
2. 算法原理
快速排序的思想是通过选取一个元素作为枢纽（pivot），将待排序序列分割成两个子序列，其中一个子序列中的元素都比枢纽小，另一个子序列中的元素都比枢纽大。然后对这两个子序列分别进行排序，最后将它们合并起来。
具体步骤如下：
2.1 选择枢纽
可以选择待排序序列中的任意一个元素作为枢纽。常见的选择方法有：
选择第一个元素作为枢纽
选择最后一个元素作为枢纽
选择中间元素作为枢纽
选择随机元素作为枢纽
在实际应用中，一般采用第一个元素或者随机元素作为枢纽。
2.2 分割
根据选取的枢纽，将序列中的元素分割成两个子序列。其中一个子序列中的元素都比枢纽小，另一个子序列中的元素都比枢纽大。
分割操作的具体过程如下：
设定两个指针low和high，将low指向待排序序列的头部，high指向尾部。
以枢纽的值为基准，从右向左遍历待排序序列，找到第一个比枢纽小的元素，将其与枢纽交换位置。
从左向右遍历待排序序列，找到第一个比枢纽大的元素，将其与枢纽交换位置。
重复以上两步，直到low等于high。
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--;
}
swap(&arr[i], &arr[j]);
while (i < j && arr[i] <= pivot) {
i++;
}
swap(&arr[i], &arr[j]);
}
return i;
}
2.3 递归排序
通过分割操作，将待排序序列分割成两个子序列。然后对这两个子序列分别进行排序，最后将它们合并起来。
递归排序的具体过程如下：
选择一个枢纽。
以枢纽为界，将序列分割。
对两个子序列分别进行递归排序。
将排序好的子序列合并起来。
递归排序的结束条件是子序列中只有一个元素或者为空。
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);
}
}
3. 实现代码
下面是完整的C语言实现代码：
#include
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--;
}
swap(&arr[i], &arr[j]);
while (i < j && arr[i] <= pivot) {
i++;
}
swap(&arr[i], &arr[j]);
}
return i;
}
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);
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {5, 3, 8, 6, 2, 7, 1, 4};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
printArray(arr, size);
quickSort(arr, 0, size - 1);
printf("Sorted array: ");
printArray(arr, size);
return 0;
}
4. 总结
快速排序是一种高效的排序算法，具有较好的平均时间复杂度。通过选取一个枢纽，将待排序序列分割成两个子序列，然后对这两个子序列进行递归排序，完成后再将它们合并起来。通过不断缩小子序列的范围，最终将整个序列排序好。
本文详细介绍了快速排序算法的原理及C语言实现，并给出了相应的代码示例。希望通过本文的介绍，读者能够理解快速排序的思想，并掌握如何用C语言实现该算法。