❤️C语言快速排序算法 ❤️
❤️快速排序算法（QSort，快排）及C语言实现[*]
[*]
[*]1.定义
[*]2.基本思想
[*]3.步骤
[*]4.代码实现
[*]5.总结
[*]
本节介绍一种排序算法——快速排序算法（Quick Sort）。
C语言中自带函数库中就有快速排序——qsort函数 ，包含在 <stdlib.h> 头文件中。
1.定义
快速排序由C. A. R. Hoare在1962年提出。快速排序是对冒泡排序的一种改进，采用了一种分治的策略。
2.基本思想
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
3.步骤
a. 先从数列中取出一个数作为基准数。
b. 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
c. 再对左右区间重复第二步，直到各区间只有一个数。
4.代码实现
#define _CRT_SECURE_NO_WARNINGS 1#include <stdio.h>#include <string.h>#include <time.h>#include <stdlib.h>//两数交换void swap(int arr[], int i, int j) {if (i != j) { arr = arr ^ arr; arr = arr ^ arr; arr = arr ^ arr;}}//这是一个处理arr的函数//默认以arr做划分，arr -> p<p==p>p//返回等于区域（左边界，右边界），返回一个长度为而的数组res, res,resint* partition(int arr[],int L, int R) {int less = L - 1;// <区域右边界int more = R;// >区域左边界static int res;//返回数组while (L < more ){//L表示当前数的位置 arr -> 划分值 if (arr < arr) {//当前数小于划分值 swap(arr, ++less, L++); } else if (arr > arr) {//当前数大于划分值 swap(arr, --more, L); }else { L++; }}swap(arr, more, R);res = less + 1;res = more;return res;}//arr排序void quickSort(int arr[], int L, int R) {if (L < R) { swap(arr, (int)(L + (rand() % (R - L + 1))),R);//取随机位数与最后一位交换，将算法的时间复杂度优化为O(nlogn) int *p = partition(arr, L, R); quickSort(arr, L, p - 1);// < 区 quickSort(arr, p + 1, R);// > 区}}void quick(int arr[], int length) {if (length < 2) { return;}quickSort(arr, 0, length - 1);}int main() {int arr[] = {49,38,65,97,76,13,27 };int length = sizeof(arr) / sizeof(arr);printf("排序前：");for (int i = 0; i < length; i++) { printf("%d\t", arr);}time_t start_t = time(NULL);//开始执行时间mergeSort(arr, length);time_t end_t = time(NULL);int t = time(&end_t) - time(&start_t);printf("\n执行耗时：%d ms\n排序后：", t);for (int i = 0; i < length; i++) { printf("%d\t",arr);}return 0;}运行结果为：
5.总结
快速排序算法的时间复杂度为O(nlogn)，是所有时间复杂度相同的排序方法中性能最好的排序算法。
作者：香芋味的猫丶
https://blog.51cto.com/u_14284202/4773074
页:
[1]