一些常见排序算法

5种排序

大致上，平时需要用到的算法有如下几种:

1. 冒泡排序
2. 选择排序
3. 计数排序
4. 快速排序
5. 插入排序
6. 归并排序

冒泡排序

这个排序的算法很简单，其实就是比较相邻两个元素的大小，然后交换,代码如下

/**
 * 冒泡排序
 * 排序为从小到大
 * 输入的参数是一个包含正整数的一维数组
 * 返回的值也是一个一维数组
 * @param   {Array}  array  [数组]
 * @return  {Array}
 */
function bubbleSort(array) {
  if (!array) return null;
  let indexOfLastUnsortedElement = array.length - 1;
  let newArray = [];
  let isSwapped = true;
  while (isSwapped) {
    isSwapped = false;
    for (let i = 0; i < indexOfLastUnsortedElement; ++i) {
      if (array[i] > array[i+1]) {
        newArray = swap(array, i, i+1);
        isSwapped = true;
      }
    }
    --indexOfLastUnsortedElement;
  }
  return newArray;
}
function swap(array, preIndex, nextIndex) {
  let temp = array[preIndex];
  array[preIndex] = array[nextIndex];
  array[nextIndex] = temp;
  return array;
}

其中需要注意的地方就是 isSwapped 这个标识位，没有这个标识位的话，在一些情况下会做重复两两判断的操作，这里实际上就是一个优化,以下是其动图演示

选择排序

每次选择这个数组的已经排好序的最后一个作为最大/小值(默认第一个是已经排好序的), 然后拿这个值依次与后面的值进行比较，比它大/小就记下它当时的下标，并且把这个值更新 为最大/小值，轮完一圈之后利用当时存的下标就可以与已经排好序的最后一个数交换，完成一轮排序操作，后面的以此类推

/**
 * 选择排序
 * 排序为从小到大
 * 输入的参数是一个包含正整数的一维数组
 * 返回的值也是一个一维数组
 * @param   {Array}  array  [数组]
 * @return  {Array}
 */
function selectionSort(array) {
  if (!array) return null;
  let newArray = [];
  for (let i = 0; i < array.length - 1; ++i) { // 从第 i 个开始
    // 重新对最小值以及最小下标进行赋值
    let minIndex = i;
    let minVal = array[i];
    for (let j = i + 1; j < array.length; ++j) { // 从第 i+1 个开始
      if (array[j] < minVal) {
        minIndex = j; // 记住最小值下标,为交换最准备
        minVal = array[j]; // 啊，中央就决定，你是最小值了!
      }
    }
    // 比完这一轮之后就 swap
    newArray = swap(array, minIndex, i);
  }
  return newArray;
}
function swap(array, preIndex, nextIndex) {
  let temp = array[preIndex];
  array[preIndex] = array[nextIndex];
  array[nextIndex] = temp;
  return array;
}

算法动态显示如下

计数排序

本质上这个就是用一个数组，将输入的数字作为这个数组的下标，然后当遇到一个相同数字的时候，对应这个下标的值就自增，最后再对这个已经按照顺序存放好数据的数组进行排序

/**
 * 计数排序
 * 排序为从小到大
 * 输入的参数是一个包含正整数的一维数组
 * 返回的值也是一个一维数组
 * @param   {Array}  array  [数组]
 * @return  {Array}
 */
function countingSort(array) {

  if (!array) return null;

  // 将数据弄到 bucket 里面
  // 每个 bucket[index] 里面的值是 array[i] 重复出现的次数
  let bucket = [];
  for (let i = 0; i < array.length; ++i) {
    let index = array[i];
    if (!bucket[index]) bucket[index] = 0;
    bucket[index] ++;
  }

  // 然后取出来排序
  let newArray = [];
  for (let i = 0; i < bucket.length; ++i) {
    for (let j = 0; bucket[i] && j < bucket[i]; ++j) {
      newArray.push(i);
    }
  }

  return newArray;
}

算法动态显示如下

快速排序

首先需要从这个数列中挑选出一个基准数,然后对这个数列做如下的排列

• 所有大于该基准数的数都放在这个数列的右边
• 所有小于该基准数的数都放在这个数列的左边

完成这样的分割之后，再递归的重复上述操作，直到排列好的数列的长度小于 2 就返回(return)

还有一个就是随机快速排序的改进版本，其实区别就在于挑选基准数这个规则上，它是随机的

