冒泡排序算法-算法大全

冒泡排序（英语：Bubble Sort，台湾另外一种译名为：泡沫排序）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序对 {\displaystyle n} n个项目需要O( {\displaystyle n^{2}} n^{2})的比较次数，且可以原地排序。尽管这个算法是最简单了解和实现的排序算法之一，但它对于包含大量的元素的数列排序是很没有效率的。

冒泡排序是与插入排序拥有相等的运行时间，但是两种算法在需要的交换次数却很大地不同。在最坏的情况，冒泡排序需要 {\displaystyle O(n^{2})} O(n^{2})次交换，而插入排序只要最多 {\displaystyle O(n)} O(n)交换。冒泡排序的实现（类似下面）通常会对已经排序好的数列拙劣地运行（ {\displaystyle O(n^{2})} O(n^{2})），而插入排序在这个例子只需要 {\displaystyle O(n)} O(n)个运算。因此很多现代的算法教科书避免使用冒泡排序，而用插入排序取代之。冒泡排序如果能在内部循环第一次运行时，使用一个旗标来表示有无需要交换的可能，也可以把最坏情况下的复杂度降低到 {\displaystyle O(n)} O(n)。在这个情况，已经排序好的数列就无交换的需要。若在每次走访数列时，把走访顺序反过来，也可以稍微地改进效率。有时候称为鸡尾酒排序，因为算法会从数列的一端到另一端之间穿梭往返。

##冒泡排序算法的运作如下：

• 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
• 针对所有的元素重复以上的步骤，除了最后一个。
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
• 由于它的简洁，冒泡排序通常被用来对于程序设计入门的学生介绍算法的概念。

##伪代码

function bubble_sort (array, length) {
    var i, j;
    for(i from 0 to length-1){
        for(j from 0 to length-1-i){
            if (array[j] > array[j+1])
                swap(array[j], array[j+1])
        }
    }
}

函数 冒泡排序 输入 一个数组名称为array 其长度为length 
    i 从 0 到 (length - 1) 
        j 从 0 到 (length - 1 - i) 
            如果 array[j] > array[j + 1] 
                交换 array[j] 和 array[j + 1] 的值 
            如果结束 
        j循环结束 
    i循环结束 
函数结束

##助记码

 i∈[0,N-1)                //循环N-1遍
   j∈[0,N-1-i)            //每遍循环要处理的无序部分
     swap(j,j+1)          //两两排序（升序/降序）

#冒泡排序算法实现示例
##冒泡排序算法C语言实现：

#include <stdio.h>
void bubble_sort(int arr[], int len) {
	int i, j, temp;
	for (i = 0; i < len - 1; i++)
		for (j = 0; j < len - 1 - i; j++)
			if (arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
}
int main() {
	int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
	int len = (int) sizeof(arr) / sizeof(*arr);
	bubble_sort(arr, len);
	int i;
	for (i = 0; i < len; i++)
		printf("%d ", arr[i]);
	return 0;
}

##冒泡排序算法C++实现：

#include <iostream>
#include <algorithm>
using namespace std;
template<typename T> //整数或浮点数皆可使用,若要使用物件(class)时必须设定大于(>)的运算子功能
void bubble_sort(T arr[], int len) {
	int i, j;
	for (i = 0; i < len - 1; i++)
		for (j = 0; j < len - 1 - i; j++)
			if (arr[j] > arr[j + 1])
				swap(arr[j], arr[j + 1]);
}
int main() {
	int arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
	int len = (int) sizeof(arr) / sizeof(*arr);
	bubble_sort(arr, len);
	for (int i = 0; i < len; i++)
		cout << arr[i] << ' ';
	cout << endl;
	float arrf[] = { 17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 };
	len = (int) sizeof(arrf) / sizeof(*arrf);
	bubble_sort(arrf, len);
	for (int i = 0; i < len; i++)
		cout << arrf[i] << ' ';
	return 0;
}

##冒泡排序算法C#实现：

static void BubbleSort(int[] intArray) {
    int temp = 0;
    bool swapped;
    for (int i = 0; i < intArray.Length; i++)
    {
        swapped = false;
        for (int j = 0; j < intArray.Length - 1 - i; j++)
            if (intArray[j] > intArray[j + 1])
            {
                temp = intArray[j];
                intArray[j] = intArray[j + 1];
                intArray[j + 1] = temp;
                if (!swapped)
                    swapped = true;
            }
        if (!swapped)
            return;
    }
}

##冒泡排序算法java实现：

   public static void bubbleSort(int[] arr) {
	int i, j, temp, len = arr.length;
	for (i = 0; i < len - 1; i++)
		for (j = 0; j < len - 1 - i; j++)
			if (arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
	}

##冒泡排序算法Ruby实现：

class Array
  def bubble_sort!
    for i in 0...(size - 1)
      for j in 0...(size - i - 1)
        self[j], self[j + 1] = self[j + 1], self[j] if self[j] > self[j + 1]
      end
    end
    self
  end
end

puts [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70].bubble_sort!

##冒泡排序算法JavaScript实现：

Array.prototype.bubble_sort = function() {
	var i, j, temp;
	for (i = 0; i < this.length - 1; i++)
		for (j = 0; j < this.length - 1 - i; j++)
			if (this[j] > this[j + 1]) {
				temp = this[j];
				this[j] = this[j + 1];
				this[j + 1] = temp;
			}
	return this;
};
var num = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70];
num.bubble_sort();
for (var i = 0; i < num.length; i++)
	document.body.innerHTML += num[i] + " ";

##冒泡排序算法Python实现：

def bubble(List):
    for j in range(len(List)-1,0,-1):
        flag = True
        for i in range(0, j):
            if List[i] > List[i+1]:
                flag = False
                List[i], List[i+1] = List[i+1], List[i]
        if flag:
            return List
    return List

testlist = [27, 33, 28, 4, 2, 26, 13, 35, 8, 14]
print('final:', bubble(testlist))

输出： final: ([2, 4, 8, 13, 14, 26, 27, 28, 33, 35])

##冒泡排序算法PHP实现：

function swap(&$x, &$y) {
	$t = $x;
	$x = $y;
	$y = $t;
}

function bubble_sort(&$arr) {//php的阵列视为基本型别，所以必须用传参考才能修改原阵列
	for ($i = 0; $i < count($arr) - 1; $i++)
		for ($j = 0; $j < count($arr) - 1 - $i; $j++)
			if ($arr[$j] > $arr[$j + 1])
				swap($arr[$j], $arr[$j + 1]);
}

$arr = array(21, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70);
bubble_sort($arr);
for ($i = 0; $i < count($arr); $i++)
	echo $arr[$i] . ' ';

##冒泡排序算法GO实现：

// BubbleSort 冒泡排序. data必须实现sort包中的Interface接口
func BubbleSort(data sort.Interface) {
	n := data.Len()
	for i := 0; i < n-1; i++ {
		isChange := false
		for j := 0; j < n-1-i; j++ {
			if data.Less(j, j+1) {
				data.Swap(j, j+1)
				isChange = true
			}
		}
		if !isChange {
			break
		}
	}
}

调用:

    // declare a array
	// this array must implenet sort.Inerface
	data := sort.IntSlice{22, 34, 3, 40, 18, 4}
	BubbleSort(data)