排序算法

排序算法总结

排序算法	平均时间复杂度	稳定性
冒泡排序	O(n2)	稳定
选择排序	O(n2)	不稳定
插入排序	O(n2)	稳定
希尔排序	O(n1.5)	不稳定
快速排序	O(N*logN)	不稳定
归并排序	O(N*logN)	稳定
堆排序	O(N*logN)	不稳定
基数排序	O(d(n+r))	稳定

一. 冒泡排序(BubbleSort)

基本思想：两个数比较大小，较大的数下沉，较小的上浮。

过程：

比较相邻的两个数据，如果第二个数小，就交换位置。
从后向前两两比较，一直到比较最前两个数据。最终最小数被交换到起始的位置，这样第一个最小数的位置就排好了。
继续重复上述过程，依次将第2.3...n-1个最小数排好位置。

let stateOld = [56, 65, 36, 12, 5, 5, 27, 37, 52]
    let length = stateOld.length
    for(let i = 0; i < length - 1; i++) {
      for(let j = length - 1; j > 0;j--) {
        if(stateOld[j] < stateOld[j-1]) {
          stateOld[length] = stateOld[j-1]
          stateOld[j-1] = stateOld[j]
          stateOld[j] = stateOld[length]
        }
      }
    }
    console.log(stateOld) // [5, 5, 12, 27, 36, 37, 52, 56, 65, 56]