FavoriteLoading
0

快速排序

快排过程:
首先设置数组第一个元素为基准数,这个数在后面会有很大的用处,此时6为基准数
i j
6 1 2 7 9 3 4 5 10 8
设置两个变量 i 和 j 指向数组的最左边和最右边
先让 j 往右找比6小的数,让 i 往左找比基准数(6)大的数

i j
6 1 2 7 9 3 4 5 10 8
找到了它们的要找的数,此时就可以把它们交换值了

i j
6 1 2 5 9 3 4 7 10 8
i 和 j 的值成功交换
但是交换了一次还远远不够,我们的目标是要将比6小的数全部交换到左边去,比6大的数全部交换到右边去

i j
6 1 2 5 9 3 4 7 10 8

i j
6 1 2 5 4 3 9 7 10 8
此时 j和i 继续一步步移动,直到第一轮交换值结束,最后会面对上图这种情况 ,j 还是要继续往左找

ij
6 1 2 5 4 3 9 7 10 8
i 和 j相遇了,因为 j 先移动的,所以此时找到了一个比6小的数,就可以将他们和基准值(6)交换了

ij
3 1 2 5 4 6 9 7 10 8
此时以基准数6为分界点,6左边的数都小于等于6,6右边的数都大于等于6。回顾一下刚才的过程, j 的使命就是要找小于基准数的数,而 i 的使命就是要找大于基准数的数,
直到i和j碰头为止。现在基准数6已经归位,它正好处在序列的第6位。此时我们已经将原来的序列,以6为分界点拆分成了两个序列,左边的序列是“3 1 2 5 4”,右边的序列是“9 7 10 8”。
接下来还需要分别处理这两个序列。因为6左边和右边的序列目前都还是很混乱的。

所以下面就是递归来大限神威了,只需通过递归分别以同样的方式处理这两个序列就可以完成排序了。

对于递归这种方法,我们没必要深究其中的每一步是怎么进行的,因为很容易陷入混乱,人脑可没有计算机效率那么高,所以只需由里及外,由小到大来做就行了,希望各位看
算法不会看的脑壳飞出去了额。

以下是我的代码:
import java.util.Arrays;
public class Quick {
public static void main(String[] args) {
int []a = {1,2,5,8,4,7,3,9,6,1};
System.out.println(Arrays.toString(a));
sort(a ,0, a.length-1);
System.out.println(Arrays.toString(a));
}
public static void sort(int a[],int left,int right){
/*
* 临时变量i和j 用来存储left和right的值
* 变量temp 用来存储基准数的值,基准值其实就是数组的第一个数
*/
int i,j,t,temp;
/*
* 先设置递归头,s递归的结束条件
*/
if(left>right) return;
i = left;
j = right;
temp = a[left]; //设temp为基准数
/*
* 设置最外围while循环条件为i不等于j,当循环停止时代表i和j相遇(i==j)
* 说明找到了这轮循环将比temp小的值放到了左边,比temp大的值放到了右边
*/
while(i!=j){
//必须要先从右边往左边找比temp小的数,这才能保证i和j相遇时不会先找到一个比temp大的值
while(i=temp){ //循环停止时,j指向比temp小的数
j--;
}
//从左往右找比temp大的数
while(i<j&&a<=temp){ //循环停止时,i指向比temp大的数
i++;
}
if(i<j){ //将i和j指向的值交换
t = a[j];
a[j] = a;
a = t;
}
}
/*
* 此时整个while循环结束,i和j相遇并都指向了一个比temp小的值
*/
a[left] = a; //将a的值和a[left]交换
a = temp;
/*
* 此时数组left至i-1的数是无序的但都比a小,i+1至right的数是无序的但都比a大
*/
sort(a,left,i-1); //将左边无序的数递归
sort(a,i+1,right);//将右边无序的数递归
}
}