冒泡排序算法介紹

冒泡排序（Bubble Sort）一種交換排序，它的基本思想是：兩兩比較相鄰記錄的關(guān)鍵字，如果反序則交換，直到?jīng)]有反序記錄為止。這是書上的定義，感覺太彎彎腸子了。冒泡排序是幾乎所有學(xué)編程的都會學(xué)的一個排序，因為其實現(xiàn)思路簡單。實際上就是2 相鄰元素兩兩比較，將最值冒到 最后面去，直到將所有的值都冒泡完畢，排序也就完成了。

冒泡排序算法代碼

在有n個元素的 arr數(shù)組，第1輪冒泡 將 最值冒到 arr[n-1]，第2輪冒泡將最值冒泡到arr[n-2]，外層循環(huán)完畢，數(shù)組元素全部冒泡ok，冒泡排序結(jié)束。下面是冒泡排序代碼：

//冒泡排序 //外層循環(huán)1次 將一個最值冒出 //直到將所有值 冒出去 void BubbleSort1(int *arr, int length) {for (int i = 0; i < length-1; i++){//冒泡排序是2相鄰元素進行比較，然后冒泡for (int j = 0; j < length - 1 - i; j++){//升序if (arr[j] > arr[j + 1]){Swap(&arr[j], &arr[j + 1]);}}} }

冒泡排序算法優(yōu)化

比如有個數(shù)組{9,1,2,3,4,5,6,7,8}。我們進行升序排序，在第1輪冒排序后，已經(jīng)排序ok，但是我們的普通冒泡排序，還有進行8輪的內(nèi)層for循環(huán)進行比較 ，這不就是浪費時間浪費青春嘛。所以當(dāng)我們發(fā)現(xiàn)排序已經(jīng)ok了，就可以不用再排序了。加一個排序是否ok的標(biāo)志位flag 就行了。比如{9,1,2,3,4,5,6,7,8}，在第2輪冒泡排序完畢，我們發(fā)現(xiàn)沒有交換數(shù)組元素，就知道排序已經(jīng)ok，就可以結(jié)束循環(huán)了。下面是優(yōu)化后的代碼：

//冒泡排序 優(yōu)化版，添加標(biāo)志位 //如果內(nèi)層循環(huán)完畢 發(fā)現(xiàn)沒有交換值，說明排序已經(jīng)ok了 void BubbleSort2(int *arr, int length) {int flag = 0;//0 表示沒有排好序for (int i = 0; i < length - 1 && flag == 0; i++){flag = 1;//假定排好序了for (int j = 0; j < length - 1 - i; j++){//升序if (arr[j] > arr[j + 1]){flag = 0;//其實還沒有排好序呢Swap(&arr[j], &arr[j + 1]);}}} }

冒泡排序算法復(fù)雜分析

內(nèi)存循環(huán)進行兩兩比較 交換值進行冒泡。在外層

第1輪循環(huán)時，arr[0]、arr[1].....arr[n-1]，他們兩兩比較 進行冒泡，總共比較次數(shù)為n -1，將第一個最值冒泡到arr[n-1] 處。

第2輪循環(huán)時，arr[0]、arr[1].....arr[n-2]，他們兩兩比較 進行冒泡，總共比較次數(shù)為n -2，將第二個最值冒泡到arr[n-2] 處。

所以不難得出它的比較的次數(shù)是n-1 + n-2 + n-3 + ....1 = n*（n-1）/2 。

時間復(fù)雜度為 = n^2/2- n/2 = n^2 ,O（n^2）。

冒泡排序和選擇排序比較

冒泡排序和選擇排序 雖然他們的時間復(fù)雜度都是O（n^2），但是由于冒泡排序是進行值的交換，而選擇排序是記錄最值下標(biāo) 減少了 值交換的次數(shù)，所以選擇排序比冒泡排序 效率略微 好一些。

完整代碼

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <time.h> #include <sys/timeb.h> #define MAXSIZE 20 #define MAXNUM 51 //交換值 void Swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp; } //選擇排序 核心是記錄最值下標(biāo) void SelectSort_Up(int *arr, int length) {for (int i = 0; i < length - 1; i++){int index = i;//記錄最值下標(biāo)for (int j = i + 1; j < length; j++){//升序if (arr[index] > arr[j]){index = j;}}if (i != index){Swap(&arr[i], &arr[index]);}} } //冒泡排序 //外層循環(huán)1次 將一個最值冒出 //直到將所有值 冒出去 void BubbleSort1(int *arr, int length) {for (int i = 0; i < length-1; i++){//冒泡排序是2相鄰元素進行比較，然后冒泡for (int j = 0; j < length - 1 - i; j++){//升序if (arr[j] > arr[j + 1]){Swap(&arr[j], &arr[j + 1]);}}} } //冒泡排序 優(yōu)化版，添加標(biāo)志位 //如果內(nèi)層循環(huán)完畢 發(fā)現(xiàn)沒有交換值，說明排序已經(jīng)ok了 void BubbleSort2(int *arr, int length) {int flag = 0;//0 表示沒有排好序for (int i = 0; i < length - 1 && flag == 0; i++){flag = 1;//假定排好序了for (int j = 0; j < length - 1 - i; j++){//升序if (arr[j] > arr[j + 1]){flag = 0;//其實還沒有排好序呢Swap(&arr[j], &arr[j + 1]);}}} } //打印數(shù)組元素 void PrintArr(int* arr, int length) {for (int i = 0; i < length; i++){printf("%d ", arr[i]);}printf("\n");return; } //獲取系統(tǒng)時間 time_t GetSysTime() {struct timeb time;ftime(&time);return time.time * 1000 + time.millitm;; }int main(int argc, char *argv[]) {srand((size_t)time(NULL));//設(shè)置隨機種子int arr1[MAXSIZE] = { 0 };int arr2[MAXSIZE] = { 0 };int arr3[MAXSIZE] = { 0 };//給每個元素設(shè)置一個隨機值for (int i = 0; i < MAXSIZE; i++){int num = rand() % MAXNUM;arr1[i] = num;arr2[i] = num;arr3[i] = num;}printf("冒泡排序前:\n");PrintArr(arr1, MAXSIZE);printf("普通版冒泡升序:\n");BubbleSort1(arr1, MAXSIZE);PrintArr(arr1, MAXSIZE);printf("冒泡排序前:\n");PrintArr(arr2, MAXSIZE);printf("優(yōu)化版冒泡升序:\n");long start1 = GetSysTime();BubbleSort2(arr2, MAXSIZE);long end1 = GetSysTime();PrintArr(arr2, MAXSIZE);/*printf("選擇排序前:\n");PrintArr(arr2, MAXSIZE);printf("選擇排序升序:\n");long start2 = GetSysTime();BubbleSort2(arr2, MAXSIZE);long end2 = GetSysTime();PrintArr(arr2, MAXSIZE);printf("%d個元素選擇排序耗費時間：%d\n",MAXSIZE,end1-start1);printf("%d個元素冒泡排序耗費時間：%d\n", MAXSIZE, end1 - start1);*/return 0; }

代碼運行檢測

普通冒泡和優(yōu)化的冒泡排序

選擇排序和冒泡排序比較，用10000個元素測試，就不打印了。差距很明顯喲。

總結(jié)

以上是生活随笔為你收集整理的排序算法：冒泡排序算法优化实现及分析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。