探究JavaScript实现冒泡排序的最高效时间复杂度为何为O(n^2)

沸腾排序的最佳时间复杂度为何为O

沸腾排序的核心理念是，对相邻的元素执行一一对比，若顺序相反则执行交换，如此一来，每一轮都能将最小或最大的元素“浮”至顶部，最终实现完全有序。

代码实现

在沸腾排序的过程中，若某一轮执行完毕，未进行任何一次交换操作，例如数组[5,4,1,2,3]，执行了两次沸腾，即两次外循环之后，分别将5和4调整到最终位置[1,2,3,4,5]。此时，再执行第三次循环后，一次交换都没有进行，这就表明剩余序列已经是有序的，排序操作也就可以终止，请看以下代码：

/

paramarr*/

publicstaticvoidbubbleSort(int[]arr){

for(inti=0;i<arr.length-1;i++){

booleanflag=true;//设置一个标记，若为true，则表示此次循环未进行交换，即待排序列已经有序，排序已经完成。

for(intj=0;j<arr.length-1-i;j++){

if(arr[j]>arr[j+1]){

swap(arr,j,j+1);

flag=false;

}

}

if(flag){

break;

}

}

}

根据上述这种沸腾实现，若原数组本身就是有序的（这是最佳情况），仅需n-1次比较即可完成；若是逆序，比较次数为 n-1+n-2+...+1=n(n-1)/2，交换次数与比较次数相等。因此，其时间复杂度依然为O(n^2)。综合来看，沸腾排序的最佳时间复杂度为O(n)。

JS排序之沸腾排序及其实现

时间复杂度指的是一个算法执行所消耗的时间

空间复杂度指运行完一个程序所需内存的大小

稳定性指，如果a=b，a在b的前面，排序后a仍然在b的前面

不稳定性指，如果a=b，a在b的前面，排序后可能会交换位置

原理

依次比较相邻的两个值，如果后面的比前面的小，则将小的元素排到前面。按照这个规则进行多次递减的迭代，直到顺序正确。

时间复杂度，空间复杂度，稳定性

1.平均时间复杂度O(nn)

3.最差情况O(nn)

4.空间复杂度O(1)

5.稳定性：稳定

沸腾排序的实现

两个循环

当i=0时，里面的循环完整执行，从j=0执行到j=6，这也就是第一遍排序，结果是将最大的数排到了最后，这一遍循环结束后的结果应该是[8,15,88,55,76,21,39,94]。

当i=1时，里面的循环再次完整执行，由于最大的数已经在最后了，没有必要去比较数组的最后两项，这也是j<arr.length-1-i的巧妙之处，结果是[8,15,55,76,21,39,88,94]。

说到这里，规律就清楚了，天通苑北大青鸟建议每次将剩下数组里面最大的一个数排到最后面，当第一个循环执行到最后的时候，也就是i=6，此时，j=0，只需要比较数组的第一和第二项，比较完毕，返回。