//快速排序：
//基本思想：（分治）
//先从数组中取出一个数作为key值；
//将比这个数小的数全部放在它的左边，
//大于或等于它的数全部放在它的右边，
//对左右两个小数组重复上述步骤，直到各个区间只有1个数
//辅助理解：(挖坑填数)
//初始时：i=0;j=8;key=6
//由于已经将a[0]中的数保存到key中，可以理解成在数组a[0]上挖了个坑，可以将其他数据填充到这里来。
//从j开始向前查找一个比key小的数，当j=8,符合条件，a[0]=a[8];i++;
//将a[8]挖出再填上一个坑a[0]中。
//这样一个坑a[0]就被搞定了，单有形成了一个新坑a[8]。
//再找个数字来天a[8]这个坑，
//这次从i开始向后找一个大于key的数，当i=4,符合条件，a[8]=a[4];j--;将a[4]挖出填到上一个坑中。
//此时i=4;j=8;key=6;
//再重复上面的步骤，先从后向前找，再从前向后找
//从j开始向前找，当j=5时符合条件，将a[5]挖出填到上一个坑中，a[3]=a[5];i++;
//从i开始向后查找，当i=5时，由于i==j退出，此时i=j=5,而a[5]刚好是上次挖的坑，将key填入a[5]
//最终可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它，然后再对a[0]到a[4]、a[6]到a[8]这两个子区间重复上述步骤
//注意：key值的选取可以有多重形式，例如中间数或者随机数，分别对算法的复杂度产生不同的影响。
//平均时间复杂度:O(nlogn)
public class QuickSort {
public static void main(String[] args) {
int[] arr = new int[]{6,2,4,1,9,3,6,7,0};
System.out.println("排序前=====");
print(arr);
System.out.println("");
System.out.println("排序后=====");
quickSort(arr,0,arr.length-1);
print(arr);
}
public static void quickSort(int[] arr,int left,int right){
if(left>=right)
return ;
int i = left;
int j = right;
int key = arr[left];//选择第一个数作为key
while(i<j){
while(i<j && arr[j]>=key)//从右向左找
j--;
if(i<j){
arr[i] = arr[j];
i++;
}
while(i<j && arr[i]<key)//从左向右找
i++;
if(i<j){
arr[j] = arr[i];
j--;
}
}
//i=j
arr[i] = key;
quickSort(arr,left,i-1);//递归调用
quickSort(arr,i+1,right);//递归调用
}
public static void print(int[] arr){
for(int i=0; i<arr.length; i++){
System.out.print(arr[i]+",");
}
}
}
网友评论