冒泡排序算法及各種程序示例打賞

冒泡排序(BubbleSort)的基本概念是:

依次比較相鄰的兩個數,將小數放在前面,大數放在后面。
即在第一趟:首先比較第1個和第2個數,將小數放前,大數放后。然后比較第2個數和第3個數,將小數放前,大數放后,如此繼續,直至比較最后兩個數,將小數放前,大數放后。至此第一趟結束,將最大的數放到了最后。

在第二趟:仍從第一對數開始比較(因為可能由于第2個數和第3個數的交換,使得第1個數不再小于第2個數),將小數放前,大數放后,一直比較到倒數第二個數(倒數第一的位置上已經是最大的),第二趟結束,在倒數第二的位置上得到一個新的最大數(其實在整個數列中是第二大的數)。

如此下去,重復以上過程,直至最終完成排序。由于在排序過程中總是小數往前放,大數往后放,相當于氣泡往上升,所以稱作冒泡排序。
用二重循環實現,外循環變量設為i,內循環變量設為j。外循環重復9次,內循環依次重復9,8,...,1次。每次進行比較的兩個元素都是與內循環j有關的,它們可以分別用a[j]和a[j+1]標識,i的值依次為1,2,...,9,對于每一個i,j的值依次為1,2,...10-i。
在許多程序設計中,我們需要將一個數列進行排序,以方便統計,而冒泡排序一直由于其簡潔的思想方法而倍受青睞。
設想被排序的數組R[1..N]垂直豎立,將每個數據元素看作有重量的氣泡,根據輕氣泡不能在重氣泡之下的原則,從下往上掃描數組R,凡掃描到違反本原則的輕氣泡,就使其向上"漂浮",如此反復進行,直至最后任何兩個氣泡都是輕者在上,重者在下為止。
若記錄序列的初始狀態為"正序",則冒泡排序過程只需進行一趟排序,在排序過程中只需進行n-1次比較,且不移動記錄;反之,若記錄序列的初始狀態為"逆序",則需進行n(n-1)/2次比較和記錄移動。因此冒泡排序總的時間復雜度為O(n*n)。
冒泡排序法存在的不足及改進方法:
第一,在排序過程中,執行完最后的排序后,雖然數據已全部排序完備,但程序無法判斷是否完成排序,為了解決這一不足,可設置一個標志單元flag,將其設置為OFF,表示被排序的表示是一個無序的表。在每一排序開始時,檢查此標志,若此標志為0,則結束排序;否則進行排序;
第二,當排序的數據比較多時排序的時間會明顯延長。改進方法:快速排序:具體做法:任意選取某一記錄(通常取第一個記錄),比較其關鍵字與所有記錄的關鍵字,并將關鍵字比它小的記錄全部放在它的前面,將比它大的記錄均存放在它的后面,這樣,經過一次排序之后,可將所有記錄以該記錄所在的分界點分為兩部分,然后分別對這兩部分進行快速排序,直至排序完

局部冒泡排序算法對冒泡排序的改進:
在冒泡排序中,一趟掃描有可能無數據交換,也有可能有一次或多次數據交換,在傳統的冒泡排序算法及近年來的一些改進的算法中,只記錄一趟掃描有無數據交換的信息,對數據交換發生的位置信息則不予處理。為了充分利用這一信息,可以在一趟全局掃描中,對每一反序數據對進行局部冒泡排序處理,稱之為局部冒泡排序。局部冒泡排序與冒泡排序算法具有相同的時間復雜度,并且在正序和逆序的情況下,所需的關鍵字的比較次數和移動次數完全相同。由于局部冒泡排序和冒泡排序的數據移動次數總是相同的,而局部冒泡排序所需關鍵字的比較次數常少于冒泡排序,這意味著局部冒泡排序很可能在平均比較次數上對冒泡排序有所改進,當比較次數較少的優點不足以抵消其程序復雜度所帶來的額外開銷,而當數據量較大時,局部冒泡排序的時間性能則明顯優于冒泡排序。

程序示例
DELPHI

49 13 13 13 13 13 13 13

38 49 27 27 27 27 27 27

