JavaScript-常见排序算法实现方法汇总

常见比较排序
1.冒泡排序
2.选择排序：简单选择排序和堆排序
3.插入排序：直接插入排序和希尔排序
4.快速排序
5.归并排序
常见非比较排序
1.计数排序
2.基数排序
3.桶排序
常见算法的稳定性：
堆排序、快速排序、希尔排序、直接选择排序是不稳定的排序算法，
基数排序、冒泡排序、直接插入排序、归并排序、折半插入排序是稳定的排序算法。

复杂度和稳定性（如图）

排序.png

注释：
n 数据规模
k 桶的个数
In-place 占用常数内存，不占用额外内存
Out-place 占用额外内存

一、冒泡排序（Bubble Sort）--常考

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

1.1 算法描述

• 步骤1：比较相邻的元素，如果第一个比第二个大，就交换它们两个，大的靠后
• 步骤2：对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该是最大的
• 步骤3：针对所有的元素重复以上的步骤，除了最后一个
• 步骤4：重复步骤1~3，直到排序完成。

1.2 动图展示

bubble.gif

1.3 代码演示

function bubbleSort (arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j+1]) {
        let temp = arr[j+1]
        arr[j+1] = arr[j]
        arr[j] = temp
        // 或者用 [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
      }
    }
  }
  return arr
}

1.4 算法分析

• 最佳情况：T(n) = O(n)
• 最差情况：T(n) = O(n^2)
• 平均情况：T(n) = O(n^2)

二、选择排序（Selection Sort）

选择排序是表现最稳定的排序算法之一，因为无论什么数据进去都是O(n^2)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了。
选择排序的工作原理是：首先在未排序的序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾，以此类推，直到排序完成。

2.1 算法描述

n个记录的直接选择排序结果可经过n-1趟直接选择排序得到有序结果。

• 步骤1：取出未排序序列的第一个元素，设为初始最小值，遍历该元素之后的部分并比较大小。
• 步骤2：如果有更小的元素，与该元素交换位置，设为最小的。
• 步骤3：每次遍历找出剩余元素中的最小值并放在已排序序列的最后，如此，n-1趟结束，数组有序化了。

2.2 动图展示

select.gif

2.3 代码演示

function  selectionSort (arr) {
  for (let i = 0; i < arr.length; i++) {
    let min_index = i;
    for (let j = i+1; j < arr.length; j++) {
      if (arr[j] < arr[min_index]) min_index = j
    }
    // 交换两个元素
    let temp = arr[min_index]
    arr[min_index] = arr[i]
    arr[i] = temp
    // 或者[arr[min_index], arr[i]] = [arr[i], arr[min_index]]
  }
  return arr
}

2.4 算法分析

• 最佳情况：T(n) = O(n^2)
• 最差情况：T(n) = O(n^2)
• 平均情况：T(n) = O(n^2)

三、堆排序（Heap Sort）--常考

堆排序是利用堆这种数据结构所设计的一种选择排序算法。堆是一种近似完全二叉树的数据结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。
1、堆是树的一种，当堆的父节点都大于或者都小于子节点时，分别称为最大堆或最小堆。
2、可以用数组来表示树（堆）。从0开始，以数组的第index个元素为堆的父节点，其左右子节点分别为数组的第2index+1和2index+2个元素。
3、已排序的元素将放在数组尾部。

3.1 算法描述

• 步骤1：把数组整理为最大堆的顺序，那么堆的根节点或者说数组的第一个元素，就是最大的值
• 步骤2：排序：把最大值与未排序部分的最后一个元素交换，剩余的部分继续调整为最大值，每次建堆都能找到剩余元素中最大的一个。
  注意：
• 第一次建堆时只需要遍历数组左侧一半元素就够了，并且要从中点向左侧倒序遍历，这样才能保证把最大的元素移动到数组头部
• 排序时，当然就要遍历数组里所有元素了

3.2 动图展示

heap.gif

3.3 代码演示

function heapSort (arr) {
  let len = arr.length
  if (len <= 1) return arr
  // 1. 建最大堆
  // 遍历一半元素即可，必须从中点开始向左遍历
  for (let middle = Math.floor(len/2); middle >= 0; middle--) {
    maxHeapify(arr, middle, len)
  }
  // 2.排序，遍历所有元素
  for (let j = len; j >= 1; j--) {
    // 2.1 将最大的根元素arr[0]与最后一个元素arr[j-1]交换
    swap(arr, 0, j-1)
    // 2.2 剩余的元素继续建最大堆
    maxHeapify(arr, 0, j-2)
  }
  return arr
}
// 建最大堆
function maxHeapify (arr, middle_index, length) {
  // 1. 假设父节点位置的值最大
  let largest_index = middle_index
  // 2. 计算左右节点位置
  let left_index = 2*middle_index + 1,
    right_index = 2*middle_index + 2
  // 3. 判断父节点是否最大
  // 如果没有超出数组长度，并且子节点比父节点大，那么修改最大节点的索引
  // 左边更大
  if (left_index <= length && arr[left_index] > arr[largest_index])
    largest_index = left_index
  // 右边更大
  if (right_index <= length && arr[right_index] > arr[largest_index])
    largest_index = right_index
  // 4. 如果largest_index发生了更新，那么交换父子位置，递归计算
  if (largest_index !== middle_index) {
    swap(arr, middle_index, largest_index)
    // 因为这时一个较大的元素提到了前面，一个较小的元素移到了后面
    // 小元素的新位置之后可能还有比它更大的，需要递归
    maxHeapify(arr, largest_index, length)
  }
}
function swap (arr, a, b) {
  let temp = arr[a]
  arr[a] = arr[b]
  arr[b] = temp
}

