十大排序算法

术语¶

稳定排序：如果 a 在 b 前，且 a == b，排序后 a 仍然在 b 前，则为稳定排序。
非稳定排序：如果 a 在 b 前，且 a == b，排序后 a 可能不在 b 前，则为非稳定排序。
原地排序(in-place)：在排序过程中不申请多余的存储空间，只利用原来数组存储空间，进行比较和交换的数据来排序。
非原地排序(out-place)：需要申请额外的数组来辅助排序。
时间复杂度：一个算法执行所消耗的时间。
空间复杂度：一个算法执行所需的内存大小。

冒泡排序¶

算法思想¶

一次比较相邻两个元素，如果它们的顺序错误就把它们交换过来。

代码¶

function bubbleSort(arr) {
  const len = arr.length;
  for(let i = 0; i < len; i++) {
    for(let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

算法效率¶

比较次数：O(n^{2)，交换次数：O(n}2)
时间复杂度：O(n^2)，空间复杂度：O(1)，稳定排序，原地排序

选择排序¶

算法思想¶

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

代码¶

function selectionSort(arr) {
  const len = arr.length;
  for(let i = 0; i < len; i++) {
    let minIndex = i;
    for(let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    // 交换
    let temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
}

算法效率¶

比较次数：O(n^2)，交换次数：O(n)
时间复杂度：O(n^2)，空间复杂度：O(1)，不稳定排序，原地排序

插入排序¶

打扑克牌时，每摸起一张牌，通常按牌的大小进行插入排序。

算法思想¶

把未排序的元素，一个一个地插入到有序的集合中。

拿到一个未排序的元素，
从后向前扫描已排序的序列，
找到相应的位置并插入。

代码¶

function insertionSort(arr) {
  const len = arr.length;
  for(let i = 1; i < len; i++) {
    let current = arr[i]; // 待插入数据
    let j = i - 1;
    for(; j >= 0 && current < arr[j]; j--) {
      arr[j + 1] = arr[j];
    }
    arr[j + 1] = current;
  }
}

算法效率¶

比较次数 O(n^2)，交换次数 O(n^2)
时间复杂度 O(n^2)，空间复杂度 O(1)，稳定排序，原地排序

希尔排序（Shell Sort）¶

希尔排序是 插入排序 的一种更高效率的实现，核心在于增量的设置。

算法思想¶

希尔排序是把记录按下标的一定增量分组；
对每组使用 插入排序 算法排序；
增量逐渐减少，当增量减至1时，所有记录被分成一组，算法终止。

示例：采用 希尔增量，选择增量 gap = length / 2，继续缩小增量 gap = gap / 2，这种增量选择可以用一个序列来表示，{n/2, (n/2)/2 … 1}，称为 增量序列。

代码¶

function shellSort(arr) {
  const len = arr.length;
  let gap = Math.floor(len / 2);
  while(gap >= 1) {
    /* --- 插入排序 --- */
    for(let i = gap; i < len; i++) {
      let current = arr[i]; // 待插入数据
      let j = i - gap;
      for(; j >= 0 && current < arr[j]; j -= gap) {
        arr[j + gap] = arr[j];
      }
      arr[j + gap] = current;
    }
    /* --- /插入排序 --- */

    gap = Math.floor(gap / 2);
  }
}

算法效率¶

时间复杂度 O(nlogn)，空间复杂度 O(1)，不稳定排序，原地排序

归并排序（Merge Sort）¶

算法思想¶

将已有序的子序列合并，得到一个完全有序的序列。

把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序。
将两个排序好的子序列合并成一个最终的排序序列。

代码¶

function mergeSort(arr) {
  const len = arr.length;
  if (len <= 1) {
    return arr;
  }

  const middle = Math.floor(len / 2);
  const leftArr = arr.slice(0, middle);
  const rightArr = arr.slice(middle);

  return merge(mergeSort(leftArr), mergeSort(rightArr));
}

function merge(leftArr, rightArr) {
  let mergeArr = [];

  let i = 0;
  let j = 0;
  while(i < leftArr.length && j < rightArr.length) {
    if (leftArr[i] <= rightArr[j]) {
      mergeArr.push(leftArr[i]);
      i++;
    } else {
      mergeArr.push(rightArr[j]);
      j++;
    }
  }

  while(i < leftArr.length) {
    mergeArr.push(leftArr[i]);
    i++;
  }

  while(j < rightArr.length) {
    mergeArr.push(rightArr[j]);
    j++;
  }

  return mergeArr;
}

算法效率¶

时间复杂度 O(nlogn)，空间复杂度 O(n)，稳定排序，非原地排序

快速排序¶

算法思想¶

挑出一个元素作为 "基准(pivot)"，一次排序进行分区，所有小于基准的元素居左，所有大于基准的元素居右，对分区进行递归快速排序。

代码¶

function quickSort(arr) {
  // arguments 依次是 [arr, leftIndex, rightIndex]
  let leftIndex = arguments[1] || 0;
  let rightIndex = arguments[2] || arr.length - 1;

  if(leftIndex >= rightIndex){
    return arr;
  }

  let pivot = arr[leftIndex]; // 基准值
  let pivotIndex = leftIndex;
  for(let i = leftIndex + 1; i <= rightIndex; i++) {
    if(arr[i] < pivot) {
      arr[pivotIndex++] = arr[i];
      arr[i] = arr[pivotIndex];
    }
  }
  arr[pivotIndex] = pivot;

  quickSort(arr, leftIndex, pivotIndex - 1);
  quickSort(arr, pivotIndex + 1, rightIndex);

  return arr;
}

算法效率¶

时间复杂度：O(nlogn)，空间复杂度：O(logn)，非稳定排序，原地排序

堆排序¶

利用了堆的概念来排序的选择排序。

大根堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列。
小根堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列。

算法思想¶

创建大根堆，
排序时取出堆顶(最大值)，放在队尾，
剩下的元素调整为大根堆。

代码¶

// 创建大根堆
function heap(arr, i, len) {
  // i 堆顶位置，len 元素个数
  // const len = arr.length;
  const left = 2 * i + 1;
  const right = 2 * i + 2;

  let maxIndex = i;
  if (left < len) {
    heap(arr, left, len);
    if (arr[left] > arr[maxIndex]) {
      maxIndex = left;
    }
  }

  if (right < len) {
    heap(arr, right, len);
    if (arr[right] > arr[maxIndex]) {
      maxIndex = right;
    }
  }

  if (maxIndex !== i) {
    let temp = arr[maxIndex];
    arr[maxIndex] = arr[i];
    arr[i] = temp;

    heap(arr, maxIndex, len);
  }
}

function heapSort(arr) {
  for(let i = arr.length; i > 0; i--) {
    heap(arr, 0, i);
    let temp = arr[0];
    arr[0] = arr[i - 1];
    arr[i - 1] = temp;
  }
}

算法效率¶

1、时间复杂度：O(nlogn) 2、空间复杂度：O(1) 3、非稳定排序 4、原地排序

计数排序¶

算法思想¶

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。
计数排序要求输入的数据必须是有确定范围的整数。

代码¶

function countingSort(arr) {
  const len = arr.length;
  const tempArr = [];
  let max = 0;

  for(let i = 0; i < len; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
    if (!tempArr[arr[i]]) {
      tempArr[arr[i]] = 1;
    } else {
      tempArr[arr[i]]++;
    }
  }

  for(let i = 0, k = 0; i <= max; i++){
    while(tempArr[i] > 0) {
      arr[k++] = i;
      tempArr[i]--;
    }   
  }
}

算法效率¶

时间复杂度：O(n+k)，空间复杂度：O(k)，稳定排序，非原地排序

桶排序¶

算法思想¶

计数排序的升级版。将输入的 n 个数据均匀的分配到 k 个桶，每个桶分别排序。

设置 BucketSize，作为每个桶所能放置多少个不同数值。（如当 BucketSize == 5 时，该桶可放｛1,2,3,4,5｝这几种数字，容量不限。）
遍历输入数据，放入对应的桶中；
每个桶分别排序（可使用其它排序方法，也可递归桶排序）；
把排好序的数据拼接起来。

代码¶

function bucketSort(arr) {
  const len = arr.length;
  const BUCKET_SIZE = 5; // default set to 5

  // 计算桶数量
  let min, max;
  for(let i = 0; i < len; i++) {
    min = arr[i] > min ? min : arr[i];
    max = arr[i] < max ? max : arr[i];
  }
  const bucketCount = Math.floor((max - min) / BUCKET_SIZE) + 1;

  // 二维数组桶初始化
  const buckets = []; 
  for(let i = 0; i < bucketCount; i++) {
    buckets[i] = [];
  }

  // 分配数据，顺便排序
  for(let i = 0; i < len; i++) {
    const bucketIndex = Math.floor((arr[i] - min) / BUCKET_SIZE); // 映射函数
    buckets[bucketIndex].push(arr[i]);

    const bucket = buckets[bucketIndex];
    for(let j = bucket.length - 1; j > 0; j--) {
      if(bucket[j] < bucket[j-1]) {
        let temp = bucket[j];
        bucket[j] = bucket[j-1];
        bucket[j-1] = temp;
      }
    }
  }

  // 分配收集数据
  arr = [];
  for(let i = 0; i < bucketCount; i++) {
    // insertionSort(buckets[i]); // 桶内排序
    arr = arr.concat(buckets[i]);
  }

  return arr;
}

算法效率¶

时间复杂度：O(n+k)，空间复杂度：O(n+k)，稳定排序，原地排序

基数排序¶

利用了桶的概念，根据键值的每位数字来分配桶。
基数排序，低位(LSD, Least Significant Digit)优先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。

算法思想¶

找到数组中的最大数，取得位数；
分配，先从个位开始，根据位值(0-9)分别放到0~9号桶中；
收集，再将放置在0~9号桶中的数据按顺序放到数组中；
重复(2)(3)过程，从个位到最高位，直到排好序为止。

代码¶

function radixSort(arr) {
  const len = arr.length;

  let max;
  for(let i = 0; i < len; i++) {
    max = arr[i] < max ? max : arr[i];
  }

  for(let i = 0, mod = 1; i < max.toString().length; i++, mod *= 10) {
    const buckets = [];

    // 分配
    for(let i = 0; i < len; i++) {
      const bucketIndex = Math.floor(arr[i] / mod) % 10;
      if (!buckets[bucketIndex]) {
        buckets[bucketIndex] = [];
      }
      buckets[bucketIndex].push(arr[i]);
    }

    // 收集
    arr = [];
    for(let i = 0; i < buckets.length; i++) {
      if (Array.isArray(buckets[i])) {
        arr = arr.concat(buckets[i]);
      }
    }
  }

  return arr;
}

算法效率¶

性质：时间复杂度：O(kn), 空间复杂度：O(n+k)，稳定排序，非原地排序

算法总结¶

排序算法	平均时间复杂度	最好情况	最坏情况	空间复杂度	稳定性
冒泡排序	O(n^2)	O(n)	O(n^2)	O(1)	稳定
选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定
插入排序	O(n^2)	O(n)	O(n^2)	O(1)	稳定
希尔排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定
快速排序	O(nlogn)	O(nlogn)	O(n^2)	O(logn)	不稳定
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定
计数排序	O(n + k)	O(n + k)	O(n^2)	O(k)	稳定
桶排序	O(n + k)	O(n + k)	O(n^2)	O(n + k)	稳定
基数排序	O(nk)	O(nk)	O(nk)	O(n + k)	稳定