快速排序是一种把大问题分成小问题的算法。它的目的是把一个无序的数组变成有序的数组。
它的思想如下：
首先选择数组的第一个数作为“中间值”。
然后把数组分成两半，左边的数都比中间值小，右边的数都比中间值大。
对左边和右边的数组分别再重复上面的步骤，直到数组的大小为1。
这个算法是通过不断分治的方法来解决问题的。我们把一个大的无序数组分成若干个小的无序数组，再对每个小的数组使用快速排序算法，最终使得整个数组变得有序。
#include<stdio.h>
//交换两个数的值
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
//划分数组，使得小于pivot的数在左边，大于pivot的数在右边
int partition(int arr[], int low, int high)
{
int pivot = arr[high]; //选取最后一个数作为pivot
int i = (low - 1); //i指向第一个数
for (int j = low; j <= high - 1; j++)
{
if (arr[j] <= pivot) //如果当前数小于等于pivot，则交换
{
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]); //最后交换pivot和i+1
return (i + 1); //返回pivot的位置
}
//快速排序
void quickSort(int arr[], int low, int high)
{
if (low < high) //如果数组不为空，则继续排序
{
int pi = partition(arr, low, high); //得到pivot的位置
quickSort(arr, low, pi - 1); //对左边数组进行排序
quickSort(arr, pi + 1, high); //对右边数组进行排序
}
}
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: \n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
#include<stdio.h>
// 函数：交换两个数的值
void swap(int *a, int *b) {
int temp = *a; // 用临时变量存储 a 的值
*a = *b; // 将 b 的值赋给 a
*b = temp; // 将临时变量的值赋给 b
}
// 快速排序算法
void quick_sort(int arr[], int left, int right) {
int i, j, pivot; // 定义循环变量和 pivot
// 判断左边的索引是否小于右边的索引
if (left < right) {
i = left; // 从左边开始遍历
j = right + 1; // 从右边开始遍历
pivot = arr[left]; // 定义 pivot 为左边的数
do {
// 找到第一个比 pivot 大的数的位置
do i++; while (arr[i] < pivot);
// 找到第一个比 pivot 小的数的位置
do j--; while (arr[j] > pivot);
// 如果 i 大于等于 j，说明两个位置的数交换位置
if (i < j) swap(&arr[i], &arr[j]);
} while (i < j); // 循环知道 i 大于等于 j
// 交换 pivot 和 j 的值，使 pivot 所在位置分隔数组为两部分
swap(&arr[left], &arr[j]);
// 对 pivot 前面的部分继续进行快速排序
quick_sort(arr, left, j - 1);
// 对 pivot 后面的部分继续进行快速排序
quick_sort(arr, j + 1, right);
}
}
int main() {
int arr[] = {5, 1, 9, 4, 6, 2, 8, 3, 7}; // 定义要排序的数组
int n = sizeof(arr) / sizeof(arr[0]); // 计算数组的大小
// 执行快速排序
quick_sort(arr, 0, n - 1);
// 输出排序后的数组
printf("Sorted array: \n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
/*该程序实现了快速排序算法。首先，它定义了一个交换两个数值的函数 `swap()`。然后，它定义了快速排序函数
`quick_sort()`，该函数对传递的数组进行排序。最后，在 `main()` 函数中，它定义了要排序的数组，并调用了快速排序函数对该数组进行排序，最后输出了排序后的数组。*/
#include <stdio.h>
/* 分割数组的函数，用于在快速排序中获取分割点的位置 */
int partition(int arr[], int low, int high)
{
int pivot = arr[high]; // 以最后一个数为分割点
int i = (low - 1); // 小于分割点的数的索引
/* 遍历数组中的元素 */
for (int j = low; j <= high - 1; 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 quick_sort(int arr[], int low, int high)
{
if (low < high) {
/* 获取分割点的索引 */
int pivot_index = partition(arr, low, high);
/* 递归地对左半边进行快速排序 */
quick_sort(arr, low, pivot_index - 1);
/* 递归地对右半边进行快速排序 */
quick_sort(arr, pivot_index + 1, high);
}
}
/* 程序的主函数 */
int main()
{
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
printf("排序前的数组：\n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
quick_sort(arr, 0, n - 1);
printf("排序后的数组：\n");
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
/*在上面的代码中，我们实现了快速排序的算法。首先我们创建了一个 partition 函数，该函数用于将数组分割为两个子数组，一个是小于等于分割点的数，另一个是大于分割点的数。在快速排序中，通过调用 partition 函数，我们可以递归地对数组进行排序。
最后，在 main 函数中，我们创建了一个数组，并使用快速排序将其排序，最后输出结果。*/
快速排序是一种非常高效的排序算法，因为它具有平均线性的时间复杂度。它的时间复杂度在最坏情况下仍然是线性的，但平均情况下要好得多。一般而言，快速排序是时间复杂度为O(nlogn)的排序算法