3.4 算法分析

• 最佳情况：T(n) = O(nlogn)
• 最差情况：T(n) = O(nlogn)
• 平均情况：T(n) = O(nlogn)

四、插入排序（Insertion Sort）

插入排序是一种简单直观的排序算法。其工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用In-place排序（即只需要用到O(1)的额外空间排序），因此从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
注：插入排序将已排序的数组放在数组前面。

4.1 算法描述

• 步骤1：从第一个元素开始，该元素可以认定为已排序
• 步骤2：取出下一个元素，在已经排序的元素序列中从后向前扫描
• 步骤3：如果该元素（已排序）大于新元素，将该元素向后挪一位置
• 步骤4： 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
• 步骤5：将新元素插入到该位置后。
• 步骤6：重复步骤2-5

4.2 动图展示

insert.gif

4.3 代码演示

// 第一种一般写法
function insertionSort (arr) {
  for (let index = 1; index < arr.length; index++) {
    // 取出一个未排序元素
    let current_ele = arr[index]
    // 已排序元素的最后一个的位置
    let ordered_index = index - 1
    while (arr[ordered_index] >= current_ele && ordered_index >= 0) {
      // 使用前面的值覆盖当前的值
      arr[ordered_index + 1] = arr[ordered_index]
      // 向前移动一个位置
      ordered_index--
    }
    // 遍历完成，前面的元素都比当前元素小，把未排序元素赋值进去
    arr[ordered_index + 1] = current_ele
  }
  return arr
}
// 第二种结合冒泡排序的写法
function insertionSort (arr) {
  for (let i = 0; i < arr.length; i++) {
    // 对前面已排序的数组和新选出来的元素执行一趟冒泡排序
    for (let j = i + 1; j >= 0; j--) {
      if (arr[j] < arr[j-1]) {
        let temp = arr[j]
        arr[j] = arr[j-1]
        arr[j-1] = temp
      }
    }
  }
  return arr
}

4.4 算法分析

• 最佳情况：T(n) = O(n)
• 最差情况：T(n) = O(n^2)
• 平均情况：T(n) = O(n^2)

五、希尔排序（Shell Sort）

希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，它与插入排序的不同之处在于，它会优先比较距离比较远的元素。首先指定一个增量gap，对数组分组，使得每相距gap-1的元素为一组，共分成gap组，对每组执行插入排序，逐步缩小gap的大小并继续执行插入排序，直到为1，也就是整个数组为一组，对整个数组进行插入排序。gap对排序结果没有影响，只是影响了算法效率。

5.1 算法描述

设置增量gap=length/2，缩小增量继续以gap=gap/2的方式，

• 步骤1：共三层循环，外层循环用来逐步减少gap的值
• 步骤2：中层与内层两层循环基本上就是插入排序，细节上的不同直接看代码就好。

5.2 动图展示

shell.png

5.3 代码演示

// 第一种写法
function shellSort (arr) {
  // 外层循环逐步缩小增量gap的值
  for (let gap = 5; gap > 0; gap = Math.floor(gap/2)) {
    // 中层和内层是插入排序
    // 普通插入排序从第1个元素开始，这里分组了，要看每个组的第1个元素
    // 共分成了gap组，第一组的第1个元素索引为gap
    // 第一组元素索引为0，0+gap，0+2+gap，...，第二组元素索引为1，1+gap，2+2+gap，...
    for (let i = gap; i < arr.length; i++) {
      let current_ele = arr[i]
      // i每次减少gap，只会与当前元素相隔n*(gap-1)的元素比较，也就是只会与同组的元素比较
      let ordered_index = i - gap
      // 对分组后的数组进行插入排序
      while (ordered_index >= 0 && arr[ordered_index] > current_ele) {
        arr[ordered_index + gap] = arr[ordered_index]
        ordered_index -= gap
      }
      arr[ordered_index + gap] = current_ele
    }
  }
  return arr
}

// 第二种写法，口诀：3 for + 1 if
function shellSort (arr) {
  let length = arr.length
  for (let gap = Math.floor(length/2); gap > 0; gap = Math.floor(gap/2)) {
    for (let i = gap; i < length; i++) {
      for (let j = i - gap; j >= 0; j -= gap) {
        if (arr[j] > arr[j + gap]) {
          [arr[j], arr[j + gap]] = [arr[j + gap], arr[j]] // 交换两个元素
        }
      }
    }
  }
  return arr
}

