当前位置:网站首页>快速排序基本思路(通俗易懂+例子)「建议收藏」
快速排序基本思路(通俗易懂+例子)「建议收藏」
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
边栏推荐
- MySQL installation and configuration
- Please, stop painting star! This has nothing to do with patriotism!
- 国金证券是国企吗?在国金证券开户资金安全吗?
- Wechat nucleic acid detection appointment applet system graduation design completion (4) opening report
- Détends - toi encore! Ces nouveaux étudiants peuvent s'installer directement à Shanghai
- 微信核酸检测预约小程序系统毕业设计毕设(3)后台功能
- 夜神模擬器+Fiddler抓包測試App
- [golang | grpc] use grpc to realize simple remote call
- 1288_ Implementation analysis of vtask resume() interface and interrupt Security version interface in FreeRTOS
- Enter a valid user name and password in the Microsoft LDAP configuration page, and enter a valid user name in the Microsoft LDAP configuration page
猜你喜欢
RDK仿真实验
Please, stop painting star! This has nothing to do with patriotism!
Wechat applet video sharing platform system graduation design completion (5) assignment
Wechat applet video sharing platform system graduation design completion (6) opening defense ppt
呆错图床系统源码图片CDN加速与破J防盗链功能
Unity学习shader笔记[八十二]增强单通道颜色渲染的黑白处理
Wechat nucleic acid detection appointment applet system graduation design completion (4) opening report
Relax again! These fresh students can settle directly in Shanghai
Simulateur nightGod + application de test de capture de paquets Fiddler
MySQL advanced - transaction and index
随机推荐
Wechat applet video sharing platform system graduation design (2) applet function
A4988与42步进电机
实施阴影介绍
RDK simulation experiment
Wechat nucleic acid detection appointment applet system graduation design completion (4) opening report
exness深度好文:动性系列-黄金流动性实例分析(五)
Renren potential field method
matplotlib的安装教程以及简单调用
Win10 uninstall CUDA
Unity学习shader笔记[八十二]增强单通道颜色渲染的黑白处理
Leetcode interview question 16.11 Diving board
qt的内存映射
[Northwestern Polytechnic University] information sharing of the first and second postgraduate examinations
Babbitt | metauniverse daily must read: can you buy a virtual anchor for 1000 yuan? Is this the live gospel of small businesses or "cutting leeks"
Use dosbox to run the assembly super detailed step "suggestions collection"
UE4 用spline畫正圓
人人工势场法
Leetcode 面试题 16.15. 珠玑妙算
MySQL advanced - transaction and index
vimium映射鍵