C語言程序如下;
#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;
}
擴展資料:
算法分析
時間復雜度
若文件的初始狀態是正序的,壹趟掃描即可完成排序。所需的關鍵字比較次數C
和記錄移動次數M均達到最小值:
所以,冒泡排序最好的時間復雜度為O(n)。
若初始文件是反序的,需要進行n-1趟排序。每趟排序要進行能n-i次關鍵字的比較(1≤i≤n-1),且每次比較都必須移動記錄三次來達到交換記錄位置。在這種情況下,比較和移動次數均達到最大值:
冒泡排序的最壞時間復雜度為O(n^2)。
綜上,因此冒泡排序總的平均時間復雜度為O(n^2)。
參考資料:
百度百科-冒泡排序法