Java快速排序（Quick Sort）

快速排序（Quick Sort）是基于二分思想，对冒泡排序的一种改进。主要思想是确立一个基数，将小于基数的数字放到基数的左边，大于基数的数字放到基数的右边，然后再对这两部分数字进一步排序，从而实现对数组的排序。

其优点是效率高，时间复杂度平均为O(nlogn)，顾名思义，快速排序是最快的排序算法，耗费的资源少，最佳情况下，空间复杂度为O(logn)，每一次都平分数组的情况，代码较为简单。

其缺点是不稳定，初始序列有序或基本有序时，时间复杂度降为O(n^2)。

例如：

public class Main {
    //快排实现方法
    public static void quickRow(int[] array,int low,int high) {
        int i,j,pivot;
        //结束条件
        if(low >= high) {
            return;
        }
        i = low;
        j = high;
        //选择的节点，这里选择的数组的第一数作为节点
        pivot = array[low];
        while(i<j) {
            //从右往左找比节点小的数，循环结束要么找到了，要么i=j
            while(array[j] >= pivot && i<j) {
                j--;
            }
            //从左往右找比节点大的数，循环结束要么找到了，要么i=j
            while(array[i] <= pivot && i<j) {
                i++;
            }
            //如果i!=j说明都找到了，就交换这两个数
            if(i<j) {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        //i==j一轮循环结束，交换节点的数和相遇点的数
        array[low] = array[i];
        array[i] = pivot;
        //数组“分两半”,再重复上面的操作
        quickRow(array,low,i-1);
        quickRow(array,i+1,high);
    }
    public static void main(String[] args) {
        int[] array = {6,17,38,59,2,10};
        int low = 0,high = array.length-1;
        quickRow(array,low,high);
        for (int i : array){
            System.out.println(i);
        }
    }
}

运行结果如下：

2
6
10
17
38
59