排序是开发中十分常见且核心的操作，虽说实际项目中很小几率会需要我们手动实现，但是了解这些精妙的思想对我们还是大有裨益的。本文简单总结下最基础的几类算法。
这里首先推荐一个数据结构和算法动态可视化网站：https://visualgo.net/zh

0. 概述

• 十种常见排序算法可以分为两大类：

  • 非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。
  • 线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。
    

• 算法复杂度
  

• 相关概念

  • 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
  • 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
  • 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
  • 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。

1. 冒泡排序（Bubble Sort）

• 思想
  对相邻的元素进行两两比较，顺序相反则进行交换，这样，每一趟会将最小或最大的元素“浮”到顶端，最终达到完全有序。
  在冒泡排序的过程中，如果某一趟执行完毕，没有做任何一次交换操作，比如数组[5,4,1,2,3]，执行了两次冒泡之后变为[1,2,3,4,5]。此时，再执行第三次循环后，一次交换都没有做，这就说明剩下的序列已经是有序的，排序提前完成。
  
  
• 算法分析
  • 时间复杂度：Ο(n^2)
  • 空间复杂度：Ο(1)
• JS实现

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

  function bubbleSort(arr) { var len = arr.length; var i, j, temp, bSwap; for(i=0; i<len-1; i++){ bSwap = false; for(j=0; j<len-i-1; j++){ if(arr[j]>arr[j+1]){ temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; bSwap = true; } }    // 用于判断此轮循环有没有做交换，如果没有交换，说明数组已经是有序的了，排序完成    if (!bSwap){ break; } } return arr; } /* 交换两个数值的简便方式，接下来的代码就采用此方式： [a,b] = [b,a]; */

2. 快速排序（Quick Sort）

• 思想
  通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
  快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
  • 1、从数列中挑出一个元素，称为 “基准”；
  • 2、重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置，这个称为分区操作；
  • 3、对每个分区不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
    

3. 插入排序

4. 希尔排序

5. 选择排序

6. 归并排序

7. 堆排序

8. 计数排序（Count Sort）

• 简介
  计数排序不是基于比较的排序算法。它的优势在于在对一定范围内的整数排序时，快于任何比较排序算法。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
• 思想
  • 1、找出待排序的数组中最大和最小的元素；
  • 2、统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
  • 3、对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
  • 4、反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
    
    

• 算法分析

  • 时间复杂度：Ο(n+k)，k为待排序数的范围，n为数组长度
  • 空间复杂度：Ο(k)
  • 稳定性：稳定
  • 要求：数值较小的整数数组。计数排序是一种以空间换时间的排序算法，并且只适用于待排序列中所有的数较为集中时。当数组较为分散时，比如一组序列中的数据为0 1 2 3 4 999就得开辟1000个辅助空间，就很不划算。

• JS实现

  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

  function countingSort(arr){ var len = arr.length, Result = [], Count = [], min = max = arr[0]; console.time('countingSort waste time:'); /*查找最大最小值,并将arr数置入Count数组中,统计出现次数*/ for(var i = 0;i<len;i++){ Count[arr[i]] = Count[arr[i]] ? Count[arr[i]] + 1 : 1; min = min <= arr[i] ? min : arr[i]; max = max >= arr[i] ? max : arr[i]; } console.log(Count) /*从最小值->最大值,将计数逐项相加*/ for(var j = min;j<max;j++){ Count[j+1] = (Count[j+1]||0)+(Count[j]||0); } /*Count中,下标为arr数值,数据为arr数值出现次数;反向填充数据进入Result数据*/ for(var k = len - 1;k>=0;k--){ /*Result[位置] = arr数据*/ Result[Count[arr[k]] - 1] = arr[k]; /*减少Count数组中保存的计数*/ Count[arr[k]]--; /*显示Result数组每一步详情*/ console.log(Result); } console.timeEnd("countingSort waste time:"); return Result; }