快速排序（Java版）

快速排序的原理是选出一个元素A，并将该元素与其他未排序的元素进行比较，把值比A小的元素放在A的左边，把值把A元素大的放在A的右边，以此类推。

快速排序的平均时间复杂度为O(nlogn)， 最好的时间复杂度为O(nlogn)，最坏时间复杂度为O(n^2)。

/**
 * Created by lkmc2 on 2018/2/27.
 */

public class QuickSort {
    
    /**
     * 快速排序
     * @param array 数组
     * @param left 左边起始下标
     * @param right 右边结束下标
     */
    public static void quickSort(int[] array, int left, int right) {
        if (left >= right) return; //左下标大于右下标，方法结束

        int position = partition(array, left, right); //排序好中间元素后获取分界点坐标
        quickSort(array, left, position - 1); //对分界点左边进行快速排序
        quickSort(array, position + 1, right); //对分界点右边进行快速排序
    }

    /**
     * 将数组进行划分
     * 此方法运行完后，left到i位置的元素都将小于value，i到j-1位置的元素都将大于value
     * arr[left + 1...i] < value ，arr[i + 1...j-1] > value
     * @param array 数组
     * @param left 左边起始下标
     * @param right 右边结束下标
     * @return 分界点坐标
     */
    private static int partition(int[] array, int left, int right) {
        int value = array[left]; //取数组第一个元素作为比较对象
        int index = left; //选取最左边的下标作为i

        for (int j = left + 1; j <= right; j++) { //j为进行移动的下标，从第二个元素开始
            if (array[j] < value) { //当j位置的元素的值小于value
                int temp = array[index + 1]; //交换j与index+1位置元素的值
                array[index + 1] = array[j];
                array[j] = temp;
                index++; //index下标加一
            }
        }

        int temp = array[left]; //交换temp与index位置元素的值
        array[left] = array[index];
        array[index] = temp;
        return index; //返回value所在的分界点坐标
    }

    public static void main(String[] args) {
        int[] array = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        quickSort(array, 0, array.length - 1);

        for (int num : array) {
            System.out.print(num + " ");
        }
    }

}

快速排序运行结果