65 38 49 38 38 38 38 38

97 65 38 49 49 49 49 49

76 97 65 49 49 49 49 49

13 76 97 65 65 65 65 65

27 27 76 97 76 76 76 76

49 49 49 76 97 97 97 97

Procedure BubbleSort(Var R : FileType) //從下往上掃描的起泡排序//

Begin

For I := 1 To N-1 Do //做N-1趟排序//

begin

NoSwap := True; //置未排序的標志//

For J := N - 1 DownTo 1 Do //從底部往上掃描//

begin

If R[J+1]< R[J] Then //交換元素//

begin

Temp := R[J+1]; R[J+1] := R[J]; R[J] := Temp;

NoSwap := False

end;

end;

If NoSwap Then Return//本趟排序中未發生交換,則終止算法//

end

End; //BubbleSort//

該算法的時間復雜性為O(n^2),算法為穩定的排序方

冒泡排序代碼
AAuto
  bubble_sort = function(array){

var temp;

for( i=1;#array ){

//i前面的已經是最小的數,并排序好了

for(j=#array;i+1;-1){

//挨個比較

if(array[j]<array[j-1]){

//小的總是往前排

bubble = array[j]

array[j] = array[j-1];

array[j-1] = bubble;

}

}

}

}

io.print("----------------")

io.print("冒泡排序( 交換類換排序 )")

io.print("----------------")

array ={2;46;5;17;1;2;3;99;12;56;66;21};

