前言

最近正在准备前端实习岗的面试，在诸多岗位的面试中，排序算法可以说是面试官必问的题目，这里对八大排序做一下总结，一来巩固一下最近复习的知识，而来方便以后再看。

冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名。
算法思路：

  1. i 从 0 开始，i 与 i+1 比较，如果 i>i+1，那么就互换
  2. i 不断增加，直到 i<n-1（n 是数组元素的个数，n-1 是数组已经最后一个元素） ，一趟下来，可以让数组元素中最大值排在数组的最后面
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * 冒泡排序 稳定
 * @param {*} arr
 */
function bubbleSort(arr) {
  let len = arr.length
  //外层循环是排序的趟数
  for (let i = 0; i < arr.length; i++) {
    //一种优化的方法，记录是否发生了置换， 0 表示没有发生置换、 1 表示发生了置换
    var isChanged = 0
    //内层循环是当前趟数需要比较的次数
    for (let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        var temp = arr[j + 1] //元素交换
        arr[j + 1] = arr[j]
        arr[j] = temp

        isChanged = 1
      }
    }
    //如果比较完一趟没有发生置换，那么说明已经排好序了，不需要再执行下去了
    if ((isChanged = 0)) {
      break
    }
  }
  return arr
}

选择排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始(末尾)位置，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个 5 挪动到第二个 5 后面）。

它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始(末尾)位置，直到全部待排序的数据元素排完

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 选择排序 不稳定
 * @param {} arr
 */
function selectionSort(arr) {
  var len = arr.length
  // 定义最小值的下标和临时变量
  var minIndex, temp
  for (var i = 0; i < len - 1; i++) {
    minIndex = i
    for (var j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        //寻找最小的数
        minIndex = j //将最小数的索引保存
      }
    }
    temp = arr[i]
    arr[i] = arr[minIndex]
    arr[minIndex] = temp
  }
  return arr
}

插入排序

插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为 O(n^2)。是稳定的排序方法。
算法思路：

  1. 首先将已排序的数据看成一个整体
  2. 一个数组是需要 n-1 趟排序的，总是用后一位跟已排序的数据比较(第一趟：第二位跟已排序的数据比，第二趟：第三位跟已排序的数据比）
  3. 用第三位和已排序的数据比，实际上就是让第三位数跟两个数比较，只不过这两个数是已经排好序的而已。而正是因为它排好序的，我们可以使用一个循环就可以将我们比较的数据插入进去
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 插入排序 稳定
 * @param {*} arr
 */
function insertionSort(arr) {
  var len = arr.length
  var preIndex, current
  for (var i = 1; i < len; i++) {
    // 记录前一个元素下标
    preIndex = i - 1
    // 当前元素
    current = arr[i]
    while (preIndex >= 0 && arr[preIndex] > current) {
      // 前一个元素向后移动一位
      arr[preIndex + 1] = arr[preIndex]
      // 再往前一个元素进行比较
      preIndex--
    }
    // 找到了合适我的位置，将当前元素插入
    arr[preIndex + 1] = current
  }
  return arr
}

优化：
二分查找插入排序的原理：是直接插入排序的一个变种，区别是：在有序区中查找新元素插入位置时，为了减少元素比较次数提高效率，采用二分查找算法进行插入位置的确定。

快速排序

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
算法思路：
在数组中找一个支点(任意),经过一趟排序后，支点左边的数都要比支点小，支点右边的数都要比支点大！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * 快速排序 不稳定
 * @param {*} arr
 */
function quickSort(arr) {
  if (arr.length <= 1) {
    return arr
  }
  // 取数组的中间元素作为基准
  var pivotIndex = Math.floor(arr.length / 2)
  // 删除中间元素，并获取它
  var pivot = arr.splice(pivotIndex, 1)[0]

  var left = []
  var right = []

  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      // 都比中间值小的数
      left.push(arr[i])
    } else {
      // 都比中间值大的数
      right.push(arr[i])
    }
  }
  // 递归
  return quickSort(left).concat([pivot], quickSort(right))
}

优化：

  1. 随机选取基准值 base(支点随机选取)
  2. 配合着使用插入排序(当问题规模较小时，近乎有序时，插入排序表现的很好)
  3. 当大量数据，且重复数多时，用三路快排

归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
算法思路：

  1. 第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
  2. 第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
  3. 第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
  4. 重复步骤 3 直到某一指针超出序列尾
  5. 将另一序列剩下的所有元素直接复制到合并序列尾
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * 归并排序
 * @param {*} arr
 */
function mergeSort(arr) {
  var len = arr.length
  if (len < 2) {
    return arr
  }
  var middle = Math.floor(len / 2)
  //   分割数组
  var left = arr.slice(0, middle)
  var right = arr.slice(middle)
  return merge(mergeSort(left), mergeSort(right))
}

