一、快速排序
快速排序是一种基于比较的排序算法，可以在平均情况下运行时间为o(n log n)，是最常使用的快速、通用的排序算法之一。这个算法的基本思想是选择一个元素作为“枢轴”（通常是数组中的第一个或最后一个元素），然后将数组中的所有其他元素与枢轴进行比较，把小于等于枢轴的元素放到一个子数组中，把大于枢轴的元素放到另一个子数组中，在对每个子数组递归地应用此过程，直到子数组只有零个或一个元素，最后将子数组按顺序连接起来即可得到排序后的数组。
具体步骤如下：
- 选择枢轴元素，通常是第一个元素或最后一个元素。
- 将数组分成两个子数组，根据枢轴元素将小于等于枢轴元素的元素放在左边的子数组中，将大于枢轴元素的元素放在右边的子数组中。
- 对左右子数组递归执行快速排序操作。
- 最后将左、枢轴、右三部分连接起来即为排序结果。
这个算法的性能取决于所选择的枢轴元素，理想情况下每次都能够选择到位于数组正中间的元素作为枢轴，此时快速排序算法的时间复杂度为o(n log n)。但是如果每次选到的枢轴都离两端比较远，则可能会导致算法效率降低，时间复杂度达到o(n^2)。因此，在实际应用中，通常会采用一些优化策略来提高算法性能
以下是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[high]; // 选取最后一个元素作为基准值
int i = (low - 1); // i指向左边界
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return (i + 1); // 返回基准值的位置
}
// 快速排序函数
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 main() {
int arr[] = {
5, 2, 8, 3, 9, 1, 6};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("排序后的数组：\n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
在上面的代码中，swap函数用于交换两个元素的值，partition函数用于将数组分成左右两部分，并返回左右指针，quickSort函数是快速排序的主要函数，用于递归地对数组进行排序。在main函数中，我们定义了一个整数数组，并调用quickSort函数对其进行排序。最后，我们输出排序后的数组。
方法二：
#include <stdio.h>
void quicksort(int *arr, int left, int right) {
if (left < right) {
int pivot = arr[right];
int i = left - 1;
int temp;
for (int j = left; j < right; j++) {
if (arr[j] <= pivot) {
i++;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
i++;
temp = arr[i];
arr[i] = pivot;
arr[right] = temp;
quicksort(arr, left, i-1);
quicksort(arr, i+1, right);
}
}
int main() {
int arr[] = {
4, 2, 1, 6, 3, 5};
int n = sizeof(arr)/sizeof(int);
quicksort(arr, 0, n-1);
printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
快速排序的主体是 quicksort 函数，它接受三个参数：一个整数数组 arr、数组的左边界 left 和数组的右边界 right。然后在函数内部使用了递归来进行分割和排序。
在 quicksort 函数中，首先判断左右指针是否相等，如果不相等就进入排序过程。
选择作为 pivot 的元素是 arr[right]，在 i 和 j 指针的移动过程中，较小的元素被放在了 [left, i-1] 区间内，i 指向下一个要交换的位置。最后将 pivot 元素归位。
最后递归地对左右两个区间进行排序，直到任务处理完毕。
当 quicksort 函数执行时，它会打印经过排序后的
