c++ 快速排序算法【过程图解】
第一、算法描述
快速排序由C. A. R. Hoare在1962年提出,该算法是目前实践中使用最频繁,实用高效的最好排序算法,
快速排序算法是采用分治思想的算法,算法分三个步骤
1.从数组中抽出一个元素作为基数v(我们称之为划界元素),一般是取第一个、最后一个元素或中间的元素
2.将剩余的元素中小于v的移动到v的左边,将大于v元素移动到v的右边
3.对左右两个分区重复以上步骤直到所有元素都是有排序好。
第二、算法实现
/*序列划分函数*/ int partition(int a[], int p, int r) { int key = a[r];//取最后一个 int i = p - 1; for (int j = p; j < r; j++) { if (a[j] <= key) { i++; //i一直代表小于key元素的最后一个索引,当发现有比key小的a[j]时候,i+1 后交换 exchange(&a[i], &a[j]); } } exchange(&a[i + 1], &a[r]);//将key切换到中间来,左边是小于key的,右边是大于key的值。 return i + 1; } void quickSort(int a[], int p, int r) { int position = 0; if (p<r) { position = partition(a,p,r);//返回划分元素的最终位置 quickSort(a,p,position-1);//划分左边递归 quickSort(a, position + 1,r);//划分右边递归 } } void main() { int d[] = { 6,4,1,8,7,5 }; cout << "输入数组 { 6,4,1,8,7,5 } " << endl; quickSort(d, 0, 5); print_arr(d, 6); }
两个辅助函数:
void exchange(int * a, int* b) { int temp = *a; *a = *b; *b = temp; } void print_arr(int *a, int size) //打印函数 { cout << "打印数组:"; for (int i = 0; i<size; i++) //打印数组 { cout << a[i] << " "; } cout << endl << endl; }
测试输出:
第三、算法图解分析
下面我们来具体分析下程序怎么运行的,
quickSort(d, 0, 5);代表以靠最有一个元素5作为基数,
程序初始化时候p=0,r=5,i=-1,j=0,key=5
通过上图我们观察到:
1.i逐渐增加,它一直代表着小于key=5的最后一个元素,j也在主键增加,一直到key前面一个元素停止
2.此时循环到了最后一个元素7,以5为基数的循环已经结束,此时i=1,a[i+1]=6,交换6和5交换,完成本轮循环
返回i+1=2,依索引2为分界线拆分2个数组,进入递归循环,执行类似上图操作
第四、总结
快速排序之所以快,相比冒泡排序他的交换是跳跃式的,它的最差时间复杂度是O(N2) 和冒泡一样,但是它的平均时间复杂度是O(nlog2N),是一种就地排序算法,
看了很多别人写的算法介绍,还是觉的不够清晰,于是决定自己写一篇博文,希望能帮助需要的人快速理解,文章中的用图是自己画的。
以上这篇c++ 快速排序算法【过程图解】就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持猪先飞。
相关文章
- 作者:Sabine 【导读】本文介绍了C#的四种排序算法:冒泡排序、选择排序、插入排序和希尔排序 冒泡排序 using System; namespace BubbleSorter { public class Bubb...2020-06-25
- 这篇文章主要用实例讲解C#递归算法的概念以及用法,文中代码非常详细,帮助大家更好的参考和学习,感兴趣的朋友可以了解下...2020-06-25
- 这篇文章主要介绍了c++中system("pause")的作用和含义,非常不错,具有参考借鉴价值,需要的朋友参考下吧...2020-04-25
基于BootStrap Metronic开发框架经验小结【八】框架功能总体界面介绍
这篇文章主要介绍了基于BootStrap Metronic开发框架经验小结【八】框架功能总体界面介绍 的相关资料,需要的朋友可以参考下...2016-05-14- 这篇文章主要介绍了C# 16 进制字符串转 int的方法,非常不错,具有参考借鉴价值,需要的朋友可以参考下...2020-06-25
InterlliJ IDEA2020新建java web项目找不到Static Web的解决
这篇文章主要介绍了InterlliJ IDEA2020新建java web项目找不到Static Web的解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-09-02- 这篇文章主要介绍了C#类中static变量用法,实例分析了static变量使用技巧与相关注意事项,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了C#判断一个字符串是否是数字或者含有某个数字的方法,本文给大家介绍的非常详细,具有一定的参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 这篇文章主要给大家介绍C# winform快捷键设置技巧,涉及到C winform快捷键相关知识,对C winform知识感兴趣的朋友可以参考下本篇文章...2020-06-25
- 这篇文章主要介绍了基于Ionic3实现选项卡切换并重新加载echarts,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2020-09-24
- 最近项目不多忙,于是抽点时间巩固下切换窗口问题,感兴趣的朋友跟着小编一起学习吧...2020-06-25
基于BootStrap Metronic开发框架经验小结【六】对话框及提示框的处理和优化
这篇文章主要介绍了基于BootStrap Metronic开发框架经验小结【六】对话框及提示框的处理和优化的相关知识,主要对比说明在Bootstrap开发中用到的这些技术要点,对此文感兴趣的朋友一起学习吧...2016-05-14pytorch绘制并显示loss曲线和acc曲线,LeNet5识别图像准确率
今天小编就为大家分享一篇pytorch绘制并显示loss曲线和acc曲线,LeNet5识别图像准确率,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-05-02- 这篇文章主要为大家详细介绍了PC蓝牙通信C#代码实现,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-06-25
- 这篇文章主要介绍了C#实现带进度条的ListView 的相关资料,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了SpringMVC文件上传原理及实现过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2020-07-15
- 这篇文章主要介绍了C#向线程中传递多个参数的解决方法(两种)的相关资料,非常不错,具有参考借鉴价值,需要的朋友可以参考下...2020-06-25
图文详解Heap Sort堆排序算法及JavaScript的代码实现
这篇文章以图文详解Heap Sort堆排序算法及JavaScript的代码实现,堆排序算法基于类二叉树的堆数据结构,需要的朋友可以参考下...2016-05-05C# MVC模式中应该怎样区分应用程序逻辑(Controller层)和业务逻辑(Model层)?
这篇文章主要介绍了C# MVC模式中应该怎样区分应用程序逻辑(Controller层)和业务逻辑(Model层)?,这也小编做.NET项目时经常思考和让人混乱的一个问题,这篇文章写的挺好,一下清晰了许多,需要的朋友可以参考下...2020-06-25- 这篇文章主要是介绍了.net C# 实现任意List的全组合算法实现代码,需要的朋友可以参考下...2020-06-25