數據結構與算法——冒泡排序

Yang_River 發布于2019-08-16 15:51 / 915人閱讀

摘要：多練練排序算法，不僅能夠讓我們知道一些排序方法的底層實現細節，更能夠鍛煉我們的思維，提升編程能力。排序算法的穩定性一個穩定的排序，指的是在排序之后，相同元素的前后順序不會被改變，反之就稱為不穩定。

1. 導言

因為這是排序算法系列的第一篇文章，所以多啰嗦幾句。

排序是很常見的算法之一，現在很多編程語言都集成了一些排序算法，比如Java 的Arrays.sort()方法，這種方式讓我們可以不在乎內部實現細節而直接調用，在實際的軟件開發當中也會經常使用到。但是站在開發者的角度而言，知其然必須知其所以然。多練練排序算法，不僅能夠讓我們知道一些排序方法的底層實現細節，更能夠鍛煉我們的思維，提升編程能力。現在很多技術面試也會涉及到基本的排序算法，所以多練習是有好處的。

文中涉及到的代碼都是Java實現的，但是不會涉及到太多的Java語言特性，并且我會加上詳細的注釋，幫助你理解代碼并且轉換成你熟悉的編程語言。

常見的排序算法有以下10種：

冒泡排序、選擇排序、插入排序，平均時間復雜度都是O(n²)

希爾排序、歸并排序、快速排序、堆排序，平均時間復雜度都是O(nlogn)

計數排序、基數排序、桶排序，平均時間復雜度都是O(n + k)

在開始具體的排序算法講解之前，先得明白兩個概念：

原地排序：指的是在排序的過程當中不會占用額外的存儲空間，空間復雜度為O(1)。

排序算法的穩定性：一個穩定的排序，指的是在排序之后，相同元素的前后順序不會被改變，反之就稱為不穩定。舉個例子：一個數組 [3，5，1，4，9，6，6，12] 有兩個6（為了區分，我把其中一個 6 加粗），如果排序之后是這樣的：[1，3，4，5，6，6，9，12]（加粗的 6 仍然在前面），就說明這是一個穩定的排序算法。

2. 言歸正傳

冒泡排序的思路其實很簡單，一個數據跟它相鄰的數據進行大小的比較，如果滿足大小關系，就將這兩個數據交換位置。一直重復這個操作，就能將數據排序。

舉個例子，假如有數組 a[3,5,1,4,9,6]，第一次冒泡的操作如下圖所示：

重復進行這個操作，6次冒泡之后，數據排序完成。

根據這個思路，應該能很容易能夠寫出下面的代碼實現冒泡排序：

public class BubbleSort {

    //data表示整型數組，n表示數組大小
    public static void bubbleSort(int[] data, int n){
        //數組大小小于等于1，無須排序
        if (n <= 1) return;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                //如果data[j] > data[j + 1]，交換兩個數據的位置
                if (data[j] > data[j + 1]){
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;
                }
            }
        }
    }
}

但是這個排序算法還可以進行優化，當冒泡操作已經沒有數據交換的時候，說明排序已經完成，就不用在進行冒泡操作了。例如上面的例子，第一次冒泡之后，數據為 [3,1,4,5,6,9]，再進行一次冒泡，數據變為 [1,3,4,5,6,9]，此時已經完成了排序，就可以結束循環了。

所以針對這個數組的排序，上面的代碼需要6次冒泡才能完成，其中有4次都是不需要的。所以可以對代碼進行優化：

public class BubbleSort {

    //優化后的冒泡排序
    //data表示整型數組，n表示數組大小
    public static void bubbleSort(int[] data, int n){
        //數組大小小于等于1，無須排序，返回空
        if (n <= 1) return;
        for (int i = 0; i < n; i++) {
            boolean flag = false;//判斷是否有數據交換

            for (int j = 0; j < n - i - 1; j++) {
                //如果data[j] > data[j + 1]，交換兩個數據的位置
                if (data[j] > data[j + 1]){
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;

                    flag = true;//表示有數據交換
                }
            }
            //如果沒有數據交換，則直接退出循環
            if (!flag) break;
        }
    }
}

好了，冒泡排序的基本思路和代碼都已經實現，最后總結一下：

冒泡排序是基于數據比較的

最好情況時間復雜度是O(n)，最壞情況時間復雜度是O(n²)，平均時間復雜度是O(n²)

冒泡排序是原地排序算法，并且是穩定的。

GPU云服務器云服務器冒泡排序前端冒泡排序冒泡排序代碼 js冒泡排序

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/73741.html

JavaScript 數據結構與算法之美 - 冒泡排序、插入排序、選擇排序

摘要：之所以把冒泡排序選擇排序插入排序放在一起比較，是因為它們的平均時間復雜度都為。其中，冒泡排序就是原地排序算法。所以冒泡排序是穩定的排序算法。選擇排序思路選擇排序算法的實現思路有點類似插入排序，也分已排序區間和未排序區間。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言算法為王。想學好前端，先練好內功，...

canger 2019-08-26 10:15 評論0 收藏0
數據結構與算法（二）：帶你讀懂冒泡排序（Bubble Sorting）

摘要：經過一次冒泡排序，最終在無序表中找到一個最大值，第一次冒泡結束。也是我們后面要說的冒泡排序的優化。冒泡排序只執行第一層循環，而不會執行第二層循環。因此冒泡排序的時間復雜度是。 showImg(https://user-gold-cdn.xitu.io/2019/6/19/16b6f986df6880f9?w=640&h=142&f=gif&s=17175);showImg(https:...

chuyao 2019-08-19 11:46 評論0 收藏0
Java 數據結構與算法系列之冒泡排序

摘要：冒泡排序一種運行效率很低的排序算法，然而雖然排序效率低，確實排序入門很重的算法，因為冒泡排序的思路是最簡單最容易理解的排序算法了。二冒泡排序定義冒泡排序是一種通過兩兩比較相鄰記錄的關鍵字，如果反序則交換，直到沒有反序的記錄為止的交換排序。一、前言相信大部分同學都已經學過數據結構與算法這門課了，并且我們可能都會發現一個現象就是我們所學過的數據結構與算法類的書籍基本都是使用 C 語言來...

1treeS 2019-08-15 17:40 評論0 收藏0
你知道和你不知道的冒泡排序

摘要：用來標示該輪冒泡排序中，數組是否是有序的。適用情況當冒泡算法運行到后半段的時候，如果此時數組已經有序了，需要提前結束冒泡排序。當第一輪冒泡排序結束后，元素會被移動到下標的位置。這篇文章包含了你一定知道的，和你不一定知道的冒泡排序。 gif看不了可以點擊【原文】查看gif。源碼: 【地址】 1. 什么是冒泡排序可能對于大多數的人來說比如我，接觸的第一個算法就是冒泡排序。我看過的很...

Worktile 2019-08-16 18:23 評論0 收藏0
Github標星2w+，熱榜第一，如何用Python實現所有算法

摘要：歸并排序歸并排序，或，是創建在歸并操作上的一種有效的排序算法，效率為大符號。以此類推，直到所有元素均排序完畢。與快速排序一樣都由托尼霍爾提出的，因而也被稱為霍爾選擇算法。 showImg(https://segmentfault.com/img/remote/1460000019096360);編譯：周素云、蔣寶尚學會了Python基礎知識，想進階一下，那就來點算法吧！畢竟編程語言只...

zxhaaa 2019-07-31 10:23 評論0 收藏0