冒泡排序

维基百科,自由的百科全书
跳转至: 导航搜索
冒泡排序
Bubble sort animation.gif
使用冒泡排序為一列數字進行排序的過程
分類 排序算法
數據結構 數組
最差時間複雜度 O(n^2)
最優時間複雜度 O(n)
平均時間複雜度 O(n^2)
最差空間複雜度 总共O(n),需要辅助空间O(1)

冒泡排序Bubble Sort,台灣另外一種譯名為:泡沫排序)是一種簡單的排序算法。它重複地走訪過要排序的數列,一次比較兩個元素,如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換,也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端。

冒泡排序對n個項目需要O(n^2)的比較次數,且可以原地排序。儘管這個演算法是最簡單瞭解和實作的排序算法之一,但它對於少數元素之外的數列排序是很沒有效率的。

冒泡排序是與插入排序擁有相等的執行時間,但是兩種法在需要的交換次數卻很大地不同。在最好的情況,冒泡排序需要O(n^2)次交換,而插入排序只要最多O(n)交換。冒泡排序的實現(類似下面)通常會對已經排序好的數列拙劣地執行(O(n^2)),而插入排序在這個例子只需要O(n)個運算。因此很多現代的演算法教科書避免使用冒泡排序,而用插入排序取代之。冒泡排序如果能在內部迴圈第一次執行時,使用一個旗標來表示有無需要交換的可能,也可以把最好的複雜度降低到O(n)。在這個情況,已經排序好的數列就無交換的需要。若在每次走訪數列時,把走訪順序反過來,也可以稍微地改進效率。有時候稱為雞尾酒排序,因為演算法會從數列的一端到另一端之間穿梭往返。

冒泡排序演算法的運作如下:

  1. 比較相鄰的元素。如果第一個比第二個大,就交換他們兩個。
  2. 對每一對相鄰元素作同樣的工作,從開始第一對到結尾的最後一對。這步做完後,最後的元素會是最大的數。
  3. 針對所有的元素重複以上的步驟,除了最後一個。
  4. 持續每次對越來越少的元素重複上面的步驟,直到沒有任何一對數字需要比較。

由於它的簡潔,冒泡排序通常被用來對於程式設計入門的學生介紹演算法的概念。

虛擬碼[编辑]

function bubblesort (A : list[0..n-1]) {
    var int i, j;
    for i from n-1 downto 0 {
        for j from 0 to i { 
            if (A[j] > A[j+1])
                swap(A[j], A[j+1])
        }
    }
}

助记码[编辑]

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

冒泡排序.jpg

实现技术[编辑]

C语言实现(1)[编辑]

标准C语言程式碼[编辑]

#include <stdio.h>
#define LENGTH 8
int main() {
	int i,j,temp,number[LENGTH]={95,45,15,78,84,51,24,12};
	for(i=0;i<LENGTH;i++)
		for(j=0;j<LENGTH-1-i;j++)
			if(number[j]>number[j+1]) {
				temp=number[j];
				number[j]=number[j+1];
				number[j+1]=temp;
			} //if end
	for(i=0;i<LENGTH;i++) printf("%d ",number[i]);
	puts("");
} //main end

C++语言实现[编辑]

#include <iostream>
#define LENGTH 8
using namespace std;
 
int main() {
	int temp,number[LENGTH]={95,45,15,78,84,51,24,12};
	for(int i=0;i<LENGTH;i++)
		for(int j=0;j<LENGTH-1-i;j++)
			if(number[j]>number[j+1]) {
				temp=number[j];
				number[j]=number[j+1];
				number[j+1]=temp;
			} //if end
	for(int i=0;i<LENGTH;i++) cout<<number[i]<<" ";
	cout<<endl;
} //main end

JAVA语言实现[编辑]

public class BubbleSort {
	public static void main(String[] args) {
		int[] number={95,45,15,78,84,51,24,12};
		int temp=0;
		for(int i=0;i<number.length;i++)
			for(int j=0;j<number.length-1-i;j++)
				if(number[j]>number[j+1]) {
					temp=number[j];
					number[j]=number[j+1];
					number[j+1]=temp;
				} //if end
		for(int i=0;i<number.length;i++) System.out.print(number[i]+" ");
		System.out.println();
	} //main end
} //BubbleSort end

Ruby实现[编辑]

