算法01 七大排序之：冒泡排序和快速排序

作者：nnngu
GitHub：https://github.com/nnngu
博客園：http://www.cnblogs.com/nnngu
簡(jiǎn)書：http://www.itdecent.cn/users/1df20d76ea5c
知乎：https://www.zhihu.com/people/nnngu/posts

排序是我們生活中經(jīng)常會(huì)面對(duì)的問題。同學(xué)們做操時(shí)會(huì)按照從矮到高排列；老師查看上課出勤情況時(shí)，會(huì)按學(xué)生學(xué)號(hào)順序點(diǎn)名；高考錄取時(shí)，會(huì)按成績(jī)總分降序依次錄取等。排序是數(shù)據(jù)處理中經(jīng)常使用的一種重要的運(yùn)算，它在我們的程序開發(fā)中承擔(dān)著非常重要的角色。

排序分為以下四類共七種排序方法：

交換排序：

① 冒泡排序

② 快速排序

選擇排序：

③ 直接選擇排序

④ 堆排序

插入排序：

⑤ 直接插入排序

⑥ 希爾排序

合并排序：

⑦ 合并排序

這篇文章主要總結(jié)的是交換排序（即冒泡排序和快速排序），交換排序的基本思想是：兩兩比較待排序元素，如果發(fā)現(xiàn)兩個(gè)元素的次序相反時(shí)即進(jìn)行交換，直到所有元素都沒有反序時(shí)為止。我會(huì)從以下幾個(gè)方面進(jìn)行總結(jié)：

1、冒泡排序及算法實(shí)現(xiàn)

2、快速排序及算法實(shí)現(xiàn)

3、冒泡排序VS快速排序

1、冒泡排序及算法實(shí)現(xiàn)

什么是冒泡排序呢？冒泡排序是一種簡(jiǎn)單的排序方法，它的基本思想是：通過(guò)相鄰兩個(gè)元素之間的比較和交換，使較大的元素逐漸從前面移向后面（升序），就像水底下的氣泡一樣逐漸向上冒泡，所以被稱為“冒泡”排序。冒泡排序的最壞時(shí)間復(fù)雜度為O(n2)，平均時(shí)間復(fù)雜度為O(n2)

下面以一張圖來(lái)展示冒泡排序的全過(guò)程，其中方括號(hào)內(nèi)為下一輪要排序的元素，方括號(hào)后面的第一個(gè)元素為本輪排序浮出來(lái)的最大元素。

1-1、示意圖

1-2、代碼

冒泡排序算法的代碼實(shí)現(xiàn)：

BubbleSort.java

public class BubbleSort {
    public static void main(String[] args) {
        int[] list = {36, 28, 45, 13, 67, 37, 18, 56};
        System.out.println("************冒泡排序************");
        System.out.println("排序前：");
        display(list);

        System.out.println("排序后：");
        bubbleSort(list);
        display(list);
    }

    /**
     * 遍歷打印
     */
    public static void display(int[] list) {
        System.out.println("********展示開始********");
        if (list != null && list.length > 0) {
            for (int num :
                    list) {
                System.out.print(num + " ");
            }
            System.out.println("");
        }
        System.out.println("********展示結(jié)束********");
    }

    /**
     * 冒泡排序算法
     */
    public static void bubbleSort(int[] list) {
        int temp;
        // 做多少輪排序（最多l(xiāng)ength-1輪）
        for (int i = 0; i < list.length - 1; i++) {
            // 每一輪比較多少個(gè)
            for (int j = 0; j < list.length - 1 - i; j++) {
                if (list[j] > list[j + 1]) {
                    // 交換次序
                    temp = list[j];
                    list[j] = list[j + 1];
                    list[j + 1] = temp;
                }
            }
        }
    }
}

測(cè)試結(jié)果：

2、快速排序及算法實(shí)現(xiàn)

快速排序(Quick Sort) 是對(duì)冒泡排序的一種改進(jìn)方法，在冒泡排序中，進(jìn)行元素的比較和交換是在相鄰元素之間進(jìn)行的，元素每次交換只能移動(dòng)一個(gè)位置，所以比較次數(shù)和移動(dòng)次數(shù)較多，效率相對(duì)較低。而在快速排序中，元素的比較和交換是從兩端向中間進(jìn)行的，較大的元素一輪就能夠交換到后面的位置，而較小的元素一輪就能交換到前面的位置，元素每次移動(dòng)的距離較遠(yuǎn)，所以比較次數(shù)和移動(dòng)次數(shù)較少，速度較快，故稱為“快速排序”。

