JS冒泡排序

说明

  • 时间复杂度指的是一个算法执行所耗费的时间
  • 空间复杂度指运行完一个程序所需内存的大小
  • 稳定指,如果a=b,a在b的前面,排序后a仍然在b的前面
  • 不稳定指,如果a=b,a在b的前面,排序后可能会交换位置

冒泡排序原理

依次比较相邻的两个值,如果后面的比前面的小,则将小的元素排到前面。
依照这个规则进行多次并且递减的迭代,直到顺序正确。
  • 平均时间复杂度O(n*n),最好情况O(n) ,最差情况O(n*n)
  • 空间复杂度O(1)
  • 稳定性:稳定

实现方法

 function bubbleSort(arr){
    var len = arr.length,
        temp;
    for(var i=0;i<len-1;i++){
        for(var j=i;j<len-1;j++){
            if(arr[j] > arr[j+1]){
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

注意

小于10000个数据的数组用它不会超时(大概一秒)
但如果更大就要用快排或归并O(n*log2(n))
引用:https://zhidao.baidu.com/question/272274716.html

时间复杂度计算

  • 若文件的初始状态是正序的,一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值:Cmin = n - 1,Mmin = 0。
    所以,冒泡排序最好的时间复杂度为On
  • 若初始文件是反序的,需要进行 n - 1 趟排序。每趟排序要进行 n - i 次关键字的比较( 1 ≤ i ≤ n-1 ),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值:
1.jpg
2.jpg
  • 冒泡排序的最坏时间复杂度为O(n2)。
  • 综上,因此冒泡排序总的平均时间复杂度为O(n2)。
展示评论