def bubbleSort(array)
  return array if array.size <2
  (array.size-2).downto(0) do |i|
    (0..i).each do |j|
      array[j],array[j+1]=array[j+1],array[j] if array[j]>=array[j+1]
    end
  end
  return array
end

JavaScript实现[编辑]

function bubbleSort(arr){
  var i=arr.length, j;
  var tempExchangVal;
  while(i>0){
    for(j=0;j<i-1;j++){
      if(arr[j]>arr[j+1]){
        tempExchangVal = arr[j];
        arr[j]=arr[j+1];
        arr[j+1]=tempExchangVal;
      }
    }
    i--;
  }
  return arr;
}
var arr = [3,2,4,9,1,5,7,6,8];
var arrSorted = bubbleSort(arr);
console.log(arrSorted);
alert(arrSorted);

控制台将输出:[1, 2, 3, 4, 5, 6, 7, 8, 9]

并且弹窗:

Pascal實現[编辑]

輸入:(在程式同目錄下的文本文件:input.txt)

 一行:等待排序的數(用空格隔開);

 實例:194 638 124 482 469 245 852 294 484 243 623

輸出:(在程式同目錄下的文本文件:output.txt)

 一行:已經排好的數(從小到大);

 實例:124 194 243 245 294 469 482 484 623 638 852

procedure swap(j:longint);  //交換過程
begin
  a[j]:=a[j] xor a[j+1];
  a[j+1]:=a[j] xor a[j+1];
  a[j]:=a[j] xor a[j+1];
end;
 
procedure bubble_sort;  //排序過程
var
  i,j:longint;
  flag:boolean;  //flag標誌:若一次排序未發現數據交換,則說明數據已經有序,可以結束排序過程
begin
  for i:=n-1 downto 1 do begin
    flag:=true;
    for j:=1 to i do begin
      if a[j]>a[j+1] then begin
        swap(j);
        flag:=false;
      end;
    end;
    if flag then exit;
  end;
end;

使用標誌的冒泡排序[编辑]

#include <iostream>
 
using namespace std;
 
void bubble_sort(int d[], int size)
{
	//#假定两两交换发生在数组最后的两个位置#%
	int exchange = size - 1;
 
	while(exchange)
	{
		//#记录下发生数据交换的位置#%
		int bound = exchange;
 
		exchange = 0; //#假定本趟比较没有数据交换#%
 
		for(int i = 0; i < bound; i++)
		{
			if (d[i] > d[i + 1])
			{
				//#交换#%
				int t = d[i];
				d[i] = d[i + 1];
				d[i + 1] = t;
 
				exchange = i;
			}
		}
	}
 
}
 
int main (int argc, char * const argv[])
{
	int a[] = {3, 5, 3, 6, 4, 7, 5, 7, 4}; //#QQ#%
 
	bubble_sort(a, sizeof(a) / sizeof(*a));
 
	//#输出#%
	for(int i = 0; i < sizeof(a) / sizeof(*a); i++)
		cout << a[i] << ' ';
	cout << endl;
 
    return 0;
}

C语言实现(2)[编辑]

typedef.h

#ifndef __TYPEDEF_H__
#define __TYPEDEF_H__
 
#include <stddef.h>
 
enum 
{
	RET_OK,
	RET_FAIL
};
 
typedef int (*DataCompare)(int a, int b);
typedef int (*BubbleSort)(int arr[], size_t count, DataCompare cmp);
 
#ifdef __cplusplus
#define DECLS_BEGIN extern "C" {
#define DECLS_END }
#else
#define DECLS_BEGIN 
#define DECLS_END 
#endif/* __cplusplus */
 
#define DEBUG_PRINT(FORMAT, VALUE) printf("File %s line %d: "\
			#VALUE " = " FORMAT "\n"\
			,__FILE__, __LINE__,VALUE\
			);
 
#define LENGTH(array) (sizeof(array)/sizeof(array[0])) 
 
#define return_if_fail(p) if(!(p)) \
	{printf("%s : %d Warning : "#p" failed.\n",\
	__func__, __LINE__); return ;}
 
#define return_val_if_fail(p, ret) if(!(p))\
	{printf("%s : %d Warning : "#p" failed.\n",\
	__func__, __LINE__); return (ret);}
 
 
#endif/*__TYPEDEF_H__*/

bubble_sort.h

#ifndef __BUBBLE_SORT_H__
#define __BUBBLE_SORT_H__
 
#include "typedef.h"
 
