如何提高冒泡排序效率呢
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
冒泡排序是一种基于比较的排序方法他的时间复杂都一般来说是ON*N。常规的冒泡排序流程如下
给定一个有n个元素的数组
比较一对相邻的两个元素a,b
如果两个元素不相等则交换两个元素
完成数组所有元素的一轮比较选出本轮的数组的最值
除去最值的其他元素开始新一轮比较直到剩余元素为1.
用C++代码形式表现
Void bubbleSort(int a[],int N){
//外循环进行N次迭代N代表数组中元素个数
for(;N>0;N--){
for(int i =0;i<N-1;i++){//从第一个元素开始比较相邻元素内循环迭代N-1次
if(a[i]>a[i+1]);//元素不一样
swap(a[i],a[i+1]);//交换
}
}
}
当i=1时迭代N-1次
当i=2时迭代N-2次
当i=N-2时迭代1次
当i=N-1时迭代0次
总迭代数(N-1)+(N-2)+...+1+0=N*(N-1)/2
总时间C*N*(N-1)/2
计算时间复杂度时常数可以忽略因此常规的冒泡排序的时间复杂度为O(N*N)
那么如何优化冒泡排序的时间复杂度呢
我们可以通过提前终止来提前结束冒泡排序。方法也很简单就是当某一次循环中元素完全不进行交换那么我们可以认为此时的数组已经完成了排序此时可以提前结束冒泡排序。
改进后的代码
Void bubbleSort(int a[],int N){
//外循环进行N次迭代N代表数组中元素个数
for(;N>0;N--){
int count = 0//通过计数器来确认内循环中是否存在元素交换
for(int i =0;i<N-1;i++){//从第一个元素开始比较相邻元素内循环迭代N-1次
if(a[i]>a[i+1]){ //元素不一样
swap(a[i],a[i+1]);//交换
count++;
}
if(count==0)
break;
}
}
}
如果说内循环没有元素交换那么计数器为0此时就可以认为此时数组已经完成了排序可以提前结束冒牌排序了。