第C語言實現冒泡排序算法的示例詳解目錄1.問題描述2.問題分析3.算法設計動圖演示4.程序設計設計一設計二結論5.流程框架6.代碼實現7.問題拓展

1.問題描述

對N個整數（數據由鍵盤輸入）進行升序排列。

2.問題分析

對于N個數因其類型相同，我們可利用數組進行存儲。

冒泡排序是在兩個相鄰元素之間進行比較交換的過程將一個無序表變成有序表。

冒泡排序的思想：首先，從表頭開始往后掃描數組，在掃描過程中逐對比較相鄰兩個元素的大小。

若相鄰兩個元素中，前面的元素大于后面的元素，則將它們互換，稱之為消去了一個逆序。

在掃描過程中，不斷地將兩相鄰元素中的大者往后移動，最后就將數組中的最大者換到了表的最后，這正是數組中最大元素應有的位置。

然后，在剩下的數組元素中（n-1個元素），重復上面的過程，將次小元素放到倒數第2個位置。

不斷重復上述過程，直到剩下的數組元素為0為止，此時的數組就變為了有序。

假設數組元素的個數為nnn，在最壞情況下需要的比較總次數為:((n1)+(n2)+...+2+1)=n(n1)/2。

3.算法設計

冒泡排序的過程我們用示意圖簡單的表示，從整個排序過程中尋找規律，n個元素只需比較n1次即可。

假設一個數組中有7個元素，現在對這7個元素進行排序，只需比較6輪即可得到所要的有序序列。

示意圖中最后加粗的數字即為經過一輪交換位置固定的數字。示意圖如下：

動圖演示

清楚了冒泡排序的過程，我們再來看一個動態圖

4.程序設計

設計一

數組名用a表示、數組下標用j表示，數組中相鄰兩個元素的下標可表示為a[j]、a[j+1]或a[j-1]、a[j]。

在利用數組解決問題時需要注意數組下標不要越界。

假如定義一個整形數組inta[n]，則數組元素下標的取值范圍是0～(n1)，下標小于0或者大于n1都視為下標越界。

如果相鄰元素采用a[j]、a[j＋1]表示的話，則下標取值范圍是0～(n2)；

若采用a[j-1]、a[j]表示，下標取值范圍則是1～(n1)

設計二

數組元素互換也是經常遇到的一類題型，一般這種情況我們需要借助一個中間變量才可以完成，對于許多初學者來說經常犯的一個錯誤是：對兩個元素直接相互賦值，而不借助中間變量。

我們先來看生活中的一個例子：

在藍墨水瓶中裝有藍墨水，紅墨水瓶中裝有紅墨水；現在我們要把藍墨水放到紅墨水瓶中，紅墨水放到藍墨水瓶中。

做法是先找一個白色空瓶（作用相當于程序中的中間變量）：

首先將藍墨水倒入白色空瓶：t=a[i]或t=a[i+1]；

接著將紅墨水倒入藍墨水瓶：a[i]=a[i+1]或a[i+1]=a[i]；

最后將白瓶中的藍墨水倒入紅墨水瓶：a[i+1]=t或a[i]=t；

經過這3步就完成了紅墨水與藍墨水的互換。如果不借助白色空瓶，直接把藍墨水倒入紅墨水瓶，或把紅墨水倒入藍墨水瓶，這樣必將破壞原來所存儲的內容。

第一輪的交換過程可以用簡單的程序段進行表示：

第二輪交換過程（最后一個元素經過第一輪比較已經確定，不需要再次進行比較）：

第三輪交換過程（最后兩個元素已經確定，不需要再次進行比較）：

結論

由上面的程序段發現，第一輪比較的判定條件為jn-1；

第二輪為jn-2；

第三輪為jn-3；

依次類推，第i輪的循環判定條件必為jn-i。

在編程過程中我們可以用兩層循環來控制，第一層循環控制交換的輪數，第二層循環控制每輪需要交換的次數。

5.流程框架

6.代碼實現

假設有下面一組無序數組，我們要對它進行升序排序

完整代碼

#includestdio.h

//冒泡排序函數

voidBubbleSort(intarr[],intlen)

inti;

intj;

inttemp;

for(i=0;ilen-1;i++)//控制比較的輪數

for(j=0;jlen-1-i;j++)//控制每輪比較的次數

if(arr[j]arr[j+1])//數組相鄰兩個元素進行交換

temp=arr[j];

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

arr[j+1]=temp;

//輸出函數

voidprint(intarr[],intlen)

inti;

for(i=0;ilen;i++)

printf("%3d",arr[i]);

intmain()

intarr[10]={5,8,6,3,9,2,1,7,12,4};

BubbleSort(arr,10);

printf("Thedataaftersorted：\n");

print(arr,10);

printf("\n");

return0;

運行結果

代碼貼圖

7.問題拓展

常用的排序方法除了上述的冒泡排序外，還有選擇排序、插入排序、快速排序和堆排序等，下面簡單介紹一下選擇排序。

選擇排序思想：

掃描整個線性表，第一輪比較拿數組中的第一個元素與其他元素進行比較，遇到比第一個元素小的則進行交換；

再拿著交換之后的第一個元素接著上次比較的位置與后面的元素進行比較，直到掃描到線性表的最后，從中選出最小的元素，將它交換到表的最前面（這是它應有的位置）。

第二輪比較的時候從第二個元素開始，依次與第三個、第四個直到最后一個比較，在比較過程中有比第二個元素小的進行交換，接著與后面的元素比較；

對剩下的子表采用同樣的方法，直到子表為空。在最壞情況下需要比較n(n1)/2次。

選擇排序如下

#includestdio.h

//選擇排序

voidselectSort(intarr[],intlen)

inti;

intj;

for(i=0;ilen-1;i++)

intmin=i;//假設第一個元素是最小的

for(j=i+1;jlen;j++)

if(arr[j]arr[min])

min=j;//保存最小元素的下標

//交換

inttemp=arr[min];

arr[min]=arr[i];

arr[i]=temp;

voidprint(intarr[],intlen)

for(inti=0;ilen;i++)

printf("%3d",arr[i]);

intmain()

intarr[10]={5,8,6,3,9,2,1,7,12,4};

selectS