大家好，又见面了，我是你们的朋友全栈君。
快速排序
【内推】日常实习和社招也可以简历发送到我邮箱，长期接受简历，部门做搜索产品研发，主要php和go语言！
【2022百度提前批招聘】填写内推码可以免专业笔试，部门直接发起面试，有想去的部门可以发送简历到 927①56零36@qq.com 定向内推，本次招聘不影响正常校招流程，相当于多一次机会，赶紧填写内推码【am8eh4】试试吧！
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
今天看到大神写的一篇快速排序的博客，肃然起敬，觉得原来快速排序这么简单
下面进行简单的试试
快速排序的基本思想是
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.net/148426.html原文链接：https://javaforall.net
