Java - 快速排序

开篇

快速排序 的思想是一种分治的思想，它的思路是选择一个 基准数字 ，通过一次遍历把要排序的数据分割成2个部分，其中1部分的所有数据都比另外一部分的所有数据要小。再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数组变得有序。过程如下:

1. 从数列中挑出一个基准值
2. 将所有比基准值小的摆放在基准前面，所有比基准值大的摆在基准的后面(相同的数可以到任一边)；在这个分区退出之后，该基准就处于数列的中间位置。
3. 递归地把基准前后2个区间的数列再次进行上述的排序,最后达到全局有序

图示过程

快速排序图示.png

Java Code

public class QuickSortDemo {
    public static void main(String[] args) {
        /**
         * 定义一个长度10的数组并给一些随机数
         */
        int[] arr = {11,7,1,33,2,22};
        quickSort(arr,0,5);
    }
    /**
     * 快速排序
     *
     * @param arr 待排序数组
     * @param l 数组的左边界
     * @param r 数组的右边界
     */
    private static void quickSort(int[] arr,int l,int r){
        if (l < r)
        {
            int i,j,x;
            i = l;
            j = r;
            x = arr[i];
            while (i < j)
            {
                while(i < j && arr[j] > x)
                {
                    // 从右向左找第一个小于x的数
                    j--;
                }

                if(i < j){
                    arr[i++] = arr[j];
                }
                while(i < j && arr[i] < x){
                    // 从左向右找第一个大于x的数
                    i++;
                }
                if(i < j){
                    arr[j--] = arr[i];
                }
            }
            arr[i] = x;
            /** 递归调用 */
            quickSort(arr, l, i-1);
            /** 递归调用 */
            quickSort(arr, i+1, r);
        }
    }
}

快速排序时间复杂度与稳定性

快速排序的时间复杂度在最坏情况下是O(N2)，平均的时间复杂度是O(NlgN)。
这句话很好理解：假设被排序的数列中有N个数。遍历一次的时间复杂度是 O(N)，需要遍历多少次呢？至少 lg(N+1) 次，最多 N 次。

1. 为什么最少是lg(N+1)次？快速排序是采用的分治法进行遍历的，我们将它看作一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的定义，它的深度至少是lg(N+1)。因此，快速排序的遍历次数最少是lg(N+1)次。
2. 为什么最多是N次？这个应该非常简单，还是将快速排序看作一棵二叉树，它的深度最大是N。因此，快读排序的遍历次数最多是N次。

快速排序是不稳定的算法，它不满足稳定算法的定义。
算法稳定性 -- 假设在数列中存在 a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！

个人思考

大学里学的最简单的排序就是冒泡排序，实际上快排和它有一些类似的地方，可以看做是冒泡排序的升级版本，冒泡排序的思想是每一次遍历都把最大的数沉下去或者最小的数浮上来。而快排每次遍历都把整个数组划分成2个区间，并且还能找到这2个区间的中间点。一个是把确定的数放2边，一个是把确定的数放中间。