排序算法java实现快速排序
public class QuickSort {
//快速排序:
//基本思想:(分治)
//先从数组中取出一个数作为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 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]+",");
}
}
}