DECLS_BEGIN 
 
int cmp_int(int a, int b);
int cmp_int_invert(int a, int b);
 
int bubble_sort_1(int arr[], size_t count, DataCompare cmp);
int bubble_sort_2(int arr[], size_t count, DataCompare cmp);
int bubble_sort_3(int arr[], size_t count, DataCompare cmp);
int bubble_sort_4(int arr[], size_t count, DataCompare cmp);
 
int bubble_sort(BubbleSort sort, DataCompare cmp ,int arr[], size_t count);
 
DECLS_END
 
#endif

bubble_sort.c

#include <stdio.h>
#include <assert.h>
#include "bubble_sort.h"
#include "typedef.h"
 
#define DEBUG 0
 
int cmp_int(int a, int b)
{
	return a - b;
}
 
int cmp_int_invert(int a, int b)
{
	return b - a;
}
 
/* 
 冒泡排序(1)
 i∈[N-1,0)               //循环N-1遍
   j∈[N-1,N-i-1)         //每遍循环要处理的无序部分
     swap(j,j-1)         //两两排序(升序/降序)
*/
int bubble_sort_1(int arr[], size_t count, DataCompare cmp)
{
#if DEBUG	
	printf("bubble_sort_1:\n");
#endif
	size_t i, j;
	int temp;
 
	if(count < 2)
	{
		return RET_OK;
	}
 
	for(i = count - 1; i > 0; i--)
	{
		for(j = count - 1; j > count - 1 - i; j--)
		{
			if(cmp(arr[j-1], arr[j]) > 0)
			{   
				temp = arr[j];
				arr[j] = arr[j-1];
				arr[j-1] = temp;
			}
		}
	}
 
	return RET_OK;
}
 
/*
 冒泡排序(2)
 i∈[0,N-1)                //循环N-1遍
   j∈[0,N-1-i)            //每遍循环要处理的无序部分
     swap(j,j+1)          //两两排序(升序/降序)
*/
int bubble_sort_2(int arr[], size_t count, DataCompare cmp)
{
#if DEBUG	
	printf("bubble_sort_2:\n");
#endif
	size_t i, j;
	int temp;
 
	if(count < 2)
	{
		return RET_OK;
	}
 
	for(i = 0; i < count - 1; i++)
	{
		for(j = 0; j < count - 1 - i; j++)
		{
			if(cmp(arr[j], arr[j+1]) > 0)
			{   
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			}
		}
	}
 
	return RET_OK;
}
 
/*
 冒泡排序(3)
 i∈[0,N-1)                //循环N-1遍
   j∈[i+1, N)             //每遍循环要处理的无序部分
     swap(i,j)            //两两排序(升序/降序)
*/
int bubble_sort_3(int arr[], size_t count, DataCompare cmp)
{
#if DEBUG	
	printf("bubble_sort_3:\n");
#endif
	size_t i, j;
	int temp;
 
	if(count < 2)
	{
		return RET_OK;
	}
 
	for(i = 0; i < count-1; i++)
	{
		for(j = i+1; j < count; j++)
		{
			if(cmp(arr[i], arr[j]) > 0)
			{   
				temp = arr[j];
				arr[j] = arr[i];
				arr[i] = temp;
			}
		}
	}
 
	return RET_OK;
}
 
/*
  改进的冒泡排序
 right∈[N-1, 0)            //循环N-1遍
   i∈[1, right)            //每遍循环要处理的无序部分
	max = i;
   swap(max, right)             //两两排序(升序/降序)
*/
int bubble_sort_4(int arr[], size_t count, DataCompare cmp)
{
#if DEBUG	
	printf("bubble_sort_4:\n");
#endif
	size_t i = 0;
	size_t max = 0;
	size_t right = 0;
	int temp;
 
	if(count < 2)
	{
		return RET_OK;
	}
 
	for(right = count-1; right > 0; right --)
	{
		for(i = 1, max = 0; i < right; i++)
		{
			if(cmp(arr[i], arr[max]) > 0)
			{
				max = i;
			}
		}
 
		if(cmp(arr[max], arr[right]) > 0)
		{
			temp = arr[max];
			arr[max] = arr[right];
			arr[right] = temp;	
		}
	}
 
	return RET_OK;
}
 
 
int bubble_sort(BubbleSort sort, DataCompare cmp, int arr[], size_t count)
{
#if DEBUG	
	DEBUG_PRINT("%d", count);
#endif
	return_val_if_fail(cmp != NULL && sort != NULL ,RET_FAIL);
	return sort(arr, count, cmp);
}

