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均达到最小值：C_min = n - 1，M_min = 0。
  所以，冒泡排序最好的时间复杂度为O_n。

• 若初始文件是反序的，需要进行 n - 1 趟排序。每趟排序要进行 n - i 次关键字的比较( 1 ≤ i ≤ n-1 )，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：
  

• 冒泡排序的最坏时间复杂度为O(n²)。
• 综上，因此冒泡排序总的平均时间复杂度为O(n²)。