计算机科学

首页 > 计算机科学

冒泡排序

2018-08-28 09:42:15     所属分类:排序算法
冒泡排序
Bubble sort animation.gif
使用冒泡排序为一列数字进行排序的过程
分类 排序算法
数据结构 数组
最坏时间复杂度
最优时间复杂度
平均时间复杂度
最坏空间复杂度 总共,需要辅助空间
冒泡排序

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

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

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

冒泡排序算法的运作如下:

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

由于它的简洁,冒泡排序通常被用来对于程序设计入门的学生介绍算法的概念。

目录

  • 1 伪代码
  • 2 助记码
  • 3 实现示例
    • 3.1 C语言
    • 3.2 C++
    • 3.3 C#
    • 3.4 JAVA
    • 3.5 Ruby
    • 3.6 JavaScript
    • 3.7 Pascal
    • 3.8 Python
    • 3.9 VB.NET
    • 3.10 PHP
    • 3.11 Rust
    • 3.12 Go
    • 3.13 Swift
  • 4 外部链接

伪代码

function bubble_sort (array, length) {
    var i, j;
    for(i from 0 to length-1){
        for(j from 0 to length-1-i){
            if (arrayj > arrayj+1)
                swap(arrayj, arrayj+1)
        }
    }
}
函数 冒泡排序 输入 一个数组名称为array 其长度为length 
    i 从 0 到 (length - 1) 
        j 从 0 到 (length - 1 - i) 
            如果 arrayj > arrayj + 1 
                交换 arrayj 和 arrayj + 1 的值 
            如果结束 
        j循环结束 
    i循环结束 
函数结束

助记码

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

冒泡排序.jpg

实现示例

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 (arrj > arrj + 1) {
				temp = arrj;
				arrj = arrj + 1;
				arrj + 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 ", arri);
	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 (arrj > arrj + 1)
				swap(arrj, arrj + 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 << arri << ' ';
	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 << arrfi << ' '<<endl;
	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 (intArrayj > intArrayj + 1)
            {
                temp = intArrayj;
                intArrayj = intArrayj + 1;
                intArrayj + 1 = temp;
                if (!swapped)
                    swapped = true;
            }
        if (!swapped)
            return;
    }
}

JAVA

  public static void bubbleSort(int arr) {
    int i, temp, len = arr.length;
    boolean changed;
    do {
      changed = false;
      len-=1;
      for (i = 0; i < len; i++) {
        if (arri > arri + 1) {
          temp = arri;
          arri = arri + 1;
          arri + 1 = temp;
          changed = true;
        }
      }
    } while (changed);
  }
  
  public static void bubbleSort2(Comparable arr) {
        int n = arr.length;
        int newn;
        do {
            newn = 0;
            for (int i = 1; i < n; i++)
                if (arri - 1.compareTo(arri) > 0) {
                    swap(arr, i - 1, i);
                    newn = i;
                }
            n = newn;
        } while (newn > 0);
  }

Ruby

class Array
  def bubble_sort!
    for i in 0...(size - 1)
      for j in 0...(size - i - 1)
        selfj, selfj + 1 = selfj + 1, selfj if selfj > selfj + 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 (thisj > thisj + 1) {
				temp = thisj;
				thisj = thisj + 1;
				thisj + 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 += numi + " ";

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
  aj:=aj xor aj+1;
  aj+1:=aj xor aj+1;
  aj:=aj xor aj+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 aj>aj+1 then begin
        swap(j);
        flag:=false;
      end;
    end;
    if flag then exit;
  end;
end;

Python

def bubble_sorted(iterable):
    new_list = list(iterable)
    list_len = len(new_list)
    for i in range(list_len - 1):
        for j in range(list_len - 1, i, -1):
            if new_listj < new_listj - 1:
                new_listj, new_listj - 1 = new_listj - 1, new_listj
    return new_list

范例:

testlist = 27, 33, 28, 4, 2, 26, 13, 35, 8, 14
print('sorted:', bubble_sorted(testlist))

输出:

sorted: 2, 4, 8, 13, 14, 26, 27, 28, 33, 35

VB.NET

 '泡沫排序由大到小的程式,預先產生一儲存亂數內容的陣列B,使用中斷點check,
  'switch 為自定兩數交換的sub
 
 Dim i, j, count As Integer
 
  For i = 0 To UBound(b) - 1
     Dim check As Boolean = False   '進入排序後設定一布林變數令其初值為false
                          
      For j = 0 To UBound(b) - 1 - i
         If b(j) < b(j + 1) Then switch(b(j), b(j + 1))
 
          check = True    '進行檢查程序,若符合交換條件即進行兩數值交換(呼叫sub程序) 並於交換後
                               '將check的值變更為true(表示有進行交換動作,則此數列尚未呈現最終排列序),
                                 '離開本層for迴圈後再度將check值重設成false
           count += 1         
       Next
 
       If check = False Then Exit For '檢查進入迴圈後是否進行過數值交換,若check值為false,
                                              '則表示排序進行到此時所有數列的值已呈現期望中的順序,
                                               '因此尚未進行完的排序檢查動作可提早結束以提升效率。
                                              
        Next
 
  MsgBox("共經過了" & count & "次排序")

  '泡沫排序由小到大的程式
      
   Dim i, j, count As Integer
  Dim check As Boolean
   
   For i = 0 To UBound(b) - 1
        check=false
        For j = 0 To UBound(b) - 1 - i
           If b(j) > b(j + 1) Then switch(b(j), b(j + 1))
           count += 1
           check = True
        Next
        If chk = False Then Exit For
    Next
  
    MsgBox("共經過了" & count & "次的排序")
   
   '兩數值交換程式
    Private Sub switch(ByRef a as integer, ByRef b as integer)
        Dim c As Integer
        c = a
        a = b
        b = c
    End Sub

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 . ' ';

Rust

fn bubble_sort(a: &mut i32) {
    let mut i = 0;
    let len = a.len();
    while i < len - 1 {
        let mut j = 0;
        while j < len - i - 1 {
            if aj > aj+1 {
                let t = aj;
                aj = aj+1;
                aj+1 = t;
            }
            j += 1;
        }
        i += 1;
    }
}

调用:

    let mut a = 5,4,7,1,9;
    bubble_sort(&mut a);
    println!("{:?}", a);


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)

Swift

 1 import Foundation
 2 
 3     func bubbleSort (arr: inout Int) {
 4         for i in 0..<arr.count - 1 {
 5             for j in 0..<arr.count - 1 - i {
 6                 if arrj > arrj+1 {
 7                     arr.swapAt(j, j+1)
 8                 }
 9             }
10         }
11     }
12 
13 // 测试调用
14 
15 func testSort () {
16         // 生成随机数数组进行排序操作
17         var list:Int = 
18         for _ in 0...99 {
19             list.append(Int(arc4random_uniform(100)))
20         }
21         print("(list)")
22         bubbleSort(arr:&list)
23         print("(list)")
24     }

外部链接

版权声明:本文由北城百科网创作,转载请联系管理获取授权,未经容许转载必究。https://www.beichengjiu.com/computerscience/339829.html

上一篇:臭皮匠排序
下一篇:计数排序
相关推荐