快速排序

快速排序Java实现

* 快速排序

* @author admin

*

*/

public class QuickSort {

    public static void quickSort(int[] array) {

        recQuickSort(array, 0, array.length - 1);

        for (int x : array) {

        System.out.print(x + " ");

        }

     }

    public static void recQuickSort(int[] array, int lower, int upper) {

        if (lower > upper)

        return;

        // 返回子数组基数的下标

        int pivotIndex = partition(array, lower, upper);

        recQuickSort(array, lower, pivotIndex - 1);

        recQuickSort(array, pivotIndex + 1, upper);

    }


    // 划分数组
    public static int partition(int[] array, int lower, int upper) {

        int pivot = array[lower];    // 选取数组第一个元素作为基数

        int left = lower;           // 左指针

        int right = upper;          // 右指针

        while (left < right) {

            // 指针从数组右边开始移动, 寻找到小于基数的元素停止, 要保证左指针下标小于右指针

            while (left < right && array[right] >= pivot)

            right--;

            // 左指针开始移动, 寻找到大于基数的元素停止, 要保证左指针下标小于右指针

            while (left < right && array[left] <= pivot)

            left++;

            // 左右指针停止移动后, 交换它们各自指向的元素

            int temp = array[right];

            array[right] = array[left];

            array[left] = temp;

        } 

        // 左右指针相遇, 把基数元素也就是开始的array[lower]与左右指针共同指向的元素array[right]或array[left]交换位置

        // 此时基数左边的元素都小于它右边的元素都大于它

        array[lower] = array[right];

        array[right] = pivot;

        return right;

    }

    public static void main(String[] args) {

        int[] array = { 6, 3, 7, 2, 5, 1, 3, 9 };

        System.out.println("排序开始");

        long s = System.currentTimeMillis();

        quickSort(array);

        long e = System.currentTimeMillis();

        System.out.println("\n排序结束用时"+(e-s)+"ms");

    }

}