快速排序算法

算法分析

       它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

        基本步骤：

1. 获得待排序数组a
2. 选取一个合适的数字p(一般来说就选取数组或是子数组的第一个元素)作为排序基准
3. 将待排序数组a中比基准p小的放在p的左边，比基准p大的放在p的右边
4. 从第3步获得的两个子数组sub1跟sub2
5. 判断sub1或sub2中是否只有一个元素，如果只有一个元素则返回此元素，否则就将sub1（或是sub2）代回到第1步中继续执行.

public class QuickSort extends Sort{
     public static void main(String args[]){
         int a[] = {2,,4,6,8,0,1,3,5,7,9};
         printArray(a);
         quickSort(a);
         printArray(a)
     }
     public static void quickSort(int a[]){
        qsort(a,0,a.length-1)
     }
     public static void qsort(int a[],int left,int right){
         int part = partition(a,left,right);
         qsort(a,left,part-1);
         qsort(a,part+1,right);
     }
     public static int partition(int a[],int left,int right){
        int part = a[left];
        while(left < right){
           while(left < right && a[right] >= part){
              right--;
           }
           a[left] = a[right];
           while(left < right && a[left] <= part){
              left++;
           }
           a[right] = a[left];
        }
        a[left] = part;
        return part;
     }
}

    

public class Sort {
	public static void printArray(int[] src){
		System.out.println();
		System.out.print("[");
		for(int i=0;i<src.length;i++){
			System.out.print(" " + src[i] + " ");
		}
		System.out.print("]");
	}
}