快速排序算法原理及其实现
快速排序算法是典型的分治算法,成功把普通排序的时间复杂度降到O(N*logN).
原理是把数组拆分成2块.每次对每块数组进行粗的排序.最后达到完全排序的效果.
public class Sort {/** * 快速排序 * @param x * @param low * @param high */public void quicksort(int a[],int low,int high){if(low<high){int x = a[high];//按最后一个元素交换int i=low;//初始化iint j=high;while(i<j){while(i<j && a[i]<=x){i++;}a[j]=a[i];while(i<j && a[j]>=x){j--;}a[i]=a[j];}a[j]=x;quicksort(a,low,i-1);//对前半段排序quicksort(a,i+1,high);//对后半段排序}}public static void main(String args[]){Sort st=new Sort();int x[]={6,5,4,3,2,1};st.quicksort(x, 0, x.length-1);for(int i=0;i<x.length;i++){System.out.println(x[i]);}}}