冒泡排序

13651657101 發布于2019-08-14 15:12 / 1647人閱讀

摘要：概述冒泡排序是一種簡單的排序算法。走訪數列的工作是重復地進行直到數列已經排序完成。簡單點說，就是冒泡排序是將比較大的數字沉在數組的后面可以理解為下面，較小的浮在前面上面。

概述

冒泡排序是一種簡單的排序算法。它重復地走訪要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的開始。

簡單點說，就是：

冒泡排序是將比較大的數字沉在數組的后面（可以理解為下面），較小的浮在前面（上面）。

直觀釋義圖：

步驟

比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。

對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。在這一點，最后的元素應該會是最大的數。

針對所有的元素重復以上的步驟，除了最后一個。

持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。

實例

原始數據：

3 5 2 6 2

第一輪

比較 3 和 5，5 大于 3 ，不需交換
3 5 2 6 2
繼續比較 5 和 2，5 大于 2，交換位置
3 2 5 6 2
繼續比較 5 和 6，6 大于 5，不需交換
3 2 5 6 2
繼續比較 6 和 2，6 大于 2，交換位置
3 2 5 2 6

6 下沉到最后，兩個2都分別向上（前）冒出。

第二輪

比較 3 和 2， 3 大于 2，交換位置
2 3 5 2 6
比較 3 和 5， 5 大于 3，不需交換
2 3 5 2 6
比較 5 和 2， 5 大于 2，交換位置
2 3 2 5 6
不需比較 5 和 6

第三輪

比較 2 和 3， 3 大于 2，不需交換
2 3 2 5 6
比較 3 和 2， 3 大于 2，交換位置
2 2 3 5 6
不需比較了

第四輪

比較 2 和 2，不需交換
2 2 3 5 6

四輪結束

2 2 3 5 6

代碼實現(Java)

package com.coder4j.main.arithmetic.sorting;

public class Bubble {

    /**
     * 冒泡排序
     * 
     * @param array
     * @return
     */
    public static int[] sort(int[] array) {
        int temp;
        // 第一層循環表明比較的輪數, 比如 length 個元素,比較輪數為 length-1 次（不需和自己比）
        for (int i = 0; i < array.length - 1; i++) {
            System.out.println("第" + (i + 1) + "輪開始");
            // 第二層循環，每相鄰的兩個比較一次，次數隨著輪數的增加不斷減少，每輪確定一個最大的，不需比較那個最大的
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j + 1] < array[j]) {
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
                System.out.println("第" + (i + 1) + "輪，第" + (j + 1) + "次比較：");
                for (int k : array) {
                    System.out.print(k + " ");
                }
                System.out.println();
            }
            System.out.println("結果：");
            for (int k : array) {
                System.out.print(k + " ");
            }
            System.out.println();
        }
        return array;
    }

    public static void main(String[] args) {
        int[] array = { 3, 5, 2, 6, 2 };
        int[] sorted = sort(array);
        System.out.println("最終結果");
        for (int i : sorted) {
            System.out.print(i + " ");
        }
    }

}

測試輸出結果：

第1輪開始
第1輪，第1次比較：
3 5 2 6 2 
第1輪，第2次比較：
3 2 5 6 2 
第1輪，第3次比較：
3 2 5 6 2 
第1輪，第4次比較：
3 2 5 2 6 
結果：
3 2 5 2 6 
第2輪開始
第2輪，第1次比較：
2 3 5 2 6 
第2輪，第2次比較：
2 3 5 2 6 
第2輪，第3次比較：
2 3 2 5 6 
結果：
2 3 2 5 6 
第3輪開始
第3輪，第1次比較：
2 3 2 5 6 
第3輪，第2次比較：
2 2 3 5 6 
結果：
2 2 3 5 6 
第4輪開始
第4輪，第1次比較：
2 2 3 5 6 
結果：
2 2 3 5 6 
最終結果
2 2 3 5 6

經測試，與實例中結果一致。

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

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

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

數據結構與算法（二）：帶你讀懂冒泡排序（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
JavaScript 數據結構與算法之美 - 冒泡排序、插入排序、選擇排序

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

canger 2019-08-26 10:15 評論0 收藏0
排序算法分析總結（附js實現）

摘要：本文對一些排序算法進行了簡單分析，并給出了的代碼實現。平均時間復雜度不好分析，它是冒泡排序是穩定的排序算法。冒泡排序是原地排序算法原地排序指的是空間復雜度是的排序算法。歸并排序，會將數組從中間分成左右兩部分。本文對一些排序算法進行了簡單分析，并給出了 javascript 的代碼實現。因為本文包含了大量的排序算法，所以分析不會非常詳細，適合有對排序算法有一定了解的同學。本文內容其實不...

liaoyg8023 2019-08-23 17:11 評論0 收藏0
數據結構與算法——冒泡排序

摘要：多練練排序算法，不僅能夠讓我們知道一些排序方法的底層實現細節，更能夠鍛煉我們的思維，提升編程能力。排序算法的穩定性一個穩定的排序，指的是在排序之后，相同元素的前后順序不會被改變，反之就稱為不穩定。 1. 導言因為這是排序算法系列的第一篇文章，所以多啰嗦幾句。排序是很常見的算法之一，現在很多編程語言都集成了一些排序算法，比如Java 的Arrays.sort()方法，這種方式讓我們可...

Yang_River 2019-08-16 15:51 評論0 收藏0
排序（1）：冒泡排序

摘要：一前言冒泡排序是一種交換排序。以升序冒泡排序為例，冒泡排序就是要每趟排序過程中通過兩兩比較相鄰元素，將小的數字放到前面，大的數字放在后面。所以，冒泡排序最好時間復雜度為。因此，冒泡排序的平均時間復雜度為。一、前言冒泡排序是一種交換排序。什么是交換排序呢？解：兩兩比較待排序的關鍵字，并交換不滿足次序要求的那對數，直到整個表都滿足次序要求為止。二、算法思想它重復地走訪要排序的...

CrazyCodes 2019-07-31 10:08 評論0 收藏0