Java/Go/Python/JS/C 語言實(shí)現(xiàn)冒泡排序算法

說明

冒泡排序（Bubble Sort）又稱為泡式排序，是一種簡(jiǎn)單的排序算法。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素，如果它們的順序錯(cuò)誤就把它們交換過來。即通過遍歷待排序的數(shù)列，一次比較兩個(gè)元素，根據(jù)大小調(diào)換位置，直到把最大的或最小的冒出來。

實(shí)現(xiàn)過程

1. 先建立兩個(gè)循環(huán)，外循環(huán)用于遍歷整個(gè)數(shù)組，內(nèi)循環(huán)遍歷待排序的區(qū)間。
2. 內(nèi)循環(huán)每次都從第一項(xiàng)開始，將該項(xiàng)與待排序的后項(xiàng)逐個(gè)進(jìn)行大小比較，再兩兩交換，將大的數(shù)字冒出來。
3. 重復(fù)第二項(xiàng)，一直到數(shù)組遍歷完。

示意圖

bubble1.png

bubble2.gif

性能分析

平均時(shí)間復(fù)雜度：O(N^2)
最佳時(shí)間復(fù)雜度：O(N)
最差時(shí)間復(fù)雜度：O(N^2)
空間復(fù)雜度：O(1)
排序方式：In-place
穩(wěn)定性：穩(wěn)定

代碼

Java

  // java冒泡排序標(biāo)準(zhǔn)版，更多版本請(qǐng)看源碼文件
  void sort1(int arr[]) {
    int len = arr.length;
    for (int i = 0; i < len; i++) {
      for (int j = 0; j < len - i - 1; j++) {
        // 自左往右每?jī)蓚€(gè)進(jìn)行比較，把大的交換到右側(cè)
        // 逐輪冒出最大數(shù)，已經(jīng)排好序的不要再比較
        if (arr[j] > arr[j + 1]) {
          int tmp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = tmp;
        }
      }
    }
  }

Python

# python冒泡排序標(biāo)準(zhǔn)版，更多實(shí)現(xiàn)版本請(qǐng)查看源文件
def bubble_sort1(arr):
  print('bubble_sort1 from left to right:')
  length = len(arr)
  for i in range(length):
    for j in range(length - i - 1):
      # 自左往右每?jī)蓚€(gè)進(jìn)行比較，把大的交換到右側(cè)
      # 逐輪冒出最大數(shù)，已經(jīng)排好序的不要再比較
      if (arr[j] > arr[j + 1]):
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]

Go

// go冒泡排序標(biāo)準(zhǔn)版，更多版本請(qǐng)查看源文件
func bubbleSort1(list []int) []int {
    var length = len(list)
    for i := 0; i < length; i++ {
        for j := 0; j < length-i-1; j++ {
            if list[j] > list[j+1] {
                var tmp = list[j+1]
                list[j+1] = list[j]
                list[j] = tmp
            }
        }
    }
    return list
}

JS

// js冒泡排序徐標(biāo)準(zhǔn)版，更多實(shí)現(xiàn)版本詳見源碼文件
function bubbleSort1(arr) {
  const len = arr.length
  for (var i = 0; i < len; i++) {
    for (var j = 0; j < len - i - 1; j++) {
      // 自左往右每?jī)蓚€(gè)進(jìn)行比較，把大的交換到右側(cè)
      // 逐輪冒出最大數(shù)，已經(jīng)排好序的不要再比較
      if (arr[j] > arr[j + 1]) {
        ;[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
      }
    }
  }
}

TS

  // TS標(biāo)準(zhǔn)版，其他版本請(qǐng)查看源碼文件
  bubbleSort1(arr: Array<number>) {
    console.log('bubbleSort1 from left to right:')
    const len = arr.length
    for (let i = 0; i < len; i++) {
      for (let j = 0; j < len - i - 1; j++) {
        // 自左往右每?jī)蓚€(gè)進(jìn)行比較，把大的交換到右側(cè)
        // 逐輪冒出最大數(shù)，已經(jīng)排好序的不要再比較
        if (arr[j] > arr[j + 1]) {
          [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
        }
      }
    }
  }

C

// 冒泡排序標(biāo)準(zhǔn)版，更多實(shí)現(xiàn)請(qǐng)看源碼
void bubbleSort1(int arr[], int len)
{

  for (int i = 0; i < len; i++)
  {
    for (int j = 0; j < len - i - 1; j++)
    {
      // 自左往右每?jī)蓚€(gè)進(jìn)行比較，把大的交換到右側(cè)
      // 逐輪冒出最大數(shù)，已經(jīng)排好序的不要再比較
      if (arr[j] > arr[j + 1])
      {
        int tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
      }

    }
  }
}

rust

fn bubble_sort1<T: Ord>(arr: &mut [T]) -> &mut [T] {
  let len = arr.len();

  for i in 0..len {
    for j in 0..len - i - 1 {
      if arr[j] > arr[j + 1] {
        // 可以直接使用swap
        arr.swap(j, j + 1);
      }
    }
  }

  return arr;
}

dart

bubbleSort1(List list) {
  var len = list.length;
  for (var i = 0; i < len; i++) {
    print("no:" + i.toString());
    for (var j = 0; j < len - i - 1; j++) {
      if (list[j] > list[j + 1]) {
        var tmp = list[j + 1];
        list[j + 1] = list[j];
        list[j] = tmp;
      }
    }
  }
  print(list);
}

鏈接

冒泡排序算法源碼：https://github.com/microwind/algorithms/tree/master/sorts/bubblesort

其他排序算法源碼：https://github.com/microwind/algorithms