bubble_sort(array,1,#array)

//輸出結果

for(i=1;#array;1){

io.print( array[i] )

}
C語言
基礎結構
  */

void bubble_sort(int *x,int n)

{

int j,k,h,t;

for (h=n-1,h=k; h>0; h--) /*循環到沒有比較范圍*/

{

for (j=0,k=0; j<h; j++) /*每次預置k=0,循環掃描后更新k*/

{

if (*(x+j) > *(x+j+1)) /*大的放在后面,小的放到前面*/

{

t = *(x+j);

*(x+j) = *(x+j+1);

*(x+j+1) = t; /*完成交換*/

k = j; /*保存最后下沉的位置。這樣k后面的都是排序排好了的。*/

}

}

}

}

程序1:

void bubble_sort(int array[],int n)

{

int i,j,flag,temp;

for(i = 0; i < n-1; i++)

{

flag = 1;

for(j = 0; j < n-i-1; j++)

{

if(array[j] > array[j+1])

{

temp= array[j];

array[j] = array[j+1];

array[j+1] = temp;

flag = 0;

}

}

if(1 == flag)

printf("%d ",i); //首先打印出,在第幾層循環時順序已排好

break; //跳出循環

}

return;

}

程序2:

#include<STDIO.H>

main()

{

long a,x,k,i[100],s;

char ch;

for(a=0;;a++)

{

printf("輸入一個數,輸完一個數按回車,最后一個數末尾要加n:");

scanf("%ld%c",&i[a],&ch);

if(a==99)

{

printf("注意!輸入的數超過100個");

break;

}

else if(ch=='n')

break;

}

do{

x=0;

for(k=0;k<a;k++)

{

if(i[k]>i[k+1])

{

s=i[k+1];i[k+1]=i[k];

i[k]=s;x++;

}

}

}while(x!=0);

printf("從小到大排列為:");

for(k=0;k<a;k++)

printf("%ld<",i[k]);

printf("%ld",i[a]);

}
C++
  #include <iostream>

#define LEN 9

using namespace std;

int main()

{

int nArray[LEN];

for(int i=0;i<LEN;i++)

{

nArray[i]=LEN-i; //賦初值

}

cout<<"原始數據為:"<<endl;

for(int j=0;j<LEN;j++)

{

cout<<nArray[j]<<" ";

}

cout<<endl;

for(int m=LEN-1;m>0;m--)

{

int temp;

for(int n=0;n<m;n++)

{

if(nArray[n]>nArray[n+1])

{

temp=nArray[n];

nArray[n]=nArray[n+1];

nArray[n+1]=temp;

}

}

}

cout<<"排序結果:"<<endl;

for(i=0;i<LEN;i++)

{

cout<<nArray[i]<<" ";

}

return 0;

}
PHP
  代碼1:

<?php

//冒泡排序(一維數組)

function bubble_sort($array)

{

$count = count($array);

if ($count <= 0) return false;

for($i=0; $i<$count; $i++)

{

for($j=$count-1; $j>$i; $j--)

{

if ($array[$j] < $array[$j-1])

{

$tmp = $array[$j];

$array[$j] = $array[$j-1];

$array[$j-1] = $tmp;

}

}

}

return $array;

}

//使用實例

$_array = array('5','8','5','6','9','3','2','4');

$_array = bubble_sort($_array);

print ($_array);

>

代碼2:

<?php

//冒泡排序

function maopaosort($arr)

{

for ($i=0;$i<count($arr)-1;$i++ ) {

for ($j=0;$j<count($arr)-1-$i;$j++ ) {

if($arr[$j]>$arr[$j+1])

{

//交換賦值,不使用中間變量

$arr[$j]=$arr[$j+1]+$arr[$j];

$arr[$j+1]=$arr[$j]-$arr[$j+1];

$arr[$j]=$arr[$j]-$arr[$j+1];

}

}

}

return $arr;

} // end func

//實例

$arr=array(7,3,6,1,5,2,11,4,44,33,22,88,44);

print_r(maopaosort($arr));

//結果輸出Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 4 [4] => 5 [5] => 6 [6] => 7 [7] => 11 [8] => 22 [9] => 33 [10] => 44 [11] => 44 [12] => 88 )

>
Ruby
  def bubble(arr)

(arr.length-1).downto(1) do |j|

a1 = arr.dup

j.times do |i|

if arr > arr[i+1]

arr,arr[i+1] = arr[i+1],arr

end

end

break if a1 == arr

end

arr

end
Java
  // 冒泡排序

public class BubbleSort {

public static void sort(Comparable[] data) {

// 數組長度

int len = data.length;

for (int i = 0; i < len - 1; i++) {

// 臨時變量

Comparable temp = null;

// 交換標志,false表示未交換

boolean isExchanged = false;

for (int j = len - 1; j > i; j--) {

// 如果data[j]小于data[j - 1],交換

if (data[j].compareTo(data[j - 1]) < 0) {

temp = data[j];

data[j] = data[j - 1];

data[j - 1] = temp;

// 發生了交換,故將交換標志置為真

isExchanged = true;

}// end if

}// end for

// 本趟排序未發生交換,提前終止算法,提高效率

if (!isExchanged) {

break;

}// end if

}// end for

}// end sort

public static void main(String[] args) {

// 在JDK1.5版本以上,基本數據類型可以自動裝箱

// int,double等基本類型的包裝類已實現了Comparable接口

Comparable[] c = { 4,9,23,1,45,27,5,2 };

sort(c);

for (Comparable data : c) {

System.out.println(data);

}

}

}

//簡單示例

public class Test_Ordination {

public static void main(String args[]){

int[] s = {23,5,12,59,78,21,100,79,66};

for(int j=1;j<=s.length;j++){

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

if(s[i]>s[i+1]){

int temp;

temp = s[i];

s[i] = s[i+1];

s[i+1] = temp;

}

}

}

for(int i=0;i<s.length;i++){

System.out.println(s[i]);

}

}

}
Visual Basic
  Private Sub Form_Load()

Dim a,c As Variant

Dim i As Integer,j As Integer,temp As Integer,bSwap As Boolean

a = Array(17,45,12,80,50)

For j = 0 To UBound(a) - 1

bSwap = False

For i = 0 To UBound(a) - 1

If (a(i) > a(i + 1)) Then '若是遞減,改為a(i)<a(i+1)

temp = a(i)

a(i) = a(i + 1)

a(i + 1) = temp

bSwap = True

End If

Next

If bSwap = False Then

Exit For

End If

Next

For Each c In a

Debug.Print c;

Next

End Sub
Pascal
  program bubble_sort;

var

a:array[1..N] of 1..MAX;

temp,i,j:integer;

begin

