废话不多说,先看代码
#define _CRT_SECURE_NO_WARNINGS 1 //快速排序算法,递归求解 #include <stdio.h> void
swap(int* a, int* b) { int c = 0; c = *a; *a = *b; *b = c; } void Compare(int
arr[], int one, int end) { int first = one;//最左边数组下标 int last = end;//最右边数组下标
int key = first;//用于比较的标量(选取最左边第一个元素) if (first >= last) { return; } while
(first < last) { while (first < last && arr[last] >= arr[key])//右边找比标量小的数 {
last--; } while (first < last && arr[first] <= arr[key])//左边找比标量大的数 { first++;
} if(first < last)//分析交换找出来的值 swap(&arr[first], &arr[last]); } if (first ==
last) { int mite = key;//交换标量到它应该到的位置上,重新选取标量 swap(&arr[mite], &arr[last]); }
Compare(arr,one,first-1);//左边递归排序 Compare(arr,first+1,end);//右边递归排序 } int
main() { int arr[] = { 5,4,6,5,2,1}; int i = 0; int len = sizeof(arr) / 4;
Compare(arr,i,len-1);//传第一个和最后一个元素的下标 for (i = 0; i < len; i++) { printf("%d ",
arr[i]); } return 0; }
首先什么是快速排序算法:快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序n 个项目要Ο(nlogn) 次比较。在最坏状况下则需要Ο(n2)
次比较,但这种状况并不常见。事实上,快速排序通常明显比其他 Ο(nlogn) 算法更快,因为它的内部循环(inner
loop)可以在大部分的架构上很有效率地被实现出来。

快速排序的最坏运行情况是 O(n²),比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn),且 O(nlogn)
记号中隐含的常数因子很小,比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以,对绝大多数顺序性较弱的随机数列而言,快速排序总是优于归并排序。

快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)

简单的说,选取一个基准(这里选取第一个数据),与其他数据进行比较,使比它小的在它的前面,比它大的在它的后面。然后再以这个基准为界限分为两部地方(比它大的部分、比它小的部分),分别选取两个部分的基准,再进行比较,比较完后在进行分界,重复下去,直到最后每部分都只有一个数据时,排序结束。

图解-->

代码讲解:<运用递归>

1、首先需要创建数组、数组第一个数据下标,最后一个数据下标三个参数,数组用于储存数据,然后创建一个Compare()用于快速排序函数,最后打印出来就是我们需要的有序数列。
int main() { int arr[] = { 5,4,6,5,2,1}; int i = 0; int len = sizeof(arr) / 4;
Compare(arr,i,len-1);//传第一个和最后一个元素的下标 for (i = 0; i < len; i++) { printf("%d ",
arr[i]); } return 0;
2、Compare()函数创建

这里使用无符号返回类型,因为不需要返回值

为保证数组第一个元素和最后一个元素下标不变,创建first和last两个局部变量记录数组第一个元素和最后一个元素的下标

创建key下标的数据作为基准
void Compare(int arr[], int one, int end) { int first = one;//最左边数组下标 int last
= end;//最右边数组下标 int key = first;//用于比较的标量(选取最左边第一个元素)
3、首先判断数列是否只有一个元素,如果只有一个元素,则函数结束。

4、开始实现函数主要比较部分

4.1、如果选取左边第一个数据为基准,先从右边开始比较,

4.2、从右边第一个数据开始与key进行比较,如果比它大则继续向右比较(last--),直到找到比key小的数据,便停下来。

4.3、此刻开始从左边开始与key比较,如果比key小则继续比较(first++),如果比key大则与右边找到的比key大的数进行交换。然后右边继续找,重复以上步骤。

4.4、直到first>=last时,都停止寻找,并交换此时first下标的数据与key的值

4.5、分治思想,以此时的key下标的数组作为分界,分为比它大的、比它小的两部分,在重复以上步骤,直至只有一个数据为止,停下排序。采用递归求解。
void Compare(int arr[], int one, int end) { int first = one;//最左边数组下标 int last
= end;//最右边数组下标 int key = first;//用于比较的标量(选取最左边第一个元素) if (first >= last) {
return; } while (first < last) { while (first < last && arr[last] >=
arr[key])//右边找比标量小的数 { last--; } while (first < last && arr[first] <=
arr[key])//左边找比标量大的数 { first++; } if(first < last)//分析交换找出来的值 swap(&arr[first],
&arr[last]); } if (first == last) { int mite = key;//交换标量到它应该到的位置上,重新选取标量
swap(&arr[mite], &arr[last]); } Compare(arr,one,first-1);//左边递归排序
Compare(arr,first+1,end);//右边递归排序 }
swap()交换函数,因为需要影响到交换函数外的值,使用指针形参。
void swap(int* a, int* b) { int c = 0; c = *a; *a = *b; *b = c; }

技术
©2019-2020 Toolsou All rights reserved,
Python学习笔记(一)Linux【shell】 shell编程创建一个线程——— Javaweb (3)evo工具使用问题——Degenerate covariance rank, Umeyama alignment is not possibleVMware 16安装centos 7详细教程C语言做一个简易的登陆验证(功能)界面C语言——qsort函数Spring Boot面试必问:自动配置原理Android EditText密码显示隐藏Qt入门教程【基础控件篇】QCalendarWidget日历控件