排序算法（五）快速排序

排序算法（五）快速排序

希尔排序是插入排序的升华，这里说的快速排序其实就是冒泡排序的升华？（啥？冒泡排序终于有了出人头地的机会了。。）不过我反正是很难看出来快速排序和冒泡排序之间的关系多的。冒泡排序是相邻的两个值之间进行比较然后进行交换，而快速排序是一种递归的过程。。真心发现不了其中的关系。

快速排序的基本介绍

之前也已经说过了，快速排序是一种不稳定的排序算法，是冒泡排序的一种优化，至于是如何优化的，后面一起看一下子吧。

快速排序的基本思路

希尔排序是将数据分组进行插入排序，那莫非快速排序就是把数据分组进行冒泡排序？其实并不是。

快速排序的思路是：

以当前的数组中的一个元素(一般取第一个元素也就是arr[0])作为基准值，然后将数组变换为左面的数都比基准值小，右值的值都比基准值大，然后对左面的那一块和右面的那一块进行同样方式的快速排序。直到发现待排序的数组的大小只有1的时候就退出。此时数组也就变得有序起来了。

下图中是将数组的最后一个作为基准值的，其实都是一样滴~

这张图是以最左面的值作为基准值的，讲解的也蛮不错的，就是画质太渣了。

可以清楚的看到上面两个快速排序的实现思路是有一点不同的。第一张采用的是移位法，第二张采用的是交换法。所以说，和插入排序，希尔排序一样，快速排序也有两个实现的思路。

快速排序——交换法代码实现

public static void quickSort(int[] arr, int left, int right){
    // 这个是后面的递归的退出的条件
    if (left >= right){
        return;
    }
    int temp = arr[left];// 最左面的值作为基准值
    int l = left;
    int r = right;
    int t;// 用于下面的数据的交换
    // 其实交换用不着额外的变量可以使用异或的操作来进行 a^=b^=a^=b 就可以对整型变量的值进行交换
    while(l < r){
        // 从右面找到比基准值小的下标
        while(l < r && arr[r] >= temp){
            --r;
        }
        t = arr[r];
        arr[r] = arr[l];
        arr[l] = t;
        // 从左面找比基准值大的下标
        while(l < r && arr[l] <= temp){
            ++l;
        }
        t = arr[r];
        arr[r] = arr[l];
        arr[l] = t;
    }
    // 退出的时候 l == r 这是肯定的毕竟每次都是只走一步l和r必定会相遇。相遇的时候arr[l] == temp!
    // 对数组的左面和右面进行同样操作，也就是递归.其实两个if是多余的，上面已经有了退出递归的条件了。不过加上if就可以减少一次递归的次数，何乐而不为呢？
    if (left < l-1){
        quickSort(arr, left, l-1);
    }
    if (l+1 < right){
        quickSort(arr, l+1, right);
    }  
}

public static void quickSort(int[] arr){
    quickSort(arr, 0, arr.length-1);
}

代码说明：

1. 基准值为什么选第一个数？

   其实你要是乐意的话，left到right之间的任意一个值都是可以取的。只要你有本事写出对应的算法就完事了。一般情况下我们是取第一个值(arr[left])或者最后一个值(arr[right])的。

2. 基准值的选择会影响后面的代码？

   这肯定的啊。要不然选个锤子的基准值的。后面我们做的事情就是不停的交换使得基准值位于这样一个位置——左面的值都比他小，右面的值都比他大

3. 这个到底是如何做到的，我看只是只是l和r不停的交换的啊？

   如果你仔细留意我上面的倒数第一张图的话，你会发现虽然是l和r的交换，实际上每次都有基准值的参与。一开始基准值位于arr[l]，我们从右面找到了第一个小于基准值的数，经过第一次的交换我们就可以确定当时r右面的值都是比基准值大的。此时基准值位于arr[r]。我们又从左面找到第一个比基准值大的数，进行第二次交换，基准值的位置又到了arr[l]，此时我们依然可以确定l左面的值都是比基准值小的。如此一来循环往复。我们始终可以确信的是，left到l-1上的值都是比基准值小的，r+1到right上的值都是比基准值大的。直到l和r相遇，基准值位于arr[l]处，他左面的值都比他小，右面的值都比他大。

4. 为什么一开始先从右面开始，也就是说为什么先从右面找第一个小于基准值的数？

   因为一开始选定的基准值是位于arr[left]的吖，如果你选定的是arr[right]作为基准值的话，你就要先从左面开始找大于基准值的数了。如果你选定的是其他位置的话。。你为什么要那么欠呢？如果你不嫌麻烦的话，当我没说。。。

快速排序——移位法代码实现

public static void quickSortPlus(int[] arr, int left, int right) {
        if (left >= right) return; // 此时不用排序
        int temp = arr[left];// 记录基准值。 左面的数都比基准值小，右面的都比基准值大

        int l = left;
        int r = right;
        while (l < r) {
            // 从右面找到比基准值小的数
            while (l < r && arr[r] >= temp) {
                --r;
            }

            // 移动到左面， 此时第一轮的时候基准值被覆盖
            arr[l] = arr[r];

            // 从左面找到比基准值大的数
            while(l < r && arr[l] <= temp) {
                ++l;
            }

            // 将大的数移动到后面，此时后面的那个比基准值小的数被覆盖了
            arr[r] = arr[l];
        }
        // 退出循环的时候l==r 此时这个位置就是temp这个基准值应该插入的位置
        arr[l] = temp;

        // 递归下去对左右两边进行排序
        if (left < l-1){
        quickSortPlus(arr, left, l-1);
            }
            if (l+1 < right){
        quickSortPlus(arr, l+1, right);
        }  
    }

public static void quickSortPlus(int[] arr){
    quickSortPlus(arr, 0, arr.length-1);
}

移位法其实说的已经蛮多的了，这里就不再赘述了。其实代码也就改了几行而已。也么得什么好说的。

快速排序的测试

public static void main(String[] args) {
        int[] arr = new int[80000];
        for (int i = 0; i < arr.length; i++) {
//            arr[i] = (int) (Math.random()*800000);
            arr[i] = new Random().nextInt(800000);
        }
//        System.out.println(Arrays.toString(arr));
        long start_time = System.currentTimeMillis();
        quickSortPlus(arr);
//        quickSort2(arr, 0, arr.length-1);
        long end_time = System.currentTimeMillis();
//        System.out.println(Arrays.toString(arr));
        System.out.println("Time :"+(end_time-start_time)+"ms");

交换法

80,000数据时：

• Time : 14ms
• Time : 23ms
• Time : 25ms

8,000,000数据时：

• Time : 836ms
• Time : 804ms
• Time : 772ms

移位法

80,000数据时：

• Time : 14ms
• Time : 13ms
• Time : 15ms

8000000数据时：

• Time : 734ms
• Time : 848ms
• *Time : 832ms

总结

感觉也没啥好说的，这个快速排序是真的蛮快的了。不过这还并不是最快的，虽然他名字是快速排序。。。至于我一开始提到的那个快速排序是冒泡排序的改进，我是真的没怎么发现这两个算法之前的联系有多么的紧密。你说希尔排序是插入排序的改进，这个我能看出来，快速排序和冒泡排序。。。额，还是我太蠢了吗？看不粗来啊！至少速度上，是看不出来，，，蛤蛤蛤，冒泡排序哭死~~