排序算法-1（javascript） 冒泡、选择、插入、希尔排序

最近看了小灰的漫画算法，受到启发，对算法有了一些新的认识，所以重新整理了算法排序的文章，把它改版为系列文章，更好的分类查看

什么是稳定的排序算法？

就是两个相同的数的相对顺序不会发生改变，则称之算法是稳定的；反之，则是不稳定的算法
比如原始数列是： 5 8 6 3 6 7
不稳定的排序结果为： 3 5 6 6 7 8
稳定的排序结果为: 3 5 6 6 7 8

排序算法的分类

按照时间复杂度，可以分为：

• O(n^2)的排序算法：

  1. 冒泡排序
  2. 选择排序
  3. 插入排序

• 介于O(n^2)-O(nlogn)之间的排序算法
  希尔排序

• O(nlogn)的排序算法：

  1. 快速排序
  2. 归并排序
  3. 堆排序

• O(n) 的排序算法

  1. 计数排序
  2. 桶排序
  3. 基数排序

排序算法的原理与实现

冒泡排序

• 初始版
  冒泡排序，是指相邻两个数依次比较，如果第一个数比第二个大，则交换位置，则最后一个值为最大值。针对所有元素重复以上步骤，除了每次循环的最后的数，直至没有任何一对数字需要比较为止。
  比如：[4, 5, 1, 2, 9]
  第一次排序：4、5比较，位置不变；5、1比较，交换位置[4, 1, 5, 2, 9]；5、2比较，交换位置[4, 1, 2, 5, 9]；5、9比较，位置不变，结果为[4, 1, 2, 5, 9]，[9]最大，固定不变，作为有序区间
  第二次排序：4、1比较，，交换位置[1, 4, 2, 5, 9]；4、2比较，交换位置[1, 2, 4, 5, 9]；4、5比较，位置不变；结果为[1, 2, 4, 5, 9]，[5, 9]为最后两大数，固定不变，作为有序区间
  第三次排序：1、2比较，无需交换；2、4比较，也无需交换；有序序列为:[4, 5, 9]
  第四次排序：1、2比较，无需交换；有序序列为[2, 4, 5, 9]，剩下1与自身无需比较，所以最后有序序列为： [1, 2, 4, 5, 9]

  • 时间复杂度O(n^2)
  • 最优空间复杂度O(0)
  • 最坏空间复杂度O(n)
  • 平均空间复杂度O(1)
  • 是稳定的排序方法

function bubbleSort(arr) {
  const len = arr.length - 1;
  // 最外层遍历，用来计数有序区间的个数，便于里层遍历得出每轮要比较的无序区间
  for(let i = 0; i < len; i++) {
    for(let j = 0; j < len - i; j++) {
      if(arr[j] > arr[j + 1]) {
        // let temp = arr[j + 1]
        // arr[j + 1] = arr[j]
        // arr[j] = temp
        // 以上三句，可以使用ES6的解构赋值进行优化
        [ arr[j], arr[j+1] ] = [ arr[j+1], arr[j] ]
      }
    }
  }
  return arr
}
const arr = bubbleSort([4, 1, 2, 5, 9])
console.log(arr); // [1, 2, 4, 5, 9]

• 优化版2
  我们看下，其实[4, 5, 1, 2, 9]到第三轮比较时，[1,2,4,5,9]就已经是个有序队列了，但是冒泡还要要继续到n-1轮，这无疑是浪费的。所以我们可以判断每轮是否发生了交换来判断剩下的是不是已经为有序队列了

function secondBubbleSort(arr) {
  const len = arr.length;
  for(let i = 0; i < len; i++) {
    let isChanged = false; // 用来记录有没交换过数据
    for(let j = 0; j < len - i -1; j++) {
      if(arr[j + 1] < arr[j]) {
        [ arr[j], arr[j+1] ] = [ arr[j+1], arr[j] ]
        isChanged = true
      }
    }
    // 如果没交换过数据，那就代表剩下的是有序区间，就可以不用再比较啦
    if(!isChanged) {
      break;
    }
  }
  return arr;
}
const arr = secondBubbleSort([4, 1, 2, 5, 9])
console.log(arr); // [1, 2, 4, 5, 9]

• 优化版3
  我们换个队列，[3, 2, 1, 4, 5, 6, 7]，按照优化版2，已经可以从6轮比较优化到比较2轮就可以得到结果。
  第1轮结果为：[2, 1, 3, 4, 5, 6, 7]
  第2轮结果为：[1, 2, 3, 4, 5, 6, 7]
  但是看下每轮的比较，可以看到1后面的队列[4, 5, 6, 7] ，其实本身就是有序的，但按照冒泡，还是第轮都得和后面有序队列的每个数依次进行比较。可不可以优化呢？其实只要记录下最后一次交换的下标，就可以得到已有的有序区间了。
  比如第1轮比较，第一次交换3、2后得到2、3， 第二次交换也就是最后一次交换3、1，得到1、3，记录下最后交换位置下标也就是数字1的位置下标1，后面的序列[3, 4, 5, 6, 7]就是都是有序队列了。

