演算法定義： 冒泡排序（Bubble Sort），是一種電腦科學領域的較簡單的排序演算法。 它重覆地走訪過要排序的元素列，依次比較兩個相鄰的元素，如果順序（如從大到小、首字母從Z到A）錯誤就把他們交換過來。走訪元素的工作是重覆地進行直到沒有相鄰元素需要交換，也就是說該元素列已經排序完成。 這個演算法的名 ...
演算法定義：
冒泡排序（Bubble Sort），是一種電腦科學領域的較簡單的排序演算法。 它重覆地走訪過要排序的元素列，依次比較兩個相鄰的元素，如果順序（如從大到小、首字母從Z到A）錯誤就把他們交換過來。走訪元素的工作是重覆地進行直到沒有相鄰元素需要交換，也就是說該元素列已經排序完成。 這個演算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端（升序或降序排列），就如同碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一樣，故名“冒泡排序”。演算法分析：
時間複雜度
若文件的初始狀態是正序的，一趟掃描即可完成排序。所需的關鍵字比較次數
和記錄移動次數
均達到最小值：
。
所以，冒泡排序最好的時間複雜度為
。
若初始文件是反序的，需要進行
趟排序。每趟排序要進行
次關鍵字的比較(1≤i≤n-1)，且每次比較都必須移動記錄三次來達到交換記錄位置。在這種情況下，比較和移動次數均達到最大值： 
冒泡排序的最壞時間複雜度為
。
綜上，因此冒泡排序總的平均時間複雜度為
。
演算法穩定性
冒泡排序就是把小的元素往前調或者把大的元素往後調。比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間。所以，如果兩個元素相等，是不會再交換的；如果兩個相等的元素沒有相鄰，那麼即使通過前面的兩兩交換把兩個相鄰起來，這時候也不會交換，所以相同元素的前後順序並沒有改變，所以冒泡排序是一種穩定排序演算法。
C代碼
bubble_sort.c
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <time.h> 4 #include <string.h> 5 #include <sys/time.h> 6 7 #include "common.h" 8 9 struct ArrayData 10 { 11 int iLen; 12 int Array[0]; 13 }; 14 15 void swap(int *a, int *b) 16 { 17 int iTmp; 18 iTmp = *a; 19 *a = *b; 20 *b = iTmp; 21 } 22 23 void bubble_sort(int *iArray, int len) 24 { 25 for(int index = 0; index < len - 1; index++) 26 { 27 for(int j = 0; j < len-1-index; j++) 28 { 29 if(iArray[j] > iArray[j+1]) 30 { 31 swap(&iArray[j], &iArray[j+1]); 32 } 33 } 34 } 35 } 36 37 int main(int argc, char **argv) 38 { 39 //int iArray[10000] = {0}; 40 int size = atoi(argv[1]); 41 struct ArrayData *iArrayData = NULL; 42 struct timeval stTimeStart; 43 iArrayData = malloc(sizeof(struct ArrayData) + size * sizeof(int)); 44 iArrayData->iLen = size; 45 int *iArray = iArrayData->Array; 46 unsigned long ulTimeUse = 0; 47 48 memset(&stTimeStart, 0, sizeof(stTimeStart)); 49 50 /* 初始化隨機數發生器 */ 51 srand((unsigned)time(NULL)); 52 53 for(int i = 0; i < size; i++) 54 { 55 iArray[i] = rand() % 200 - 100; 56 } 57 58 //printf("冒泡排序前：\r\n"); 59 //for(int i = 0; i < size; i++) 60 //{ 61 //printf("%d ", iArray[i]); 62 //} 63 64 COMMON_StartRecordTime(&stTimeStart); 65 bubble_sort(iArray, size); 66 ulTimeUse = COMMON_EndRecordTime(&stTimeStart); 67 68 printf("排序%d個數據，耗時%ld usec.\r\n", size, ulTimeUse); 69 //printf("\r\n冒泡排序後：\r\n"); 70 //for(int i = 0; i < size; i++) 71 // { 72 // printf("%d ", iArray[i]); 73 //} 74 //printf("\r\n"); 75 76 return 1; 77 }
common.c
1 #include <stdio.h> 2 #include <sys/time.h> 3 4 void COMMON_StartRecordTime(struct timeval *pstTimeStart) 5 { 6 gettimeofday(pstTimeStart, NULL); 7 } 8 9 unsigned long COMMON_EndRecordTime(struct timeval *pstTimeStart) 10 { 11 struct timeval stTimeEnd; 12 gettimeofday(&stTimeEnd, NULL); 13 return 1000000 * (stTimeEnd.tv_sec - pstTimeStart->tv_sec) + (stTimeEnd.tv_usec - pstTimeStart->tv_usec); 14 }
comman.h
1 extern void COMMON_StartRecordTime(struct timeval *pstTimeStart); 2 extern unsigned long COMMON_EndRecordTime(struct timeval *pstTimeStart);
