初级排序算法

意义：排序算法常常是我们解决其他问题的第一步

选择排序
插入排序
希尔排序

初级算法的意义

这些简单的算法在某些情况下比复杂算法更有效；
它们有助于改进复杂算法的效率

1️⃣ 选择排序

定义

首先，找到数组中最小的那个元素，其次，将它和数组中的第一个元素交换位置。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。

这种方法叫做选择排序，因为它在不断地选择剩余元素之中的最小者。

实现

// 选择排序
function selection (arra) {
  let n = arr.length
  for (let i = 0; i < n; i ++) {
    let min = i
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[min]) {
        min = j
      }
    }
    // 交换元素
    exch(arr, i, min)
  }
  return arr
}

特点

1.运行时间和输入数组的有序度无关

一个已经有序地数组或是全部键都相等的数组和一个元素随机排列的数组所用的排序时间一样长。

2.数据移动是最少的

每次交换都会改变两个数组元素的值，因此总共用了 N 次交换 —— 交换次数和数组的大小是线性关系。

消耗

对于长度为 N 的数组，选择排序需要大约 N²/2 次比较和 N 次交换。

2️⃣ 插入排序

定义

类似于人们整理桥牌，将每一张牌插入到其他已经有序的牌中的适当位置。

实现

function insertion (arr) {
  let n = arr.length
  // 按 arr 升序排列
  for (let i = 1; i < n; i++) {
    for (let j = i; j > 0 && arr[i] < arr[j]; j--) {
      exch(arr, i, j)
    }
  }
  return arr
}

注意：

内层循环初始值 j=i，依次递减
比较操作 arr[i] < arr[j] 放在循环体

优化

要大幅提高插入排序的速度并不难，只需要在内循环中将较大的元素都向右移动而不总是交换两个元素（这样访问数组的次数就能减半）。

特点

对部分有序的数组很有效。

部分有序的数组的定义：

数组中每个元素距离它的最终位置都不远；

一个有序地大数组接一个小数组；

数组中只有几个元素的位置不正确。

消耗

对于随机排列的长度为 N 且主键不重复的数组：

平均情况下插入排序需要 ~ N²/4 次比较以及 ~ N²/4 次交换。
最坏情况下需要 ~ N²/2 次比较和 ~ N²/2 次交换
最好情况下需要 N-1 次比较和 0 次交换

3️⃣ 希尔排序

定义

希尔排序的思想是使数组中任意间隔为 h 的元素都是有序的。这样的数组被称为 h 有序数组。

实现

实现希尔排序的一种方法是对于每个 h，用插入排序将 h 个子数组独立地排序。但因为子数组是相互独立的，一个更简单的方法是在 h- 子数组中将每个元素交换到比它大的元素之前去（将比它大的元素向右移动一格）。只需要在插入排序代码中将移动元素的距离由 1 改为 h 即可。这样，希尔排序的实现就转化为了一个类似于插入排序但使用不同增量的过程。

function Shell (arr) {
  let n = arr.length
  let h = 1
  while (h < n/3) {
    h = 3 * h + 1
  }
  while (h >= 1) {
    // 将数组变为 h 有序
    for (let i = h; i < n; i++) {
      for (let j = i; j >= h && arr[j] < arr[j-h]; j-=h) {
        exch(arr, j, j-h)
      }
    }
    h = parseInt(h/3)
  }
  return arr
}

特点

希尔排序更高效的原因是它权衡了子数组的规模和有序性。

排序之初，各个子数组都很短，排序之后子数组都是部分有序的，这两种情况都很适合插入排序。

这是我们唯一无法准确描述其对于乱序的数组的性能特征的排序方法。

希尔排序比插入排序和选择排序要快得多，并且数组越大，优势越大。

为什么有这么多排序算法？

许多排序算法的性能都和输入模型有很大的关系，因此不同的算法适用于不同应用场景中的不同输入。例如：对于部分有序的小规模的数组，应该选择插入排序。其他限制条件，例如空间和重复的主键，也都是需要考虑的因素。