C#實現冒泡排序

一、算法原理

?

1、比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。

2、對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。在這一點，最后的元素應該會是最大的數。

3、針對所有的元素重復以上的步驟，除了最后一個。

4、持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。

?

二、算法分析

?

平均時間復雜度：冒泡排序最好為O(n)?，最壞為O(n2)，平均時間復雜度為O(n2)

空間復雜度：O(1) ?(用于交換)

?

三、算法穩定性

?

冒泡排序就是把小的元素往前調或者把大的元素往后調。比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間。所以，如果兩個元素相等，我想你是不會再無聊地把他們倆交換一下的；如果兩個相等的元素沒有相鄰，那么即使通過前面的兩兩交換把兩個相鄰起來，這時候也不會交換，所以相同元素的前后順序并沒有改變，所以冒泡排序是一種穩定排序算法。

?

四、冒泡排序有兩個很明顯的優勢

1.“編程復雜度”很低，很容易寫出代碼；

2.具有穩定性，這里的穩定性是指原序列中相同元素的相對順序仍然保持到排序后的序列，而堆排序、快速排序均不具有穩定性。 ?

五、C#冒泡排序算法

?

C# 代碼 ??復制

//冒泡排序

void BubbleSort(int array[],int n)

{int i=0; int j=0; int temp=0;int flag = 0;for(i=0;i<n - 1 ;i++)   /*外循環控制排序的總趟數*/
{flag = 0;   /*本趟排序開始前，交換標志應為假*/for(j=n-1;j > i;j--) /*內循環控制一趟排序的進行*/ 
{ if(array[j] < array[j-1] ) /*相鄰元素進行比較，若逆序就交換*/ { temp =array[j]; array[j] = array[j-1]; array[j-1] = temp; flag = 1; /*發生了交換，故將交換標志置為真*/ } } if (flag == 0) /*本趟排序未發生交換，提前終止算法*/ break; /* printf("第%d趟排序結果： \\n",i+1); PrintArray(array,n); */ } } 

?

算法的應用

?

C# 代碼 ??復制

//打印數組

void PrintArray(int  array[] , int n)

{int i;for(i=0;i<n;i++)printf(" %d ",array[i]);printf("\\n");
}void TestBubbleSort()
{int array[8] ={38,20,46,38,74,91,12,25};BubbleSort(array,8);PrintArray(array,8);
}

?

輸出形式

?

第1趟?? 第2趟? 第3趟?? 第4趟?? 第5趟?? 第6趟?? 第7趟

12????? 12????? 12????? 12????? 12????? 12????? 12?????????????????????????????

38????? 20????? 20????? 20????? 20????? 20????? 20

20????? 38????? 25????? 25????? 25????? 25????? 25

46????? 25????? 38????? 38????? 38????? 38????? 38

38????? 46????? 38????? 38????? 38????? 38????? 38

74????? 38????? 46????? 46????? 46????? 46????? 46

91????? 74????? 74????? 74????? 74????? 74????? 74

25????? 91????? 91????? 91????? 91????? 91????? 91 ?