randomize;

for i:=1 to N do a:=1+random(MAX);

writeln('Array before sorted:');

for i:=1 to N do write(a,' ');

writeln;

for i:=N-1 downto 1 do

for j:=1 to i do

if a[j]<a[j+1] then

begin

temp:=a[j];

a[j]:=a[j+1];

a[j+1]:=temp;

end;

writeln('Array sorted:');

for i:=1 to N do write(a,' ');

writeln;

writeln('End sorted.');

readln;

end.
C#
  static void Main(string[] args)

{

int[] array = { 23,45,16,7,42 };

int length = array.Length - 1;

bool isExchanged = false;

for (int i = 0; i < length; i++)

{

isExchanged = false;

for (int j = length; j > i; j--)

{

if (array[j] > array[j - 1])

{

int temp = array[j];

array[j] = array[j - 1];

array[j - 1] = temp;

isExchanged = true;

}

}

if (!isExchanged)//一遍比較過后如果沒有進行交換則退出循環

break;

}

foreach (int i in array)

{

Console.WriteLine(i);

}

Console.Read();

}
Python
  #BubbleSort used python3.1 or python 2.x

def bubble(str):

tmplist = list(str)

count = len(tmplist)

for i in range(0,count-1):

for j in range(0,count-1):

if tmplist[j] > tmplist[j+1]:

tmplist[j],tmplist[j+1] = tmplist[j+1],tmplist[j]

return tmplist

#useage:

str = "zbac"

print(bubble(str)) # ['a','b','c','z']

number=[16,134,15,1]

print(bubble(number)) # [1,15,16,134]
JS
  function(array){

var i = 0,len = array.length,

j,d;

for(; i<len; i++){

for(j=0; j<len; j++){

if(array[i] < array[j]){

d = array[j];

array[j] = array[i];

array[i] = d;

}

}

}

return array;

}
Action Script
  var arr:Array=new Array(88,0,4,22,89,0,8,15);

var temp:int=0;

for(var i:int=0;i<arr.length;i++){

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

if(arr[j]>arr[j+1]){

temp=arr[j];

arr[j]=arr[j+1];

arr[j+1]=temp;

}

}

}

for(var t:int=0;t<arr.length;t++){

trace(arr[t]);

}
偽代碼
  BUBBLESORT(A)

for i <- 1 to length[A]

do for j <- length[A] downto i + 1

do if A[j]<A[j - 1]

then exchange A[j] <-> A[j-1]

PL/SQL代碼 

declare

type varr_type is varray(10) of integer;

varr varr_type:=varr_type(65,32,44,78,20,13,28,99,0,1);

i integer;

j integer;

t integer;

begin

for i in reverse 1..10 loop --保證最大的那個值在最終的位置上

for j in 1..i-1 loop

if varr(j)>varr(j+1) then

t:=varr(j);

varr(j):=varr(j+1);

varr(j+1):=t;

end if;

end loop;

end loop;

for i in 1..10 loop

dbms_output.put_line(varr(i));

end loop;

end;
REAL Basic
  Private Sub Form_Load()

Dim a,c As Variant

Dim i As Integer,j As Integer,temp As Integer

a = Array(17,45,12,80,50)

For j = 0 To UBound(a) - 1

For i = 0 To UBound(a) - 1

If (a(j) > a(i)) Then

temp = a(j)

a(j) = a(i)

a(i) = temp

End If

Next

Next

For i=0 to UBound(a)

msgbox str(a(i))
Next
End Sub
變種算法
一個叫做雞尾酒排序(也稱雙向冒泡排序)的算法,和冒泡排序的“編程復雜度”一樣,但對隨機序列排序性能稍高于普通冒泡排序,但是因為是雙向冒泡,每次循環都雙向檢查,極端環境下會出現額外的比較,導致算法性能的退化,比如“4、5、7、1、2、3”這個序列就會出現退化

冒泡排序算法及各種程序示例
文章《冒泡排序算法及各種程序示例》二維碼
  • 微信打賞
  • 支付寶打賞

暫無評論

(必填)

(必填)

(可選)

黑龙江22选5开奖