排序------快速排序（C语言实现）

目录

快速排序算法

例题

题目描述

具体代码：

代码分析

函数定义：

主函数：

---

快速排序算法

快速排序（QuickSort）是一种高效的排序算法，它采用分治策略，通过选择一个“基准”元素并将其他元素重新排列为两部分，一部分小于基准，另一部分大于基准，然后递归地对这两部分进行排序。快速排序的基本步骤包括：

1. 选择基准：从数组中选择一个元素作为基准。常见的选择方法有选择第一个元素、最后一个元素、随机选择或中间元素。
2. 分区：将数组划分为两部分，使得所有小于基准的元素都在基准的左边，所有大于基准的元素都在基准的右边。分区后，基准元素位于其最终排序位置。
3. 递归排序：对基准元素左边和右边的子数组分别进行快速排序，直到子数组的大小为1或0。

快速排序的平均时间复杂度为O(n log n)，但在最坏情况下，如果每次选择的基准元素都导致极端不平衡的划分，时间复杂度会退化到O(n²)。为了避免最坏情况，可以采用随机化选择基准或“三数取中”策略。

空间复杂度方面，快速排序的空间复杂度主要取决于递归调用的栈空间，平均情况下为O(log n)。

快速排序在实际应用中广泛使用，因为它通常比其他O(n log n)算法更快，且在内存使用上是原地排序算法. 

例题

题目描述

快速排序是一种常见的排序方式，但是你知道这个排序是怎么实现的吗？现在要求你不使用库函数，实现快速排序。

输入格式
第一行输入一个整数 n，表示数列的长度。
第二行输入 n 个数，表示数列中的元素。

输出格式
输出 n 个数，表示排好序的数列。

输入输出样例
输入
4
4 3 2 1

输出
1 2 3 4

样例说明
4 3 2 1
排序结束是
1 2 3 4

具体代码：

#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 - 1; j++) {// 当前元素小于或等于pivotif (arr[j] <= pivot) {i++;    // 增加小于区域的长度swap(&arr[i], &arr[j]);}}swap(&arr[i + 1], &arr[high]);return (i + 1);
}void quickSort(int arr[], int low, int high) {if (low < high) {// pi是分区后的基准元素索引int pi = partition(arr, low, high);// 递归排序基准元素左右两侧的子数组quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}
}int main() {int n;scanf("%d", &n);int arr[n];for (int i = 0; i < n; i++) {scanf("%d", &arr[i]);}quickSort(arr, 0, n - 1);for (int i = 0; i < n; i++) {printf("%d", arr[i]);if (i < n - 1) {printf(" ");}}printf("\n");return 0;
}

代码分析

1. 函数定义：

   • swap：交换两个整数变量的值。
   • partition：选择基准，将数组划分，并返回基准的最终位置。
   • quickSort：递归地进行快速排序。

2. 主函数：

   • 读取输入的n，然后读取n个整数到数组arr中。
   • 调用quickSort函数对arr进行排序。
   • 输出排序后的数组元素。