💓博主CSDN主页:杭电码农-NEO💓
⏩专栏分类:八大排序专栏⏪
🚚代码仓库:NEO的学习日记🚚
🌹关注我🫵带你学习排序知识
🔝🔝
1. 前言🏁
博主第一次听见这个排序的时候
只觉得它很嚣张.别人都叫:
插入,希尔,归并排序,凭什么你叫快排
你到底有多快?心里是这个表情
但是当我学习完快排的思想
并且用三种方法写出代码后
博主只想说这是什么神仙思想
想出此方法的人定非 常人也!
废话不多说,上硬菜!
2. 快速排序基本思想🏁
基本思想:
- 从待排序的数组中选取一个基准值.
(我们把基准值记为key) - 再将数组分为两部分:
1. 左子数组所有元素小于基准值
2. 右子数组所有元素大于基准值 - 左右子数组再选基准值重复这个过程
对基准值选取的思考:
一般把数组第一个或
最后一个元素作为基准值
但是这样做有一定的缺陷
后面遇见问题了再修正
3. 快排思想实现(hoare版本)🏁
hoare版本:(发明者叫:C. A. R. Hoare )
也就是发明快排的人想出的方法
我们先定义一个无序数组:
int a[10]={6,1,2,7,9,3,4,5,10,8}; • 1
思路详解:
- 将第一个元素6作为基准值
- 定义两个指针指向:第一和最后的位置
- 左边的指针(L)找比基准值大的值
- 右边的指针( R)找比基准值小的值
- R先走.R找到满足要求的值后停下
- L再走,找到满足要求的值后停下
- 当L和R都停下,交换两个位置数据
- 当L和R相等时:
交换当前位置与基准值的值.
听起来比较抽象,我们画图理解一下:
走完一次循环后,数组变成了这样:
基准值的左边全部小于它
基准值的右边全部大于它
这说明这个基准值6
已经放在了数组中的正确位置!
也就是最终排好序的位置
我们只要不断递归左右子数组
最终这个数组就会变成有序!
