快速排序

morewindows的快速排序讲解，非常好

不稳定
O（N*LogN）

package sort;
//快速排序
public class QuickSort {

    public static void main(String[] args) {

        int[] array = { 72, 6, 57, 88, 60, 42, 83, 73, 48, 85 };
        int[] arr1 = { 65, 66, 67, 68, 69, 70, 71, 72, 73, 74 };
        quickSort(array, 0, array.length-1);
//      int partition = partition(arr1, 0, arr1.length - 1);
//      System.out.println("partition:" + partition);
//      for (int i : arr1) {
//          System.out.println(i);
//      }

         int partition = partition(array, 0, array.length-1);
         System.out.println("partition:"+partition);
         for (int i : array) {
         System.out.println(i);
         }
        
    }

    static void quickSort(int[] array, int begin, int end) {
        if (begin < end) {
            int i = partition(array, begin, end);
            quickSort(array, begin, i - 1);
            quickSort(array, i + 1, end);
        }

    }

    static int partition(int[] array, int start, int end) {

        int low = start;
        int high = end;

        int key = array[low];

        while (low < high) {

            while (low < high && array[high] >= key)
                high--;

            if (low < high) {
                array[low] = array[high];
                low++;
            }

            while (low < high && array[low] <= key)
                low++;

            if (low < high) {
                array[high] = array[low];
                high--;
            }
        }
        array[low] = key;
        return low;
    }
}