排序算法之快速排序

作者: 阿狸404 | 来源:发表于2018-03-20 16:36 被阅读443次

package com.wang.sort;

/**
 * 快速排序
 * 思路：为每一个基数通过分治思想找到合理位置
 * 
 * @author wxe
 * @since 0.0.1
 */
public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        int i, j, temp, t;
        if (low > high) {
            return;
        }
        i = low;
        j = high;
        // temp就是基准位
        temp = arr[low];
        System.out.println("我是基准："+temp);

        while (i < j) {
            // 先看右边，依次往左递减
            while (temp <= arr[j] && i < j) {
                j--;
            }
            // 再看左边，依次往右递增
            while (temp >= arr[i] && i < j) {
                i++;
            }
            // 如果满足条件则交换
            if (i < j) {
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }

        }
        // 最后将基准为与i和j相等位置的数字交换
        arr[low] = arr[i];
        arr[i] = temp;
        
        // 递归调用左半数组
        quickSort(arr, low, j - 1);
        // 递归调用右半数组
        quickSort(arr, j + 1, high);
    }

    public static void main(String[] args) {
        int[] arr = {6,1,2,7,9,3,4,5,10,8};
        System.out.println("开始");
        quickSort(arr, 0, arr.length - 1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+",");
        }
    }

}

我们来分析一下基本的思路：

基准数为6.png

第一次交换：以6为基准，首先j向前移动，直到遇见比这个基准6小的第一个数为止，然后i向后移动，直到遇见比这个基准数6大的第一个数为止。如图所示：

基准数为6.png

现在我们知道j指向数字5，i指向数字7，我们将这两个数字进行交换，如图所示：

基准数为6.png
第一次交换结束了，首先仍然是j向前移动，直到遇见比这个基准6小的第一个数为止，然后i向后移动，直到遇见比这个基准数6大的第一个数为止。如图所示：
基准数为6.png

现在我们知道j指向数字4，i指向数字9，将两个数字进行交换，如图所示：

图片.png
第二次交换结束了，首先仍然是j向前移动，直到遇见比这个基准6小的第一个数为止，然后i向后移动，直到遇见比这个基准数6大的第一个数为止。如图所示：
基准数为6.png
当j向前移动遇到3停止了，i向后移动也遇到3了，说明i,j相遇了，没有必要再走下去了，这个时候，该是给基数找到了一个新的位置。将基准数与该数进行交换，该数成为新的基准数，而原来的基准数也找到了合适的位置，如图所示：
基准数为6.png
到此为止，第一个基准数找到了合适的位置，此时，我们就需要根据原来的基准数6将数分为两类了，基准数6的数字都是比6小，而基准数6右边的数都是比6大。此时我们需要再以这个基准数为分解将数据分为两部分，并分别对这两部分进行以上步骤的基准数分类。现在我们知道，基准数6分类后的两类数分别为：左边为3,1,2,5,4.右边为9,7,10,8。
接下来我们将通过以上步骤对左边数据为基准数找位置。

基准数为3.png

左边数据第一次交换：以3位基准数，首先仍然是j向前移动，直到遇见比这个基准3小的第一个数为止，然后i向后移动，直到遇见比这个基准数3大的第一个数为止。如图所示：

图片.png
当j遇到数字2时停止，然后i开始移动遇到2发现i,j又相遇了，没有必要再走下去了。这个时候，相当于说明给基准数3找到了合适的位置了。进行交换如图所示：
基准数为3.png

到此为止第二个基准数找到了合适的位置。此时，我们根据基准数3将数据分为两类，左边为2,1，右边为5,4。记下来对这两部分进行以上步骤的基准数分类。
接下来我们将通过以上步骤对左边数据为基准数找位置。

基准数为2.png

左边数据进行交换：以2位基准数，首先仍然是j向前移动，直到遇见比这个基准2小的第一个数为止，然后i向后移动，直到遇见比这个基准数2大的第一个数为止。

图片.png
现在只剩下两个数，如果j向前移动，没有比2小的数了，只有1，所以j保持不动，i向后移动，在数字1处相遇，此时就为基数2找到了合适的位置，同时也找到了新的基数1.两者进行交换，如图所示：
基准数为2.png
现在新的基准数为1，只剩下一个数，没有必要再进行任何处理了。如图所示：

基准数为1.png
接下来我们看看之前3右边数的分类。新的基数为5如图所示：

基准数为5.png
现在又找到了新的基准数4，只有一个数字了，没有必要进行任何处理了。

基准数为4.png

到此为止，我们把最开始基准数为6左边分类所有的数字的基准数都找到了合适的位置.

现在来处理基准数6右边的分类数字，如图所示：

基准数为9.png

第一次交换：j向前移动找到第一个小于基准数9的位置即停止，i向前移动，找到第一个大于基准数9的位置即停止，如图所示：

图片.png
j找到8的时候停止，i指向数字10的时候停止，进行交换，如图所示：
基准数为9.png

第一次交换结束了，j继续向前走，找到8比技术9小，i继续向后走，正好在数字8出相遇，没有必要再走下去了，说明已经为基准数9找到了合适的位置，同时也找打了新的基准数8，两者进行交换，如图所示：

基准数为9.png
现在原来的基准数又把数据分为两部分了，左边为8,7。右边为10。
我们先来为左边的数据进行基准数8找合适位置。

基准数为8.png

j找到的第一个小于基准数8的位置，然后接着i向后移动寻找第一个大于基准数8的位置，正好在数字7相遇，没有必要再走下去，说明为基准数8找到了合适位置，也找打了新的基准数7.两者进行交换，如图所示：

基准数为8.png
到此为止，我们原来的基准数8将数据分类好了。
左边只剩下7，也就是新的基准数，只有一个数字，不需要进行任何处理了。如图所示：

基准数为7.png
再来看看基准数9右边的数据，只剩下数字10也是。如图所示：
基准数为10.png
只剩下一个数字，也是新的基准数10，不需要任何处理了。
到此为止，我们通过快速排序的方法将数字排好序了，如图所示：
图片.png
由上分析可知：我们的基准数分别为：6,3,2,1,5,4,9,8,7,10
因此快速排序的最差时间复杂度是O((n²)，它的平均时间复杂度为O(nlogn)