Java图解快速排序算法(附源码)
点击上面蓝字onlyserver，关注万人公众号
号内福利：
1.架构师成神之路-最新视频资源-65个课题【免费下载】
2.400多人的微信技术群，干净，没广告，气氛活跃
3.技术文章都是精华文章，助你进步，成长，强大
=长摁关注=
=回复加群进微信技术群=
=回复1024下载视频资源=
先说一下原理：两个指针，分别从数组的首尾开始向中间运动，左指针先运动，左指针指到的数若大于或等于枢纽元则停下来，当左指针停下来的时候，右指针运动，右指针指到的数若小于枢纽元则停下来，此时，交换左右指针指向的数，然后重复上述运动。直到左右指针相遇，运动结束。
比如数组：【7 10 2 4 7 1 8 5 19】， 把7当做基准值：
左指针指到的数等于7，停下来；右指针指向的数大于7，继续走。。。
右指针指向的数为5，小于7，停下来；然后交换两个指针指向的数。。。
然后左指针继续走，走到10，大于7，停下来；然后右指针走，指向8，大于7，继续走，然后走到1，小于7，停下来。。。
然后交换左右两个指针的指向的值。。。
然后左指针继续走，走到2，小于7，继续走，走到4，继续走，走到7，等于7，停；然后右指针走，走到7，和左指针相遇。。。
然后以7位界限，左边的都是小于7的数，右边的都是大于7的数。然后将左边的【5,1,2,4】和右边的【10,8,7,19】看成是两个数组，重复上述的步骤，就可以排成【1,2,4,5,7,7,8,10,19】这样的从小到大的有序数组。
上源码：
package 快速排序;
/**
* 7 10 2 4 7 1 8 5 19
* 1.先找一个数，作为基准，比如7
* 2.左边一个指针，从左向右找，找到大于等于7的就停下来， 找不到就继续走
* 3.右边一个指针，从右向左找，找到小于7的就停下来，找不到就继续走
* 4.左右都停下来以后，交换指针下边的值
* 5.一直到左边的指针碰到右边的指针，算是完成第一遍。
* 6.这样的目的是为了以7为界，把小于7的数都放到左边，把大于7的数都放到右边
* 7.递归上面的操作，把左右分开的两部分，再按上面的步骤来一遍。
* des: 有3个while ,大while里面套着2个小while, 有递归，左右两部分要递归
* 时间复杂度：
* 1.最坏的情况（基准值左边或者右边的序列为空）,复杂度是：On2
* 2.最好的情况（基准值每次都恰好左右数量相等）,复杂度是：Onlogn
* 3.平均的情况
* created by miapoeng on 2021/8/10 14:32
*/
public class QuickSort {
private static void quickSort (int[] arr, int low, int high) {
int i;//左边指针
int j;//右边指针
int temp;//基准值
int t;//用于交换的第三者
//左边指针大于右边指针的时候，不再执行? >=能行吗?
if (low > high) {
return;
}
i = low;//给左边指针赋值(下标)
j = high;//给右边指针赋值(下标)
temp = arr[low];//基准值默认取第一个数
//他俩没相遇，就一直执行
while (i < j) {
//左边指针指的这个数大于等于7就停下， 下于7就继续走
while (arr[i] < temp && i < j) {//&& i < 是必须要加的，否则会报错
i++;
}
//右边指针指的这个数小于7就停下， 大于等于7就继续走
while (arr[j] >= temp && i < j) {
j--;
}
//都停下以后，进行交换
// if (i < j) {
t = arr[j];
arr[j] = arr[i];
arr[i] = t;
// }
}
quickSort(arr, low, j-1);
quickSort(arr, j+1, high);
}
public static void main(String[] args) {
int[] arr = {7, 10, 2, 4, 7, 1, 8, 5, 19, 190};
quickSort(arr, 0, arr.length - 1);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
//1 2 4 5 7 7 8 10 19 190
}
}
评论