排序算法java实现快速排序

算法魔功 2016-02-02

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]+",");

}

}

}

相关推荐