5.4 算法分析

• 最佳情况：T(n) = O(nlog2n)
• 最坏情况：T(n) = O(nlog2n)
• 平均情况：T(n) = O(nlog2n)

六、快速排序（Quick Sort）--常考

快速排序的工作原理是：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。快速排序是对冒泡排序的一种改进，第一趟排序时将数据分成两部分，一部分比另一部分的所有数据都要小。然后递归调用，在两边都实行快速排序。

6.1 算法描述

快速排序使用分治法将一个串分为两个子串，具体步骤如下：

• 步骤1：从数列里挑一个元素，称为基准（pivot）。比如第一个元素
• 步骤2：重新排序数列，所有比基准小的元素摆放在基准前面，建一个数组；所有比基准大的元素摆放在基准后面，也建一个数组；相同的数可以放在任一边。在这个分区退出之后，该基准就处于数列的中间位置，这个称为分区操作。
• 步骤3：递归地把小于基准元素的子数列和大于基准元素的子数列排序。继续执行步骤1，直到数组只剩1个元素；递归的同时把这三部分连接起来

普通快速排序没有考虑与 pivot 相等的情况，只建了更小和更大的两个数组。
像上面考虑与 pivot 相等的情况时，又叫做[三路快排]。

6.2 动图展示

quick.gif

6.3 代码演示

function quickSort (arr) {
  // 只剩1个元素的话，不能再分割了
  if (arr.length <= 1) return arr
  // 取第1个元素为基准值
  let pivot = arr[0]
  // 分割为左小右大两个数组，以及包含元素本身的中间数组
  let left = [], middle = [pivot], right = []
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] === pivot) middle.push(arr[i])
    else if (arr[i] < pivot) left.push(arr[i])
    else right.push(arr[i])
  }
  // 递归并连接
  return quickSort(left).concat(middle, quickSort(right))
}

6.4 算法分析

• 最佳情况：T(n) = O(nlogn)
• 最差情况：T(n) = O(n^2)
• 平均情况：T(n) = O(nlogn)

七、归并排序（Merge Sort）--常考

归并排序始终都是O(nlogn）的时间复杂度，代价是需要额外的内存空间。归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的典型应用，它是一种稳定的排序算法。通过将已有序的子序列合并，得到完全有序的序列，即先使每个子序列有序，再使子序列段间有序，若将两个有序表合并成一个有序表，称为2路归并。

7.1 算法描述

• 步骤1：把长度为n的序列分为两个长度为n/2的子序列
• 步骤2：对这两个子序列分别采用归并排序
• 步骤3：将两个排序好的子序列合并成一个最终的排序序列。

7.2 动图展示

merge.gif

7.3 代码演示

// 分割
function mergeSort (arr) {
  // 如果只剩1个元素，分割结束
  if (arr.length <= 1) return arr
  // 否则继续分成2部分
  let middle_index = Math.floor(arr.length / 2),
    left = arr.slice(0, middle_index),
    right = arr.slice(middle_index)
  return merge(mergeSort(left), mergeSort(right))
}
function merge (left, right) {
  let result = []
  // 当左右两个数组都还没有取完的时候，比较大小然后合并
  while (left.length && right.length) {
    if (left[0] < right[0]) result.push(left.shift()) // 将左边数组中的第一个元素取出存入result
    else result.push(right.shift())
  }
  // 其中一个数组空了，另一个还剩下一些元素
  // 因为是已经排序过的，所以直接concat就好了
  // 注意 concat 不改变原数组
  if (left.length) result = result.concat(left)
  if (right.length) result = result.concat(right)
  return result
}

// 合并

7.4 算法分析

• 最佳情况：T(n) = O(nlogn)
• 最差情况：T(n) = O(n^2)
• 平均情况：T(n) = O(nlogn)

八、二分查找（Binary Search）

二分查找算法，也叫折半查找。它的工作原理是：针对一个有序的数据集合，每次通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间缩小为0。

8.1 算法描述

• 步骤1：从有序数组的最中间元素开始查找，如果该元素正好是指定查找的值，则查找过程结束，否则进行下一步。
• 步骤2：如果指定要查找的元素大于或者小于中间元素，则在数据大于或小于中间元素的那一半区域查找，然后重复第一步
• 步骤3：重复以上过程，直到找到目标元素的索引，查找成功；或者直到子数组为空，查找失败。

8.2 动图展示

binary.png

8.3 代码演示

// 循环查找法
function binarySearch (arr, target) {
  let low = 0, high = arr.length - 1
  while (low <= high) {
    let mid = Math.floor((low + high) / 2)
    if ( target > arr[mid]) {
      low = mid + 1
    } else if (target < arr[mid]) {
      high = mid - 1
    } else { // mid = target
      return mid
    }
  }
  return -1
}

8.4 算法分析

二分查找的时间复杂度为O(logn)。虽然二分查找的时间复杂度为O(logn)但是比很多O(1)的速度都要快，因为O(1)可能标示一个非常大的数值。