/**
 * 合并数组
 * @param {*} left
 * @param {*} right
 */
function merge(left, right) {
  var result = []
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      // 从左数组头部取出一个元素放入结果数组
      result.push(left.shift())
    } else {
      result.push(right.shift())
    }
  }

  while (left.length) result.push(left.shift())

  while (right.length) result.push(right.shift())

  return result
}

堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。
完全二叉树有个特性：左边子节点位置 = 当前父节点的两倍 + 1，右边子节点位置 = 当前父节点的两倍 + 2
简单来说：堆排序是将数据看成是完全二叉树、根据完全二叉树的特性来进行排序的一种算法

  1. 最大堆要求节点的元素都要不小于其孩子，最小堆要求节点元素都不大于其左右孩子
  2. 那么处于最大堆的根节点的元素一定是这个堆中的最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
var len // 全局变量——数组的长度

/**
 * 建立大顶堆
 * @param {*} arr
 */
function buildMaxHeap(arr) {
  len = arr.length
  for (var i = Math.floor(len / 2); i >= 0; i--) {
    heapify(arr, i)
  }
}

/**
 * 交换数组
 * @param {*} arr
 * @param {*} i
 * @param {*} j
 */
function swap(arr, i, j) {
  var temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}

/**
 * 建堆
 * @param {*} arr
 * @param {*} i
 */
function heapify(arr, i) {
  var left = 2 * i + 1
  var right = 2 * i + 2
  var max = i

  if (left < len && arr[left] > arr[max]) {
    max = left
  }
  if (right < len && arr[right] > arr[max]) {
    max = right
  }

  if (max != i) {
    swap(arr, i, max)
    heapify(arr, max)
  }
}

/**
 * 堆排序
 * @param {*} arr
 */
function heapSort(arr) {
  buildMaxHeap(arr)
  for (var i = arr.length - 1; i > 0; i--) {
    swap(arr, 0, i)
    len--
    heapify(arr, 0)
  }
  return arr
}

希尔排序

希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。
算法思路：

  1. 希尔排序在排序前：将一个序列分成了好几个序列
  2. 在第一趟排序时：将这几个序列做插入排序。排序后，部分较大的数字往后靠，部分较小的数字往前靠
  3. 在第二趟排序时：将这个序列又分了好几个序列做插入排序(但比第一次分的数要少,ps:如果第一次分 5 个，第二次可能就 2 个了)。排序后，部分较大的数字往后靠，部分较小的数字往前靠
  4. …………….
  5. 在第 n 趟排序时：将这个序列又分了好几个序列(直到剩下一个序列)，从宏观上看，此序列就基本是有序的了。这时就用简单插入排序将数列直至已序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 希尔排序
 * @param {*} arr
 */
function shellSort(arr) {
  var len = arr.length,
    temp,
    gap = 1
  while (gap < len / 3) {
    //动态定义间隔序列
    gap = gap * 3 + 1
  }
  for (gap; gap > 0; gap = Math.floor(gap / 3)) {
    for (var i = gap; i < len; i++) {
      temp = arr[i]
      for (var j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
        arr[j + gap] = arr[j]
      }
      arr[j + gap] = temp
    }
  }
  return arr
}

基数排序

从来没有接触过的一个排序算法额……..
算法思路：

  1. 第一趟桶排序将数字的个位数分配到桶子里面去，然后回收起来，此时数组元素的所有个位数都已经排好顺序了
  2. 第二趟桶排序将数字的十位数分别分配到桶子里面去，然后回收起来，此时数组元素的所有个位数和十位数都已经排好顺序了(如果没有十位数、则补 0)
  3. 第三趟桶排序将数字的百位数分别分配到桶子里面去，然后回收起来，此时数组元素的所有个位数和十位数和百位数都已经排好顺序了(如果没有百位数、则补 0)
  4. …………………………….
  5. 直至全部数(个、十、百、千位…)排好顺序，那么这个数组就是有序的了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
var counter = []
/**
 * 基数排序
 * @param {*} arr
 * @param {*} maxDigit
 */
function radixSort(arr, maxDigit) {
  var mod = 10
  var dev = 1
  for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
    for (var j = 0; j < arr.length; j++) {
      var bucket = parseInt((arr[j] % mod) / dev)
      if (counter[bucket] == null) {
        counter[bucket] = []
      }
      counter[bucket].push(arr[j])
    }
    var pos = 0
    for (var j = 0; j < counter.length; j++) {
      var value = null
      if (counter[j] != null) {
        while ((value = counter[j].shift()) != null) {
          arr[pos++] = value
        }
      }
    }
  }
  return arr
}