当前位置:网站首页>快速排序基本思路(通俗易懂+例子)「建议收藏」
快速排序基本思路(通俗易懂+例子)「建议收藏」
2022-07-02 16:58:00 【全栈程序员站长】
大家好,又见面了,我是你们的朋友全栈君。
快速排序
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 今天看到大神写的一篇快速排序的博客,肃然起敬,觉得原来快速排序这么简单 下面进行简单的试试
快速排序的基本思想是
1、先从数列中取出一个数作为基准数
2、分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边
3、再对左右区间重复第二步,直到各区间只有一个数
概括来说为 挖坑填数+分治法
下面举例来进行说明,主要有三个参数,i为区间的开始地址,j为区间的结束地址,X为当前的开始的值
第一步,i=0,j=9,X=21
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
21 | 32 | 43 | 98 | 54 | 45 | 23 | 4 | 66 | 86 |
第二步,从j开始由,后向前找,找到比X小的第一个数a[7]=4,此时i=0,j=6,X=21 进行替换
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
4 | 32 | 43 | 98 | 54 | 45 | 23 | 21 | 66 | 86 |
第三步,由前往后找,找到比X大的第一个数a[1]=32,此时i=2,j=6,X=21
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
4 | 21 | 43 | 98 | 54 | 45 | 23 | 32 | 66 | 86 |
第四步,从j=6开始由,由后向前找,找到比X小的第一个数a[0]=4,此时i=2,j=0,X=21,发现j<=i,所以第一回结束
可以发现21前面的数字都比21小,后面的数字都比21大 接下来对两个子区间[0,0]和[2,9]重复上面的操作即可
下面直接给出过程,就步详细解说了
i=2,j=6,X=43
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
4 | 21 | 43 | 98 | 54 | 45 | 23 | 32 | 66 | 86 |
i=4,j=6,X=43
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
4 | 21 | 32 | 98 | 54 | 45 | 23 | 43 | 66 | 86 |
i=4,j=5,x=43
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
4 | 21 | 32 | 43 | 54 | 45 | 23 | 98 | 66 | 86 |
i=5,j=5,x=43
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
4 | 21 | 32 | 23 | 43 | 45 | 54 | 98 | 66 | 86 |
然后被分为了两个子区间[2,3]和[5,9]
…最后排序下去就是最终的答案
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
4 | 21 | 23 | 32 | 43 | 45 | 54 | 66 | 86 | 98 |
总结:
1.i =L; j = R; 将基准数挖出形成第一个坑a[i]。
2.j–由后向前找比它小的数,找到后挖出此数填前一个坑a[i]中。
3.i++由前向后找比它大的数,找到后也挖出此数填到前一个坑a[j]中。
4.再重复执行2,3二步,直到i==j,将基准数填入a[i]中。
代码
class Solution {
public void sort(int left,int right,int[] array) {
if (left>=right) return ;
int start=left;
int end=right;
int flag=left;
while(left<right) {
while ((left<right)&&(array[right]>=array[flag])) {
right--;
}
if (array[right]<array[flag]) {
int tmp=array[right];
array[right]=array[flag];
array[flag]=tmp;
flag=right;
}
while ((left<right)&&(array[left]<=array[flag])) {
left++;
}
if (array[left]>array[flag]) {
int tmp=array[left];
array[left]=array[flag];
array[flag]=tmp;
flag=left;
}
}
sort(start, left-1, array);
sort(left+1, end, array);
}
}
分享一个比较牛逼的学习java的网站,基础知识和架构等都有,连接如下: http://how2j.cn?p=54321
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/148426.html原文链接:https://javaforall.cn
边栏推荐
- Unity learning shader notes [81] simple color adjustment post-processing (brightness, saturation, contrast)
- Leetcode 面试题 16.15. 珠玑妙算
- C# 检测图片是否被旋转并修改到正真的旋转
- Typescript
- 求求你们,别再刷 Star 了!这跟“爱国”没关系!
- Pychar modify pep8 e501 line too long > 0 characters
- Wechat nucleic acid detection appointment applet system graduation design completion (4) opening report
- 微信核酸检测预约小程序系统毕业设计毕设(3)后台功能
- Please, stop painting star! This has nothing to do with patriotism!
- 一款简约PHP个人发卡程序V4.0版本
猜你喜欢
Wechat applet video sharing platform system graduation design completion (5) assignment
Nvidia 显卡 Failed to initialize NVML Driver/library version mismatch 错误解决方案
SteamOS 3.3 Beta 发布,Steam Deck 中文键盘终于来了
巴比特 | 元宇宙每日必读:一千块就能买一个虚拟主播?这是小企业的直播福音还是在“割韭菜”?...
Redis(6)----对象与数据结构
300+篇文献!一文详解基于Transformer的多模态学习最新进展
Relax again! These fresh students can settle directly in Shanghai
Wechat nucleic acid detection appointment applet system graduation design completion (4) opening report
微信小程序视频分享平台系统毕业设计毕设(5)任务书
NVIDIA graphics card failed to initialize nvml driver/library version mismatch error solution
随机推荐
Explain kubernetes network model in detail
Wechat applet video sharing platform system graduation design completion (6) opening defense ppt
Tower safety monitoring system unattended inclination vibration monitoring system
怎么用ps提取图片颜色分析色彩搭配
[Northwestern Polytechnic University] information sharing of the first and second postgraduate examinations
Renren potential field method
哪个券商公司网上开户佣金低又安全又可靠
Pit encountered during installation of laravel frame
Export Excel files using npoi
架构设计——ID生成器「建议收藏」
[Oracle final review] addition, deletion and modification of tablespaces, tables, constraints, indexes and views
RDK仿真实验
SteamOS 3.3 Beta 发布,Steam Deck 中文键盘终于来了
一个优秀程序员可抵五个普通程序员!
微信小程序视频分享平台系统毕业设计毕设(2)小程序功能
Typescript
Chrome officially supports MathML, which is enabled in chromium dev 105 by default
Is Guojin securities a state-owned enterprise? Is it safe to open an account in Guojin securities?
如何开启IDEA的Run Dashboard功能
再放寬!這些應届生,可直接落戶上海