快速排序的基本思想是：通過(guò)一輪排序?qū)⒋判蛟胤指畛瑟?dú)立的兩部分， 其中一部分的所有元素均比另一部分的所有元素小，然后分別對(duì)這兩部分的元素繼續(xù)進(jìn)行快速排序，以此達(dá)到整個(gè)序列變成有序序列?？焖倥判虻淖顗臅r(shí)間復(fù)雜度為O(n2)，平均時(shí)間復(fù)雜度為O(n*log2n)

2-1、示意圖

2-2、代碼

快速排序算法的代碼實(shí)現(xiàn)：

QuickSort.java

public class QuickSort {
    public static void main(String[] args) {
        int[] list = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
        System.out.println("************快速排序************");
        System.out.println("排序前：");
        display(list);

        System.out.println("排序后：");
        quickSort(list, 0, list.length - 1);
        display(list);
    }

    /**
     * 快速排序算法
     */
    public static void quickSort(int[] list, int left, int right) {
        if (left < right) {
            // 分割數(shù)組，找到分割點(diǎn)
            int point = partition(list, left, right);

            // 遞歸調(diào)用，對(duì)左子數(shù)組進(jìn)行快速排序
            quickSort(list, left, point - 1);
            // 遞歸調(diào)用，對(duì)右子數(shù)組進(jìn)行快速排序
            quickSort(list, point + 1, right);
        }
    }

    /**
     * 分割數(shù)組，找到分割點(diǎn)
     */
    public static int partition(int[] list, int left, int right) {
        // 用數(shù)組的第一個(gè)元素作為基準(zhǔn)數(shù)
        int first = list[left];
        while (left < right) {
            while (left < right && list[right] >= first) {
                right--;
            }
            // 交換
            swap(list, left, right);

            while (left < right && list[left] <= first) {
                left++;
            }
            // 交換
            swap(list, left, right);
        }
        // 返回分割點(diǎn)所在的位置
        return left;
    }

    /**
     * 交換數(shù)組中兩個(gè)位置的元素
     */
    public static void swap(int[] list, int left, int right) {
        int temp;
        if (list != null && list.length > 0) {
            temp = list[left];
            list[left] = list[right];
            list[right] = temp;
        }
    }

    /**
     * 遍歷打印
     */
    public static void display(int[] list) {
        System.out.println("********展示開始********");
        if (list != null && list.length > 0) {
            for (int num :
                    list) {
                System.out.print(num + " ");
            }
            System.out.println("");
        }
        System.out.println("********展示結(jié)束********");
    }
}

測(cè)試結(jié)果：

3、冒泡排序VS快速排序

代碼如下：

BubbleVsQuick.java

public class BubbleVsQuick {

    public static void main(String[] args) {
        testQuick();
        testBubble();
    }

    /**
     * 測(cè)試快速排序耗費(fèi)的時(shí)間
     */
    public static void testQuick() {
        int[] list = new int[10000];
        for (int i = 0; i < 10000; i++) {
            list[i] = (int) (Math.random() * 100000);
        }

        // 快速排序
        long start = System.currentTimeMillis();
        QuickSort.quickSort(list, 0, list.length - 1);
        long end = System.currentTimeMillis();
        System.out.println("快速排序耗費(fèi)的時(shí)間：" + (end - start));
        display(list);
    }

    /**
     * 測(cè)試冒泡排序耗費(fèi)的時(shí)間
     */
    public static void testBubble() {
        int[] list = new int[10000];
        for (int i = 0; i < 10000; i++) {
            list[i] = (int) (Math.random() * 100000);
        }

        // 冒泡排序
        long start = System.currentTimeMillis();
        BubbleSort.bubbleSort(list);
        long end = System.currentTimeMillis();
        System.out.println("冒泡排序耗費(fèi)的時(shí)間：" + (end - start));
        display(list);
    }

    /**
     * 遍歷打印前10個(gè)數(shù)
     */
    public static void display(int[] list) {
        System.out.println("********排序之后的前10個(gè)數(shù)start********");
        if (list != null && list.length > 0) {
            for (int i = 0; i < 10; i++) {
                System.out.print(list[i] + " ");
            }
            System.out.println("");
        }
        System.out.println("********排序之后的前10個(gè)數(shù)end**********");
        System.out.println("");
    }
}

測(cè)試結(jié)果：

可見，快速排序的速度比冒泡排序更快。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容