代做备案网站,seo顾问张智伟,汕头seo网络推广,杭州专业网站设计策划基本算法研究1-冒泡排序算法测试 1、经典冒泡排序法基本原理 先看一个动态图#xff0c;感觉比较形象#xff1a; 冒泡排序#xff08;Bubble Sort#xff09;是一种简单的排序算法。默认是从小到大排序#xff0c;即把最大的数据排在最后#xff0c;相当于每次把最大数据…基本算法研究1-冒泡排序算法测试 1、经典冒泡排序法基本原理 先看一个动态图感觉比较形象 冒泡排序Bubble Sort是一种简单的排序算法。默认是从小到大排序即把最大的数据排在最后相当于每次把最大数据像气泡一样浮到水面一样。它重复地走访过要排序的数列一次比较两个元素如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换。 基本步骤 1、比较相邻的元素。如果第一个比第二个大就交换他们两个。 2、对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对。在这一点最后的元素应该会是最大的数。 3、针对所有的元素重复以上的步骤除了最后一个。 4、持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较。 最经典的冒泡排序法就是两层For循环嵌套。外层For循环是“趟”数内层是每一“趟”对相邻的两个数据进行大小比较根据需要进行交换位置。 int a[SORT_NUM];for (int i0; iSORT_NUM; i)a[i]arc4random()%SORT_NUM1;//随机生成数组
for (int i0; iSORT_NUM; i)//外层循环{ for (int j0; jSORT_NUM-i-1; j)//内层循环{ if (a[j]a[j1])//交换数据{int tempa[j];a[j]a[j1];a[j1]temp;} }}2、冒泡排序的性能 时间复杂度平均O(n²) 最好O(n²) 最差O(n²) 稳定稳定的 空间复杂度O(1) 备注在n较小时排序效果比较好优点是比较简单。但是随着n的增大耗时增加很快。 3、实际测试结果 使用Xcode对冒泡排序进行了测试结果如下 nn倍数第1次第2次第3次平均时间倍数使用时间单位10 18.0025.0314.0119.01 微秒1001067.9770.9943.9960.983.21微秒1000102.071.942.082.0333.29毫秒10 00010298.59265.01279.29280.96138.40毫秒100 0001029.8931.1832.5131.19111.01秒200 0002129.95122.60128.04126.984.07秒 基本上可以发现随着数据规模增加到之前的N倍所用的时间是之前所用时间的N²倍。比如一万数据用时是280.96毫秒十万数据用时是31.19秒十万数据用时是一万数据用时的111.01倍大约是10²倍。和冒泡排序法的时间复杂度O(N²)是相符的。 测试程序如下 在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 i0; iSORT_NUM; i){//随机生成数组a[i]arc4random()%SORT_NUM1;// printf( %d,a[i]);}NSDate * startTime[NSDate date];startTime[startTime dateByAddingTimeInterval:60*60*8];for (int i0; iSORT_NUM; i)//外层循环{for (int j0; jSORT_NUM-i-1; j)//内层循环{if (a[j]a[j1])//交换数据{int tempa[j];a[j]a[j1];a[j1]temp;}}}NSDate * endTime[NSDate date];endTime[endTime dateByAddingTimeInterval:60*60*8];NSTimeInterval sortTime[endTime timeIntervalSinceDate:startTime];printf(\n排序后\n);//for (int i0; iSORT_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
