

冒泡排序



冒泡排序

中文名冒泡排序

所属学科计算机科学

算法稳定性稳定排序算法

目录导航

演绎过程

时间复杂度

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

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

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

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

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

算法稳定性

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

算法原理

冒泡排序算法的原理如下：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

冒泡排序流程图

算法代码

public void maopaoSort(int[] array){
    for(int i=array.length-1;i>0;i--){
        boolean flag = false;
        for(int j=0;j array[j+1]){
                int tmp = array[j];
                array[j] = array[j+1];
                array[j+1] = tmp;
                flag = true;
            }
        }
        if(!flag) break;
    }
}

算法描述

C语言

12345678910111213141516171819202122232425262728293031323334

#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\t", arr[i]); putchar ('\n'); return 0;}

Visual Fox Pro语言

1234567891011121314151617

?'Original Array ' + CHR(43147)DIMENSION arr(10)FOR i = 1 TO 10 arr(i) = ROUND(rand()*100,0)ENDFORDISPLAY 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 ENDFORENDFORDISPLAY MEMORY LIKE arr

Python3

123456789

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]

Swift

1234567891011121314

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)

C++

C++语言程序示例如下

12345678910111213141516171819202122232425262728293031323334

#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;}

RUBY

123456789

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 arrayend

PHP

1234567891011121314151617181920212223242526272829303132333435363738394041

C#语言

1234567891011121314151617181920212223242526272829303132333435363738394041

冒泡算法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(); } }}

Erlang

123456789101112131415

JAVA

12345678910111213141516

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; } } } }

Kotlin

12345678910111213

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.}

JavaScript

1234567891011121314151617181920

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

并且弹窗；

Visual Basic语言

1234567891011121314151617

Sub maopao() Dim a = Array(233, 10086, 31, 15, 213, 5201314) 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 iEnd Sub

Objective-C

12345678910

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);

Go语言

123456789101112131415161718192021222324

package mainimport ( "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

1234567891011121314151617

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

12345678910111213141516

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.

Python

123456789101112

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)

汇编

12345678910111213141516171819202122232425

有一个首地址为A的5个有符号数字的数组，请采用“冒泡”排序DATAS SEGMENTA DW 9,4,26,85,38DATAS ENDSCODES SEGMENTASSUME CS:CODES,DS:DATASSTART: 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,字变量，下一个字偏移地址+2LOOP LP2 ;内循环次数-1,内循环次数是否为0？ DEC DI;外循环次数-1 JNZ LP1;外循环次数是否为0? MOV AH,4CH INT 21HCODES ENDS END START

lua

123456789101112

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 endend