数据结构算法学习总结-慕课网(五)冒泡排序,与选择,插入排序的异同(从小到大)
1.回顾
上一节讲到了插入排序的优化,了解了插入排序的优势,这一节会讲冒泡排序的实现方式
2.思路
对于{5,4,2}这样的数组,下标从0开始,第一轮,比较5和4,发现4比5小,那么交换两者的位置,数组变成{4,5,2},比较5和2,发现2比5小,交换两者的位置,数组变成{4,2,5},第一轮结束;第二轮,比较4和2,发现2比4小,交换两者位置,数组变成{2,4,5},第三轮不满足条件,排序结束
3.比较异同
相同点
时间复杂度都是O(n^2)
不同点
思路不同
冒泡排序:元素之间最小的元素逐渐往前,呈冒泡的方式,一个一个的传递,直到找到合适的元素最小的位置
选择排序:每轮直接寻找到最小的元素,然后放在合适的位置
插入排序:后一个元素与前一个元素比较,然后是否插入或者插入到合适的位置
4.实战
BubbleSort.cpp
#include <iostream>#include "SortTestHelper.h"#include "SelectionSort.h"using namespace std;template<typename T>void bubbleSort(T arr[],int n){for(int i = 0;i<n;i++){for(int j = 0;j<n-1-i;j++){if(arr[j+1] < arr[j]){int temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}}}
5.意见与建议
如果博友有任何问题或者建议,欢迎留言讨论如果觉得《数据结构算法学习总结-慕课网(五)冒泡排序 与选择 插入排序的异同(从小到大)》对你有帮助,请点赞、收藏,并留下你的观点哦!