/**
 * 快速排序
 * 从数列中挑出一个元素，称为“基准”（pivot），
 * 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）
 * 在这个分割结束之后，该基准就处于数列的中间位置。这个称为分割（partition）操作。
 * 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序
 * 排序为从小到大
 * 输入的参数是一个包含正整数的一维数组
 * 返回的值也是一个一维数组
 * @param   {Array}   array           [数组]
 * @param   {Number}  pivotIndex      [基准数下标]
 * @param   {Number}  rightMostIndex  [右边最远下标]
 * @return  {Array}
 */
function quickSort(array, pivotIndex, rightMostIndex) {
  if (!array) return null;
  if (pivotIndex >= rightMostIndex) {
    return;
  }

  // 设置基准数
  let pivot = pivotIndex;

  // 先存一下基准下标
  let storeIndex = pivotIndex;
  // 向右找
  for (let i = pivotIndex + 1; i <= rightMostIndex; ++i) {
    // 若找到一个比基准数还小的数
    if (array[i] < array[pivot]) {
      // 与这个数交换
      array = swap(array, i, ++storeIndex);
    }
  }
  // 快排一个小于基准数的子集合已经弄在一起了，但还是需要交换顺序
  array = swap(array, pivot, storeIndex);

  // 现在可以递归了
  quickSort(array, pivotIndex, storeIndex - 1);
  quickSort(array, storeIndex + 1, rightMostIndex);

  return array;
}
function swap(array, preIndex, nextIndex) {
  let temp = array[preIndex];
  array[preIndex] = array[nextIndex];
  array[nextIndex] = temp;

  return array;
}

算法动态显示如下

插入排序

这个跟打牌的道理是一样的，它需要经历以下步骤

1. 默认取数列的第一个为已经为排好序的序列
2. 然后取剩下的没有排好序的序列的第一个数，从已经排好序的序列的最后一位开始比较
3. 如果 没有排好序列的第一个数 比较小,就移动数组将它插入到前面去
4. 反复比较，最后插入

/**
 * 插入排序
 * 排序为从小到大
 * 输入的参数是一个包含正整数的一维数组
 * 返回的值也是一个一维数组
 * @param   {Array}  array  [数组]
 * @return  {Array}
 */
function insertionSort(array) {
  if (!array) return null;
  let val = 0;
  let j = 0;
  for (let i = 1; i < array.length; ++i) { // 数组第一个默认排序好
    // 取出元素 X
    val = array[i];
    for (j = i - 1; j >= 0 && (array[j] > val); --j) { // 已经排好序的前面的数列倒着与元素 X 比较
      // 先让排好序的元素后移
      array[j+1] = array[j];
    }
    // 让元素 X 插到前面去
    array[j+1] = val;
  }
  return array;
}

算法动态显示如下

归并排序

这种归并的算法就用到了”分治”的思想,就是指将两个已经排序的序列合并成一个序列的操作,该操作需要以下步骤

1. 先把长度为 n 的数组分成两半
2. 然后把调用排序函数递归排序(merge sort)
3. 最后将数组的左边和右边进行合并(merge)

/**
 * 插入排序
 * 排序为从小到大
 * 输入的参数是一个包含正整数的一维数组
 * 返回的值也是一个一维数组
 * @param   {Array}  array  [数组]
 * @return  {Array}
 */
function mergeSort(array) {
  if (!array) return null;

  if (array.length === 1) {
    return array;
  }

  // 将数组分成两半
  let n = parseInt(array.length / 2);
  let left = array.slice(0, n);
  let right = array.slice(n);

  // 递归排序
  left = mergeSort(left);
  right = mergeSort(right);

  // 将数组左半边和右半边合并
  return merge(left, right);
}
function merge(left, right) {
  let final = [];
  while (left.length && right.length) {
    // 依次取出最小放到 final 里面
    final.push(left[0] <= right[0] ? left.shift() : right.shift());
  }
  // 剩下的 left.concat(right) 的值就是最大的
  // 然后再 final.concat(left.concat(right)) 将最后的这个最大数连接起来
  return final.concat(left.concat(right));
}

算法动态显示如下

算法复杂度

见下表

排序方法	时间复杂度(平均)	时间复杂度(最坏)	时间复杂度(最优)	空间复杂度	稳定性
冒泡排序	O(n^2)	O(n^2)	O(n)	O(1)	稳定
选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定
计数排序	O(n+k)	O(n+k)	O(n+k)	O(n+k)	稳定
快速排序	O(nlogn)	O(n^2)	O(nlogn)	O(nlogn)	不稳定
插入排序	O(n^2)	O(n^2)	O(n)	O(1)	稳定
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定

