快捷導(dǎo)航

冒泡排序的原理及java代碼實(shí)現(xiàn)

更新時(shí)間：2016年02月02日 11:33:18 投稿：hebedich

冒泡排序法：關(guān)鍵字較小的記錄好比氣泡逐趟上浮，關(guān)鍵字較大的記錄好比石塊下沉，每趟有一塊最大的石塊沉底。算法本質(zhì)：（最大值是關(guān)鍵點(diǎn)，肯定放到最后了，如此循環(huán)）每次都從第一位向后滾動(dòng)比較，使最大值沉底，最小值上升一次，最后一位向前推進(jìn)

概述

冒泡排序是一種簡(jiǎn)單的排序算法。它重復(fù)地走訪要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的開(kāi)始。

簡(jiǎn)單點(diǎn)說(shuō)，就是：

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

直觀釋義圖：

步驟

比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)。
針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。
實(shí)例

原始數(shù)據(jù)：

3 5 2 6 2
第一輪

比較 3 和 5，5 大于 3 ，不需交換
3 5 2 6 2
繼續(xù)比較 5 和 2，5 大于 2，交換位置
3 2 5 6 2
繼續(xù)比較 5 和 6，6 大于 5，不需交換
3 2 5 6 2
繼續(xù)比較 6 和 2，6 大于 2，交換位置
3 2 5 2 6
6 下沉到最后，兩個(gè)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

四輪結(jié)束

2 2 3 5 6

代碼實(shí)現(xiàn)(Java)

package com.coder4j.main.arithmetic.sorting;

public class Bubble {

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

}

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

第1輪開(kāi)始
第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 
結(jié)果：
3 2 5 2 6 
第2輪開(kāi)始
第2輪，第1次比較：
2 3 5 2 6 
第2輪，第2次比較：
2 3 5 2 6 
第2輪，第3次比較：
2 3 2 5 6 
結(jié)果：
2 3 2 5 6 
第3輪開(kāi)始
第3輪，第1次比較：
2 3 2 5 6 
第3輪，第2次比較：
2 2 3 5 6 
結(jié)果：
2 2 3 5 6 
第4輪開(kāi)始
第4輪，第1次比較：
2 2 3 5 6 
結(jié)果：
2 2 3 5 6 
最終結(jié)果
2 2 3 5 6

經(jīng)測(cè)試，與實(shí)例中結(jié)果一致。

您可能感興趣的文章: