排序算法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]+",");

}

}

}