test.c

#include <stdio.h>
#include <assert.h>
#include "bubble_sort.h"
 
#define DEBUG 0
 
int main(int arc, char* const argv[])
{
	size_t i = 0, n = 0;
	int arr1[] = {5, 4, 1, 3, 6};
	int arr2[] = {5, 4, 1, 3, 6, 10, 9, 8, 7, 2, 2};
	int arr3[] = {5, 4, 1, 3, 6, 10, 2, 8, 7, 2, 7};
	int arr4[] = {6, 1, 2, 3, 3, 10, 2, 9, 8, 2, 7};
 
	//-1-
	n = LENGTH(arr1);
#if DEBUG
	DEBUG_PRINT("%d", n);
#endif
	printf("Before sort:\n");
	for(i = 0; i < n; i++)
		printf("%4d", arr1[i]);
 
	printf("\nAfter sort:\n");
	bubble_sort(bubble_sort_1, cmp_int, arr1, n);
	for(i = 0; i < n; i++)
		printf("%4d", arr1[i]);
	printf("\n");
 
	//-2-
	n = LENGTH(arr2);
#if DEBUG
	DEBUG_PRINT("%d", n);
#endif
	printf("Before sort:\n");
	for(i = 0; i < n; i++)
		printf("%4d", arr2[i]);
 
	printf("\nAfter sort:\n");
	bubble_sort(bubble_sort_2, cmp_int_invert, arr2, n);
	for(i = 0; i < n; i++)
		printf("%4d", arr2[i]);
	printf("\n");
 
	//-3-
	n = LENGTH(arr3);
#if DEBUG
	DEBUG_PRINT("%d", n);
#endif
	printf("Before sort:\n");
	for(i = 0; i < n; i++)
		printf("%4d", arr3[i]);
 
	printf("\nAfter sort:\n");
	bubble_sort(bubble_sort_3, cmp_int, arr3, n);
	for(i = 0; i < n; i++)
		printf("%4d", arr3[i]);
	printf("\n");
 
	//-4-
	n = LENGTH(arr4);
#if DEBUG
	DEBUG_PRINT("%d", n);
#endif
	printf("Before sort:\n");
	for(i = 0; i < n; i++)
		printf("%4d", arr4[i]);
 
	printf("\nAfter sort:\n");
	bubble_sort(bubble_sort_4, cmp_int_invert, arr4, n);
	for(i = 0; i < n; i++)
		printf("%4d", arr4[i]);
	printf("\n");
 
	return 0;
}

Makefile

src = test.c bubble_sort.c
target = test
temp = $(wildcard *~)
all:$(src)
	gcc -g $^ -o $(target)
 
clean:
	rm $(temp) $(target)

Python語言代碼[编辑]

def bubble(List):
    for j in range(len(List)-1,0,-1):
        for i in range(0,j):
            if List[i]>List[i+1]:List[i],List[i+1]=List[i+1],List[i]
    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])

C#语言实现[编辑]

/// <summary>
/// 冒泡排序O(n^2)
/// </summary>
/// <param name="intArray">待排序数组</param>
static void BubbleSort(int[] intArray)
{
    int temp = 0;//存储临时变量
    for (int i = 0; i < intArray.Length; i++)
    {
        for (int j = i - 1; j >= 0; j--)
        {
            if (intArray[j + 1] < intArray[j])
            {
                temp = intArray[j + 1];
                intArray[j + 1] = intArray[j];
                intArray[j] = temp;
            }
        }
    }
}

PHP語言代碼[编辑]

function bubble_sort($arr) {
   $n=count($arr);
   for($i=0;$i<$n-1;$i++){
       for($j=$i+1;$j<$n;$j++) {
           if($arr[$j]<$arr[$i]) {
              $temp=$arr[$i];
              $arr[$i]=$arr[$j];
              $arr[$j]=$temp;
           }
       }
   }
   return $arr;
}

示例:

$test = array(27, 33, 28, 4, 2, 26, 13, 35, 8, 14);
var_export(bubble_sort($test));

輸出: final: array ( 0 => 2, 1 => 4, 2 => 8, 3 => 13, 4 => 14, 5 => 26, 6 => 27, 7 => 28, 8 => 33, 9 => 35, )

外部鏈接[编辑]