function thirdBubbleSort(arr) {
  const len = arr.length;
  let changedIndex = 0 // 每次交换的位置下标
  let lastChangedIndex = 0 // 每轮冒泡结束后的最后位置下标
  for(let i = 0; i < len; i++) {
    let isChanged = false; // 用来记录有没交换过数据 
    for(let j = 0; j < len - 1 - lastChangedIndex; j++) {
      if(arr[j + 1] < arr[j]) {
        [ arr[j], arr[j+1] ] = [ arr[j+1], arr[j] ]
        isChanged = true
        // 更新每次交换的位置下标
        changedIndex = j
      }
    }
    lastChangedIndex = changedIndex
    // 如果没交换过数据，那就代表剩下的是有序区间，就可以不用再比较啦
    if(!isChanged) {
      break;
    }
  }
  return arr;
}
const arr = thirdBubbleSort([3, 2, 1, 4, 5, 6, 7])
console.log(arr); // [1, 2, 3, 4, 5, 6, 7]  

选择排序

选择排序的思想是：每一趟取出最大（或最小）的值，放到队伍最后面（或最前），下一次排序第二大值放在末尾第二位，如此循环在无序队列继续此操作，直至无序队列为空为止
比如： [3, 1, 5, 0, 7]

1. 第一次循环，找到7最大，放至末尾[3, 1, 5, 0, 7]
2. 第二次循环，找到5最大，放到末尾第二位，[3, 1, 0, 5, 7]
3. 第三次循环，找到3最大，放到末尾第三位，[0, 1, 3, 5, 7]
4. 第四次循环，找到1最大，放到末尾第四位，[0, 1, 3, 5, 7]
5. 第五次循环，发现只剩0，放到第一位，不变，结束

• 时间复杂度：总次数为(n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n^2)
• 是不稳定的排序算法

function selectSort(arr){
  const len = arr.length;
  for(let i =0; i < len; i++) {
    let maxNum = arr[0]
    let maxIndex = 0;
    for(let j=0; j < len -i; j++) {
      if(arr[j] > maxNum) {
        maxNum = arr[j];
        maxIndex = j;
      }
    }
    if(maxIndex !== len - i -1) {
      arr[maxIndex] = arr[len - i -1]
      arr[len - i -1] = maxNum;
    }
  }
  return arr;
}
const arr = selectSort([3,1,2,5,2,9,4, 10,12, 5])
console.log(arr);

插入排序

参考资源：https://baike.baidu.com/item/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F/7214992?fr=aladdin
思想：已知一个排好的序列数组，插入的数值依次从后往前与前面的数字比较，如果比前面的数字大，则插入到前面数字的后面
例子：[3, 1, 2]
第1次：3和1比较，3比1大，交换位置，[1, 3, 2]
第2次：2和3比较，3比2大，交换位置，[1, 2, 3]
第3次：2和1比较，1比2小，保持位置不变，至此，结果为[1, 2, 3]

• 最优解: 只用比较n-1次
• 最坏解：O（n^2）
• 时间复杂度：O(n^2)
• 空间复杂度：常量，O(1)

// 插入排序算法实现：
function insertSort(arr) {
  const len = arr.length;
  for(let i = 1; i < len; i++) {
    let preIndex = i - 1;
    const key = arr[i]
    while(preIndex >= 0 && arr[preIndex] > key) {
      arr[preIndex + 1] = arr[preIndex]
      preIndex -= 1
    }
    arr[preIndex + 1] = key
  }
  console.log(arr)
}
insertFunc([1,3,2,5,2,9,5,4])
// >>> [ 1, 2, 2, 3, 4, 5, 5, 9 ]

希尔排序

参考： https://github.com/sisterAn/JavaScript-Algorithms/issues/75
又叫缩小增量排序，就是把数组进行分组，每个分组内分别进行插入排序，然后逐渐将分组变少，再分别进组插入排序，如此循环直至分组变为1时，将整个数组看成一个分组，进行最后的插入排序。一般我们将每次分组设为数组长度的一半，每次分组依次对半，直到分组1
比如： [1, 4, 2, 8, 3, 9]
第一次排序，len= 6, 6/2 = 3, 所以间隔是3,分成3组，则 8和1进行比较，位置不变；4和3进行比较，交换位置；9和2比较，位置不变；结果为[1, 3, 2, 8, 4, 9]
第二次排序, 3/2 = 1, 间隔为1，将整个数组当成一个分组，进行插入排序，结果为：[1, 2, 3, 4, 8, 9]

• 时间复杂度O(nlogn)
• 空间复杂度为O(1)

function shellSort(arr) {
  const len = arr.length;
  for(let gap = Math.floor(len/2); gap > 0; gap = Math.floor(gap/2)) {
    console.log("gap:", gap)
    for(let i = gap; i < len; i ++) {
      let key = arr[i]
      let j = i;
      while(j - gap >= 0 && arr[j - gap] > key) {
        arr[j] = arr[j - gap]
        j = j - gap;
      }
      arr[j] = key;
    }
    console.log(arr);
  }
  return arr
}
const arr = shellSort([1,3,2,5,2,9,5,4])

参考：漫画算法（魏梦舒，@程序员小灰），力荐入门级算法书哦

排序算法系列文章传送门(未完，持续更新中)：
排序算法-1（javascript） 冒泡、选择、插入、希尔排序的实现
排序算法-2（javascript） 快速排序的实现
排序算法-3（javascript） 堆排序的实现
排序算法-4（javascript） 归并排序的实现