基本算法研究1-冒泡排序算法測試

1、經典冒泡排序法基本原理

先看一個動態圖，感覺比較形象：

? ? ? ? 冒泡排序（Bubble Sort）是一種簡單的排序算法。默認是從小到大排序，即把最大的數據排在最后，相當于每次把最大數據像氣泡一樣浮到水面一樣。它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換。

? ? ? ? 基本步驟：

? ? ? ? 1、比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
? ? ? ? 2、對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。在這一點，最后的元素應該會是最大的數。
? ? ? ? 3、針對所有的元素重復以上的步驟，除了最后一個。
? ? ? ? 4、持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。

?

? ? ? ?最經典的冒泡排序法就是兩層For循環嵌套。外層For循環是“趟”數，內層是每一“趟”對相鄰的兩個數據進行大小比較，根據需要進行交換位置。

int a[SORT_NUM];for (int i=0; i<SORT_NUM; i++)a[i]=arc4random()%SORT_NUM+1;//隨機生成數組
for (int i=0; i<SORT_NUM; i++)//外層循環{
for (int j=0; j<SORT_NUM-i-1; j++)//內層循環{
if (a[j]>a[j+1])//交換數據{int temp=a[j];a[j]=a[j+1];a[j+1]=temp;} }}

2、冒泡排序的性能

時間復雜度：平均：O(n2) ?最好：O(n2) 最差：O(n2)

? ? ? ? 穩定：穩定的

空間復雜度：O(1)

備注：在n較小時排序效果比較好，優點是比較簡單。但是隨著n的增大，耗時增加很快。

3、實際測試結果

使用Xcode對冒泡排序進行了測試，結果如下

n	n倍數	第1次	第2次	第3次	平均	時間倍數	使用時間（單位）
10	?	18.00	25.03	14.01	19.01	?	微秒
100	10	67.97	70.99	43.99	60.98	3.21	微秒
1000	10	2.07	1.94	2.08	2.03	33.29	毫秒
10 000	10	298.59	265.01	279.29	280.96	138.40	毫秒
100 000	10	29.89	31.18	32.51	31.19	111.01	秒
200 000	2	129.95	122.60	128.04	126.98	4.07	秒

?

基本上可以發現，隨著數據規模增加到之前的N倍，所用的時間是之前所用時間的N2倍。比如一萬數據用時是280.96毫秒，十萬數據用時是31.19秒，十萬數據用時是一萬數據用時的111.01倍（大約是102倍）。和冒泡排序法的時間復雜度O(N2)是相符的。

測試程序如下：

在Xcode下運行。

#import <Foundation/Foundation.h> #define SORT_NUM 200000 //需要排序的數組的長度 int main(int argc, const char * argv[]) { #pragma mark --startint a[SORT_NUM];printf("未排序：");for (int i=0; i<SORT_NUM; i++){//隨機生成數組a[i]=arc4random()%SORT_NUM+1;// printf(" %d",a[i]);}NSDate * startTime=[NSDate date];startTime=[startTime dateByAddingTimeInterval:60*60*8];for (int i=0; i<SORT_NUM; i++)//外層循環{for (int j=0; j<SORT_NUM-i-1; j++)//內層循環{if (a[j]>a[j+1])//交換數據{int temp=a[j];a[j]=a[j+1];a[j+1]=temp;}}}NSDate * endTime=[NSDate date];endTime=[endTime dateByAddingTimeInterval:60*60*8];NSTimeInterval sortTime=[endTime timeIntervalSinceDate:startTime];printf("\n排序后：\n");//for (int i=0; i<SORT_NUM; i++)// printf(" %d",a[i]);NSLog(@"開始時間：%@",startTime);NSLog(@"結束時間：%@",endTime);NSLog(@"使用時間：%.2f微秒",sortTime*1000000);NSLog(@"使用時間：%.2f毫秒",sortTime*1000);NSLog(@"使用時間：%.2f秒",sortTime);printf("\n冒泡排序\n");#pragma mark --endreturn 0; }　

轉載于:https://www.cnblogs.com/nathan1987/p/4839497.html

總結

以上是生活随笔為你收集整理的基本算法研究1-冒泡排序算法测试的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。