其他一些常用算法

二分查找

二分查找是建立在被查找的数组是一个有序序列的基础上的，想法也是很朴素的，即找一个中间的数，若被查找的数小于这个中间的数，那么必然往数组更小的方向去找;若被查找的数大于这个中间的数，那么必然往数组更大的方向去找，然后在下一次找的时候取一个要查找范围的中间数，以此类推,这里尝试用递归的思路实现

/**
 * 二分查找算法
 * 方式是递归查找
 * @param   {Array}  array  [数组]
 * @param   {Number} low    [起始下标]
 * @param   {Number} high   [终点下标]
 * @param   {Number} target [查找目标数]
 * @return  {Number} mid    [查找到的数对应的下标]
 */
function binarySearch(array, low, high, target) {
  if (!array) return null;
  if (low > high)
    return -1;
  var mid = parseInt((high + low) / 2);
  if (array[mid] > target)
    return binarySearch(array, low, mid - 1, target);
  if (array[mid] < target)
    return binarySearch(array, mid + 1, high, target);
  return mid;
}

翻转二叉树

经常被人吐槽说若去面试 google,连这道面试题都答不出来的就可以滚了，2333。一个简单的实现就是递归翻转这个二叉树，然后将得到的这个递归出来的节点的左边指向它的右边,将得到的这个递归出来的节点的右边指向它的左边,代码如下

/**
 * 简单翻转二叉树算法
 * @param   {Object}  node  [一颗树的对象]
 * @return  {Object}  node  [一颗树的对象]
 */
function reverseBinaryTree(node) {
  if (!node) {
    return;
  }

  let left = reverseBinaryTree(node.left);
  let right = reverseBinaryTree(node.right);

  node.left = right;
  node.right = left;

  return node;
}

打印二叉树

用递归

function printTree(prefix, node, isLeft) {
  if (node) {
    console.log(prefix + (isLeft ? "|-- " : "\\-- ") + node.value);
    printTree(prefix + (isLeft ? "|   " : "    "), node.left, true);
    printTree(prefix + (isLeft ? "|   " : "    "), node.right, false);
  }
}

桶排序

桶排序是计数排序的升级版，比如像这样的数组

[0, 56, 1, 1, 3, 67]

桶排序算法相对于计数排序升级的地方主要在于其 hash 的存储方式，如下

hash: {
    0: [0],
    1: [1,1],
    2:[],
    3:[],
    4:[],
    5:[],
    ...,
    56:[56],
    67:[67],
}

其实可以看出来，就像是一个数组里面又存放了一个数组,很像二维数组 的存储方式
其本质上就是将数组中重复的数放到这个有限数量的桶里面，然后再次对这个桶里面的数组进行排序,具体实现在 代码链接

基数排序

就是根据 [基数] 来排序，比如有如下数组

23 202 103 566 32 617 37

hash 的存储情况如下

hash: {
    '0': undefined,
    '1': undefined,
    '2': [202,32],
    '3': [23,103],
    '4': undefined,
    '5': undefined,
    '6': [566],
    '7': [617,37],
    '8': undefined,
    '9': undefined,
}

思路就是，第一次比较个位，第二次比较十位，第三次比较百位，第四次比较千位…,然后把排列好的序列从桶里面抽出来,放到原来的数组中去,然后再次重复上述操作,这里需要注意的是每个桶都是一个队列,可以利用队列先进先出的特性来排。所以基数排序是在在桶排序的基础上优化而来的，目的是解决桶排序中待排序数字跨度过大,需要使用很多桶空间的问题。桶排序很简单，但是很浪费桶资源,但是对于基数排序，桶的个数是固定的。
具体实现在 代码链接

堆排序

堆可以视为一颗完全的二叉树，完全二叉树的一个性质是，除了最底层之外，每一层都是满的，这使得堆可以用数组来表示,特点就是最大的数在最上面
这里有个关键的地方，叫做 最大堆调整
具体实现在 代码链接

算法特征归纳

• 输入: 一个算法必须有零个或以上输入量
• 输出: 一个算法应有一个或以上输出量，输出量是算法计算的结果
• 明确性: 算法的描述必须无歧义，以保证算法的实际执行结果是精确地匹配要求或期望，通常要求实际运行结果是确定的
• 有限性: 一个算法是能够被任何图灵完备系统模拟的一串运算，而图灵机只有有限个状态，有限个输入符号和有限个转移函数(指令)
• 有效性: 可行性，算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现

参考网站

网站 排序可视化