冒泡排序

2021-11-02|来源：|发布者：

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

作为最简单的排序算法之一，冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样，每次都在第一页第一位，所以最熟悉。冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来

1. 算法步骤

1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

3、针对所有的元素重复以上的步骤，除了最后一个。

4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

2. 动图演示

冒泡排序

3. 时间复杂度

若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数和记录移动次数均达到最小值：，。

所以，冒泡排序最好的时间复杂度为。

若初始文件是反序的，需要进行趟排序。每趟排序要进行次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：

冒泡排序的最坏时间复杂度为。

综上，因此冒泡排序总的平均时间复杂度为。

4. 算法实现

冒泡排序C语言

#include <stdio.h>

#define ARR_LEN 255 /*数组长度上限*/
#define elemType int /*元素类型*/

/* 冒泡排序 */
/* 1. 从当前元素起，向后依次比较每一对相邻元素，若逆序则交换 */
/* 2. 对所有元素均重复以上步骤，直至最后一个元素 */
/* elemType arr[]: 排序目标数组; int len: 元素个数 */
void bubbleSort (elemType arr[], int len) {
    elemType temp;
    int i, j;
    for (i=0; i<len-1; i++) /* 外循环为排序趟数，len个数进行len-1趟 */
        for (j=0; j<len-1-i; j++) { /* 内循环为每趟比较的次数，第i趟比较len-i次 */
            if (arr[j] > arr[j+1]) { /* 相邻元素比较，若逆序则交换（升序为左大于右，降序反之） */
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
}

int main (void) {
    elemType arr[ARR_LEN] = {3,5,1,-7,4,9,-6,8,10,4};
    int len = 10;
    int i;
    
    bubbleSort (arr, len);
    for (i=0; i<len; i++)
        printf ("%d	", arr[i]);
    putchar ('\n');
    
    return 0;
}

冒泡排序C++

#include <iostream>
using namespace std;
template<typename T>
//整数或浮点数皆可使用
void bubble_sort(T arr[], int len)
{
    int i, j;  T 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[] = { 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;
}

冒泡排序PHP

function bubbleSort($numbers) {
    $cnt = count($numbers);
    for ($i = 0; $i < $cnt - 1; $i++) {
        for ($j = 0; $j < $cnt - $i - 1; $j++) {
            if ($numbers[$j] > $numbers[$j + 1]) {
                $temp = $numbers[$j];
                $numbers[$j] = $numbers[$j + 1];
                $numbers[$j + 1] = $temp;
            }
        }
    }

    return $numbers;
}

$num = array(20, 40, 60, 80, 30, 70, 90, 10, 50, 0);
var_dump(bubbleSort($num));

//输出结果如下：
//array(10) {
//  [0]=>
//  int(0)
//  [1]=>
//  int(10)
//  [2]=>
//  int(20)
//  [3]=>
//  int(30)
//  [4]=>
//  int(40)
//  [5]=>
//  int(50)
//  [6]=>
//  int(60)
//  [7]=>
//  int(70)
//  [8]=>
//  int(80)
//  [9]=>
//  int(90)
//}

冒泡排序JAVA

    public static void bubbleSort(int arr[]) {

	for(int i =0 ; i<arr.length-1 ; i++) { 
	  
		for(int j=0 ; j<arr.length-1-i ; j++) {  

			if(arr[j]>arr[j+1]) {
				int temp = arr[j];
				
				arr[j]=arr[j+1];
				
				arr[j+1]=temp;
		}
		}    
	}
}

冒泡排序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);

冒泡排序C#语言

namespace 数组排序
{
    class Program
    {
        static void Main(string[] args)
        {
            int temp = 0;
            int[] arr = {23, 44, 66, 76, 98, 11, 3, 9, 7};
            #region该段与排序无关
            Console.WriteLine("排序前的数组：");
            foreach (int item in arr)
            {
                Console.Write(item + "");
            }
            Console.WriteLine();
            #endregion
            for (int i = 0; i < arr.Length - 1; i++)
            {
                #region将大的数字移到数组的arr.Length-1-i
                for (int j = 0; j < arr.Length - 1 - i; j++)
                {
                    if (arr[j] > arr[j + 1])
                    {
                        temp = arr[j + 1];
                        arr[j + 1] = arr[j];
                        arr[j] = temp;
                    }
                }
            #endregion
            }
            Console.WriteLine("排序后的数组：");
            foreach (int item in arr)
            {
                Console.Write(item+"");
            }
            Console.WriteLine();
            Console.ReadKey();
        }
    }
}

冒泡排序Visual Basic语言

Sub maopao()
Dim a = Array(233, 10086, 31, 15, 213, 5201314, 427)
Dim i As Integer, j As Integer

For i = UBound(a) - 1 To 0 Step -1
	For j = 0 To i
		If a(j) > a(j + 1) Then
			a(j) = a(j) + a(j + 1)
			a(j + 1) = a(j) - a(j + 1)
			a(j) = a(j) - a(j + 1)
		End If
	Next j
Next i
For i = 0 To UBound(a)
	Print a(i)
Next i
End Sub

冒泡排序Objective-C

 for (int i = 0; i<result.count-1; i++) {
	for (int j = 0; j<result.count-1-i; j++) {
		NSInteger left = [result[j] integerValue];
		NSInteger right = [result[j+1] integerValue];
		if (left>right) {
			[result exchangeObjectAtIndex:j withObjectAtIndex:j+1];
		}
	}
}
NSLog(@"%@",result);

冒泡排序Python

def bubble(bubbleList):
listLength = len(bubbleList)
while listLength > 0:
	for i in range(listLength - 1):
		if bubbleList[i] > bubbleList[i+1]:
			bubbleList[i], bubbleList[i+1] = bubbleList[i+1], bubbleList[i]
	listLength -= 1
print bubbleList

if __name__ == '__main__':
bubbleList = [3, 4, 1, 2, 5, 8, 0]
bubble(bubbleList)

冒泡排序Python3

def bubble_sort(nums):
for i in range(len(nums) - 1):  # 这个循环负责设置冒泡排序进行的次数
	for j in range(len(nums) - i - 1):  # j为列表下标
		if nums[j] > nums[j + 1]:
			nums[j], nums[j + 1] = nums[j + 1], nums[j]
return nums

print(bubble_sort([45, 32, 8, 33, 12, 22, 19, 97]))
# 输出：[8, 12, 19, 22, 32, 33, 45, 97]

冒泡排序Visual Fox Pro语言

?'Original Array ' + CHR(43147)
DIMENSION arr(10)
FOR i = 1 TO 10
    arr(i) = ROUND(rand()*100,0)
ENDFOR
DISPLAY MEMORY LIKE arr
?'After Sort ' + CHR(43147)
FOR i = 1 TO 10
    FOR j = 1 TO 10 - i
        IF arr(j) > arr(j + 1)
            lnTemp = arr(j)
            arr(j) = arr(j + 1)
            arr(j + 1) = lnTemp
        ENDIF
    ENDFOR
ENDFOR
DISPLAY MEMORY LIKE arr

冒泡排序Swift

func bubbleSort(_ nums: inout [Int]) {
    let n = nums.count
    for i in 0..<n {
        for j in 0..<(n - 1 - i) {
            if nums[j] > nums[j + 1] {
                nums.swapAt(j, j + 1)
            }
        }
    }
    print(nums)
}

var nums = [1,3,7,8,9]
bubbleSort(&nums)

冒泡排序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

冒泡排序Erlang

bubble_sort(L)->
bubble_sort(L,length(L)).

bubble_sort(L,0)->
L;
bubble_sort(L,N)->
bubble_sort(do_bubble_sort(L),N-1).

do_bubble_sort([A])->
[A];
do_bubble_sort([A,B|R])->
caseA<Bof
true->[A|do_bubble_sort([B|R])];
false->[B|do_bubble_sort([A|R])]
end.

冒泡排序Kotlin

fun bubbleSort(array: Array<Int>) { 
	val arrayLength = array.size    
	for (i in 0 until arrayLength) {        
		for (j in 0 until arrayLength - i - 1) {            
			if (array[j] > array[j + 1]) {                
				val temp = array[j]                
				array[j] = array[j + 1]                
				array[j + 1] = temp           
			}       
		}   
	}   
	// Prints result.
 }

冒泡排序Go语言

package main
import (
    "fmt"
)
const (
    LENGTH = 8
)
func main() {
    var tmp int
    number := []int{95, 45, 15, 78, 84, 51, 24, 12}
    for i := 0; i < LENGTH; i++ {
        for j := LENGTH - 1; j > i; j-- {
            if number[j] < number[j-1] {
                tmp = number[j-1]
                number[j-1] = number[j]
                number[j] = tmp
            }
        }
    }
    for i := 0; i < LENGTH; i++ {
        fmt.Printf("%d ", number[i])
    }
    fmt.Printf("\n")
}

冒泡排序GO语言2

func BubbleSort(values []int) {
    flag := true
    vLen := len(values)
    for i := 0; i < vLen-1; i++ {
        flag = true
        for j := 0; j < vLen-i-1; j++ {
            if values[j] > values[j+1] {
                values[j], values[j+1] = values[j+1], values[j]
                flag = false
                continue
            }
        }
        if flag {
            break
        }
    }
}

冒泡排序PASCAL

var
a:array[1..4] of integer;
i, j, temp, n:integer;
begin
read(n);
for i := 1 to n do read(a[i]);
for i := 1 to n do
   for j := 1 to n-i do
	   if a[j] > a[j + 1] then
		   begin
			   temp := a[j];
			   a[j] := a[j + 1];
			   a[j+1] := temp;
		   end;
for i:= 1 to n do write(a[i]);
end.

冒泡排序lua

function sortBubble(list)
	local len = #list
	for i = 1, len do
		for j = 1, len-i do
			if list[j+1]>list[j] then
				local t = list[j+1]
				list[j+1] = list[j]
				list[j] = t
			end
		end
	end
end

冒泡排序汇编

有一个首地址为A的5个有符号数字的数组，请采用“冒泡”排序
DATAS SEGMENT
A  DW 9,4,26,85,38
DATAS ENDS
CODES SEGMENT
ASSUME CS:CODES,DS:DATAS
START:
    MOV AX,DATAS
    MOV DS,AX
    MOV DI,4;初始化外循环次数为数组个数-1
 LP1:MOV CX,DI;外循环次数初值为数组个数-1
     MOV  BX,0;基址初值BX为0
  LP2:MOV AX,A[BX]
    CMP AX,A[BX+2]
    JGE CONT;大于等于不交换
    XCHG AX,A[BX+2];小于交换,AX保存的为较大的数
MOV A[BX],AX;A[BX]保存的为较大的数，准备进行下一次比较,
  CONT:ADD BX,2;基址初值BX+2,字变量，下一个字偏移地址+2
LOOP LP2  ;内循环次数-1,内循环次数是否为0？
    DEC DI;外循环次数-1
    JNZ LP1;外循环次数是否为0?
    MOV AH,4CH
    INT 21H
CODES ENDS
    END START

5. 优化

针对问题：数据的顺序排好之后，冒泡算法仍然会继续进行下一轮的比较，直到arr.length-1次，后面的比较没有意义的。

方案：设置标志位flag，如果发生了交换flag设置为true；如果没有交换就设置为false。这样当一轮比较结束后如果flag仍为false，即：这一轮没有发生交换，说明数据的顺序已经排好，没有必要继续进行下去。

以Java为例

public static void BubbleSort1(int [] arr){
　
　
　   int temp;//临时变量
　
　   boolean flag;//是否交换的标志
　
　   for(int i=0; i<arr.length-1; i++){   //表示趟数，一共 arr.length-1 次
　
　
　       // 每次遍历标志位都要先置为false，才能判断后面的元素是否发生了交换
　
　       flag = false;
　
　       
　
　       for(int j=arr.length-1; j>i; j--){ //选出该趟排序的最大值往后移动
　
　
　           if(arr[j] < arr[j-1]){
　
　               temp = arr[j];
　
　               arr[j] = arr[j-1];
　
　               arr[j-1] = temp;
　
　               flag = true;    //只要有发生了交换，flag就置为true
　
　           }
　
　       }
　
　       // 判断标志位是否为false，如果为false，说明后面的元素已经有序，就直接return
　
　       if(!flag) break;
　
　   }
　
　}

不知

冒泡排序

1. 算法步骤

2. 动图演示

3. 时间复杂度

4. 算法实现

冒泡排序C语言

冒泡排序C++

冒泡排序PHP

冒泡排序JAVA

冒泡排序JavaScript

冒泡排序C#语言

冒泡排序Visual Basic语言

冒泡排序Objective-C

冒泡排序Python

冒泡排序Python3

冒泡排序Visual Fox Pro语言

冒泡排序Swift

冒泡排序RUBY

冒泡排序Erlang

冒泡排序Kotlin

冒泡排序Go语言

冒泡排序GO语言2

冒泡排序PASCAL

冒泡排序lua

冒泡排序汇编

5. 优化