冒泡排序文章目录冒泡排序1. 问题2.算法思想3. 关于冒泡排序的优化3.1 ⼀次优化3.2 二次优化4. 复杂度分析5. 稳定性分析6. 如何用两个栈实现冒泡7. 测试函数8.头文件部分9. 实现10. 测试案例main函数输出结果1. 问题冒泡排序似乎是初学者接触的第一个排序算法但是你真的已经完全掌握他了吗 冒泡排序如何判断数组是否有序了呢 冒泡排序数组 [ 3 , 1 , 2 , 4 , 5 , 6 , 7 , 8 , 9 ] 是否有优化⽅式呢 冒泡排序最好的时间复杂度最坏的时间复杂度还有空间复杂度清楚吗 如何⽤递归的形式实现冒泡排序 如何使⽤两个栈来实现冒泡排序 对单链表⼜该如何进⾏冒泡排序 最后⼀个简单的如何使⽤冒泡排序对字符串数组进⾏排序 2.算法思想冒泡排序是最简单的排序算法了。冒泡排序通过不断地⽐较两个相邻元素将较⼤的元素交换到右边升序从⽽实现排序那我们直接看例⼦吧我们对数组 [514284] 采⽤冒泡排序进⾏排序注意这⾥的两个 4 的颜⾊是不同的主要是为了区分两个不同的 4 进⽽解释冒泡排序算法的稳定性问题第⼀轮冒泡排序第⼀步⽐较 5 和 1 5 1则交换 5 和 1 的位置第⼆步⽐较 5 和 45 4交换 5 和 4 的位置第三步⽐较 5 和 2 5 2交换 5 和 2 的位置第四步⽐较 5 和 8 5 8 不交换第五步⽐较 8 和 4 8 4交换 8 和 4 此刻我们获得数组当中最⼤的元素 8 使⽤紫⾊进⾏标记第⼀轮冒泡结束最⼤的元素8到了最后然后对于前⾯5个元素进⾏第⼆轮冒泡 此处省略一万张图最终结果事实上第⼆阶段结束整个数组已经有序了但是对于冒泡排序⽽⾔并不知道她还需要通过第三阶段的⽐较操作进⾏判断。对于冒泡排序算法⽽⾔他是通过判断整个第三阶段的⽐较过程中是否发⽣了交换来确定数组是否有序的显然上⾯的过程中没有交换操作冒泡排序也就知道了数组有序整个算法执⾏结束。3. 关于冒泡排序的优化基本的冒泡排序的实现⽅式就是两个for循环持续⽐较和交换。这种实现⽅式有⼀个明显的弊端就是不论数组是否有序两层 for 循环都要执⾏⼀遍⽽我们是希望数组有序的时候仅进⾏⼀轮判断或者⼀轮都不进⾏当然不判断排序算法是不能知道数组是否有序的3.1 ⼀次优化我们增加了⼀个标识数组是否有序 当冒泡排序过程中没有交换操作时 swapped false 也意味着数组有序否则数组⽆序继续进⾏冒泡排序3.2 二次优化⼀次优化是为了避免数组有序的情况下继续进⾏判断操作的。那么⼆次优化⼜为了什么呢看下面的例子经过⼀次冒泡后我们会注意到⼀个问题但是我们注意到数组数组中的 [5,6,8] 本身已经有序⽽对于有序的部分进⾏⽐较是没有意义的相当于在⽩⽩浪费资源有没有什么办法减少这样的⽐较次数呢换句话说是否能够确定出已经有序部分和⽆序部分的边界呢答案当然是肯定的这个边界就是第⼀趟冒泡排序的过程中最后⼀次发⽣交换的位置 j 也就是1 和 4 发⽣交换之后4 和 5 没有发⽣交换此时 1 之后的元素为有序。第⼀步4 和 2⽐较4 2 交换 4 和 2 将 LastSwappedIndex 0第⼆步4 和 1 ⽐较4 1交换 4 和 1 LastSwappedIndex 1第三步⽐较 4 和 5 4 5不交换 lastSwappedIndex 也不更新第四步⽐较 5 和 6 不交换 lastSwappedIndex 也不更新第五步⽐较 6 和 8 不交换 lastSwappedIndex 也不更新第⼀趟冒泡排序结束了这⾥似乎看不出和之前有什么区别但是来看第⼆趟冒泡排序就不⼀样了此时 j 的 取值将从 j 0 到 j lastSwappedIndex 第⼀步⽐较 2 和 1 2 1交换 lastSwappedIndex 0 并且第⼆趟冒泡也就结束了也就说我们节省了 从 2 到 6的⽐较操作最后再来⼀趟冒泡排序发现没有任何交换所以冒泡排序结束相⽐于⼀次优化的实现⽅式⼆次优化的实现⽅式进⼀步减少了不必要的执⾏次数两种优化后的实现⽅式需要冒泡排序的趟数是⼀样的本质上没有什么区别。所以即使对于⼀个有序的数组两种⽅式的时间复杂度都是On4. 复杂度分析最好情况 (数组有序)第一轮遍历全程没有发生任何交换swapped为 false直接 break 结束仅执行 1 趟扫描一共 (n-1) 次比较时间复杂度O (n)最坏情况 (数组逆序)无法提前退出依然需要跑完全部 (n-1) 趟总比较次数依旧n ( n − 1 ) 2 \frac{n(n-1)}{2}2n(n−1)时间复杂度O(n^2)如果是未优化的冒泡排序固定执行 (n-1) 趟外层循环不会提前退出最好最坏时间复杂度都是 O(n^2)5. 稳定性分析稳定的在最开始的例子中我们可以发现两个 4 的相对位置没有发⽣变化也就是说冒泡排序是稳定的。但这仅相当于实验验证⽽在理论上冒泡排序为什么是稳定的呢本质原因在于冒泡排序⽐较和交换的是两个相邻元素对于键值相同的关键字是不交换位置的所以排序前后键值相同的关键字的相对位置才保持不变的。6. 如何用两个栈实现冒泡ps明天写7. 测试函数这些函数也是之前写的排序算法里用到的在插入排序那里提到过 看懂即可typedefintkeyType;typedefstruct{keyType key;// 查找表中每个数据元素的关键值void*data;// 数据的其他区域}Element;typedefstruct{Element*data;// 存放查找表中数据元素的首地址intlength;// 查找表的元素个数}SortTable;enumsortStatus{success,failed};voidswapElement(Element*a,Element*b);// 交换元素a和元素bSortTable*generateRandomArray(intn,intlow,inthigh);// 产生随机数范围[low,high]SortTable*generateLinearArray(intn,intswapTimes);// 参数顺序空间随机交换swapTimes次 //轻微乱序 整体接近有序SortTable*copySortTable(SortTable*old);// 拷贝和old一样值的排序表voidreleaseSortTable(SortTable*table);// 排序算法函数的别名typedefvoid(*sortHandler)(SortTable*);// 测试sortName的排序算法voidtestSort(constchar*sortName,sortHandler sort,SortTable*table);#endif/* 交换a和b的元素值 */voidswapElement(Element*a,Element*b){Element tmp;memcpy(tmp,a,sizeof(Element));memcpy(a,b,sizeof(Element));memcpy(b,tmp,sizeof(Element));}/* 产生n个随机数的排序表值的范围是[low, high] */SortTable*generateRandomArray(intn,intlow,inthigh){SortTable*tablemalloc(sizeof(SortTable));if(tableNULL){fprintf(stderr,sort table malloc failed!\n);returnNULL;}table-lengthn;table-data(Element*)malloc(sizeof(Element)*n);if(table-dataNULL){fprintf(stderr,element malloc failed!\n);free(table);returnNULL;}srand(time(NULL)1);for(inti0;in;i){table-data[i].key(rand()%(high-low1))low;table-data[i].dataNULL;}returntable;}/* 产生n个随机交换swapTimes次的有序顺序表 *///轻微乱序 整体接近有序SortTable*generateLinearArray(intn,intswapTimes){SortTable*tablemalloc(sizeof(SortTable));if(tableNULL){fprintf(stderr,sort table malloc failed!\n);returnNULL;}table-datamalloc(sizeof(Element)*n);if(table-dataNULL){fprintf(stderr,data malloc failed!\n);free(table);returnNULL;}table-lengthn;for(inti0;in;i){table-data[i].keyi;table-data[i].dataNULL;}// 在已经有序的排序表中交换swapTimes次srand(time(NULL)2);for(inti0;iswapTimes;i){intpos1rand()%n;intpos2rand()%n;swapElement(table-data[pos1],table-data[pos2]);}returntable;}/* 拷贝一个排序表使用同样的数据进行不同排序算法的测试 */SortTable*copySortTable(SortTable*old){SortTable*table(SortTable*)malloc(sizeof(SortTable));table-lengthold-length;table-datamalloc(sizeof(Element)*old-length);for(inti0;iold-length;i){table-data[i].keyold-data[i].key;table-data[i].dataold-data[i].data;}returntable;}/* 释放table */voidreleaseSortTable(SortTable*table){if(table){if(table-data){free(table-data);}free(table);}}// 检查排序表里的数据是否是从小到大排序staticenumsortStatuscheckData(constSortTable*table){for(inti0;itable-length-1;i){if(table-data[i].keytable-data[i1].key){printf(Check Sort Data Failed: %d : %d\n,table-data[i].key,table-data[i1].key);returnfailed;}}returnsuccess;}/* 测试sortName的排序算法算法通过sort传递函数名数据以table传入 */voidtestSort(constchar*sortName,sortHandler sort,SortTable*table){clock_tstartclock();sort(table);clock_tendclock();if(checkData(table)failed){printf(%s failed!\n,sortName);return;}printf(%s cost time: %fs.\n,sortName,(double)(end-start)/CLOCKS_PER_SEC);}8.头文件部分//1. 原汁原味冒泡voidbubbleSortV1(SortTable*table);//2. 一次优化voidbubbleSortV2(SortTable*table);//3. 二次优化voidbubbleSortV3(SortTable*table);9. 实现/*冒泡排序 第一次遍历[0...n-1) 第二次遍历[0...n-2) ... 遍历n-1次*/voidbubbleSortV1(SortTable*table){for(inti0;itable-length-1;i){for(intj0;jtable-length-1-i;j){if(table-data[j].keytable-data[j1].key){swapElement(table-data[j1],table-data[j]);}}}}/*引入是否交换的标志 当发现某一轮不需要交换 那么说明已经有序 退出循环*/voidbubbleSortV2(SortTable*table){for(inti0;itable-length-1;i){intisSorted1;for(intj0;jtable-length-1-i;j){if(table-data[j].keytable-data[j1].key){swapElement(table-data[j1],table-data[j]);isSorted0;}}if(isSorted){break;}}}/*引入newIndex标记交换的索引位置 下次冒泡的时候结束位置就是newIndex*/voidbubbleSortV3(SortTable*table){intnewIndex;intntable-length;do{newIndex0;for(inti0;in-1;i){if(table-data[i].keytable-data[i1].key){swapElement(table-data[i1],table-data[i]);newIndexi1;}}nnewIndex;}while(newIndex0);}10. 测试案例main函数//冒泡voidtest02(){intn10000;// table1: n个随机数的排序表值的范围是[0, 5000]// table2: 拷贝table1中的内容// table3: 拷贝table1中的内容SortTable*table1generateRandomArray(n,0,05000);SortTable*table2copySortTable(table1);SortTable*table3copySortTable(table1);testSort(bubbleSortV1,bubbleSortV1,table1);testSort(bubbleSortV2,bubbleSortV2,table2);testSort(bubbleSortV3,bubbleSortV3,table3);releaseSortTable(table1)releaseSortTable(table2);releaseSortTable(table3);}intmain(){test02();return0;}输出结果bubbleSortV1 cost time:0.443000s.bubbleSortV2 cost time:0.449000s.bubbleSortV3 cost time:0.449000s.多次测试所得耗时数值不会完全相同 会受很多因素影响这里就贴个三组数据感兴趣可以自己测试下嘻嘻嘻嘻冒泡排序部分到此结束快速排序 静候更新(有错误欢迎指出) (疑问也是)❤️❤️持续更新中…
