1. 快速排序的思想
主要思想还是分治法的思想
- 首先选择一个基数,用作排序的标准
- 其次定义两个小人(变量),分别代表序列的最左边,和最右边
- 然后最关键的是让最右边的人先走!!!碰到小于基数就停下来,最左边的人再走,碰到大于基数就停下来
- 最后交换各自代表的数,然后重复上述动作,直至二人走到同一位置,将当前位置的数与基数进行交换
- 这时候就会发现基数左边的数都比基数小,基数右边的树都比基数大,然后对基数左边和右边的序列重复相同操作
下面上图!!
!!!注:如果让左边先走的话,他找的是比基数大的数,那么就有可能二人在比基数大的数上面碰面,交换位置后出现错误,所以让右边的人先走
2. 上代码
package com.baidu.ueditor;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] arr = {8,4,5,7,1,3,6,2};
int[] newarr = new int[arr.length];
QSort(arr , 0 , arr.length-1);
System.out.println("排序后的序列"+Arrays.toString(arr));
}
public static void QSort(int[] arr , int left , int right){
if(left>right){
return;
}
int i = left;
int j = right;
//定义一个基数,作为基准
int temp = arr[left];
while(i < j){
while(temp<arr[j] && i<j){
j--;
};
while(temp>arr[i] && i<j){
i++;
};
if(i < j){
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
int a = arr[i];
arr[i] = temp;
temp = a;
QSort(arr , left , j - 1);
QSort(arr , j + 1 , right);
System.out.println(Arrays.toString(arr));
}
}
标签:arr,int,快速,右边,排序,基数,left
From: https://www.cnblogs.com/yujiahang/p/18023561