前言

  再不趁热，我就又要忘记了。
  十大排序算法，属于算法里基础的东西，学习难度自然不能说大，但是，相当容易忘，究其原因不外乎就是平时用不到，就是要用，也有现成的接口可以调。
  当然，我们不能因为平时用不到就不去巩固他，这玩意，只要学了，练了，复习了就有好处，不谈工作上用不用的到，面试上差不多会问。
  巩固学习，重点是什么呢？是理解并记住其思想。假如面试让我实现快排，那我遇到的第一个问题会是什么呢？那就是快排是什么，以什么思想实现的排序方法叫做快排。是的，假如不事前温习一下，回答快排的概念都费劲。所以，总结再画图加深理解记忆，不得不这么做。
  以前读书时，我老是不理解为什么学如逆水行舟不进则退，只要学了，不就是有进步。随之离开了学校，离开了那个充满了知识的地方。我真真发现，知识离开了他的沃土就会枯萎。前些天，刷抖音，刷到一个题，让我们判断三盏灯是并连还是串连。我发现，我已经不记得电源符号哪边是表示正极了。
  吓得我，马上提起了键盘，吃饭的家伙，不能也这样忘了啊。

菜鸟学院：十大经典排序算法
动图演示网站

零、十大排序

名词解释：

• n：数据规模 k："桶"的个数
• In-place：占用常数内存，不占用额外内存
• Out-place：占用额外内存
• 稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同

一、冒泡排序（bubbleSort）

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

冒泡排序核心思想 ↓

重复上述操作，逐渐缩小对比区域，直到数据排列完毕。

/*** 冒泡排序*/
function bubbleSort() {let arr = deepClone(array)console.log('--------------------')console.log('冒泡排序:开始：' + arr)for (var i = 0; i < arr.length - 1; i++) {for (var j = 0; j < arr.length - 1 - i; j++) {if (arr[j] > arr[j + 1]) {arr[j] += arr[j + 1]arr[j + 1] = arr[j] - arr[j + 1]arr[j] -= arr[j + 1]}}console.log('冒泡排序：第' + (i + 1) + '趟---' + arr)}
}

二、选择排序（selectionSort）

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

/*** 选择排序*/
function selectionSort() {let arr = deepClone(array)console.log('--------------------')console.log('选择排序:开始：' + arr)let minIndex, tempfor (var i = 0; i < arr.length - 1; i++) {minIndex = ifor (var j = i + 1; j < arr.length; j++) {if (arr[j] < arr[minIndex]) {minIndex = j}}temp = arr[minIndex]arr[minIndex] = arr[i]arr[i] = tempconsole.log('选择排序' + (i + 1) + '趟---' + arr)}
}

三、插入排序（insertSort）

插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 [1] 。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动 [2] 。

核心记忆点—插入，类似于插牌的过程。

/*** 插入排序*/
function insertSort() {let arr = deepClone(array)console.log('--------------------')console.log('插入排序:开始：' + arr)let cur, tempfor (var i = 1; i < arr.length; i++) {cur = ifor (var j = i - 1; j >= 0; j--) {if (arr[j] > arr[cur]) {temp = arr[cur]arr[cur] = arr[j]arr[j] = tempcur = j} else {break}}console.log('插入排序' + (i) + '趟---' + arr)}
}

四、希尔排序（shellSort）

希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止

  希尔排序是直接插入排序算法的一种更高效的改进版本，形象点打比方的话就是，插入排序是一个人抓一堆牌，希尔排序是几个人一起抓牌排序，抓完后，按顺序，把牌堆好，按设定减人继续抓，直到最后剩一个，也就变成了插入排序（如下图 gap：1，排序过程与插入排序完全一致）。
  形象点记忆的话，就是四个人轮流抓牌，，总比一个人抓牌好吧。实际设计，就是插入排序外层加套了一个间隔（gap）变动的 for 循环。

/*** 希尔排序*/
function shellSort() {let arr = deepClone(array)console.log('--------------------')console.log('希尔排序:开始：' + arr)let cur, temp, gap = 1while (gap < array.length / 3) {gap = gap * 3 + 1}for (gap; gap > 0; gap = Math.floor(gap / 3)) {console.log('希尔排序：------gap：' + gap + '-----')for (var i = gap; i < arr.length; i++) {cur = ifor (var j = i - gap; j >= 0 && arr[j] > arr[cur]; j -= gap) {temp = arr[cur]arr[cur] = arr[j]arr[j] = tempcur = jconsole.log('希尔排序' + (i) + '趟---' + arr)}}}
}

五、归并排序（mergeSort）

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

  归并排序的图我就偷个懒了，因为《图解排序算法(四)之归并排序》的作者，你们瞅瞅，这图画得确实又好又细。一篇文章的阅读量打我全部。
  我呢，随便画点要加强记忆的地方就行了。

  归并排序有二路归并排序和多路归并排序，我们这里每次一分为二，显然是二路归并。

/*** 归并排序，核心思想：分治*/
function mergeSort() {let arr = deepClone(array)console.log('--------------------')console.log('归并排序:开始：' + arr)function merge(left, mid, right) {let lStart = leftlet rStart = mid + 1let cur = leftwhile (lStart < mid + 1) {if (rStart > right) {while (lStart < mid + 1) {temp[cur++] = arr[lStart++]}break}if (arr[lStart] > arr[rStart]) {temp[cur] = arr[rStart]rStart++} else {temp[cur] = arr[lStart]lStart++}cur++}console.log('----归并排序 merge(' + left + '-' + right + ')----')console.log('temp:' + temp)while (left < cur) {arr[left] = temp[left]left++}console.log('arr :' + arr)}function sort(left, right) {console.log('----归并排序 sort(' + left + '-' + right + ')----')let mid = Math.floor((left + right) / 2)if (left !== mid) {sort(left, mid)sort(mid + 1, right)}merge(left, mid, right)return}let len = array.lengthlet temp = new Array(len)sort(0, len - 1)
}

六、快速排序（quickSort）

快速排序（Quicksort）是对冒泡排序算法的一种改进。

  快排的定义，百度百科写得及其敷衍，我也没找到其他好的描述，基本是以算法步骤来形容的，如下。所以，画图吧，比文字香。

算法步骤：
1.从数列中挑出一个元素，称为 “基准”（pivot）;
2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

快速排序用到了分治思想，是在冒泡基础上加入基准值概念以及递归的产物。

一次循环中，数据操作过程如下，将基准值单独拉出来后，便多了一个空位供数据插入，在遍历完毕后，再将基准值插入回去即可（及指针1位置）

/*** 快速排序*/
function quickSort() {let arr = deepClone(array)console.log('--------------------')console.log('快速排序:开始：' + arr)function partition(left, right) {if (left >= right) {return}console.log('---- partition(' + left + '-' + right + ')----')let mid = sort(left, right)console.log('return mid:' + mid)console.log('arr :' + arr)partition(left, mid - 1)partition(mid + 1, right)}function sort(left, right) {let base = arr[left]let lP = leftfor (let i = left + 1; i <= right; i++) {console.log(i + 'sort 判断 基准值：' + base + ' > ' + arr[i] + ':' + (base > arr[i]))if (base > arr[i]) {arr[lP] = arr[i]lP++arr[i] = arr[lP]}}arr[lP] = basereturn lP}partition(0, array.length - 1)console.log('快速排序:结束：' + arr)
}

七、堆排序（heapSort）

堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

  堆排序的重点在于堆化（heapify），在掌握了堆化的情况下，该排序不过就是一个简单的循环。

堆的概念：
堆是一种特殊的树形数据结构，一般讨论的堆都是二叉堆。堆的特点是根结点的值是所有结点中最小的或者最大的，并且根结点的两个子树也是一个堆结构。

如上图所示，整体过程就是通过堆化构建最大堆（最小堆）来寻找最大值（最小值）进行排序。（ps：堆排序构建的是二叉堆）

/*** 堆排序*/
function heapSort() {let arr = deepClone(array)console.log('--------------------')console.log('堆排序:开始：' + arr)/*** 堆化*/function heapify(len) {for (let i = Math.floor(len / 2); i >= 1; i--) {let parent = ilet lagerChild = 2 * parentwhile (lagerChild <= len) {if (lagerChild < len && arr[lagerChild - 1] < arr[lagerChild]) {lagerChild++}if (arr[lagerChild - 1] > arr[parent - 1]) {swap(lagerChild - 1, parent - 1)parent = lagerChildlagerChild = 2 * parent} else {break}}}console.log('长度为：' + len + ',数组堆化')console.log('arr：' + arr)}/*** 交换节点值*/function swap(i1, i2) {let temp = arr[i1]arr[i1] = arr[i2]arr[i2] = temp}function heapSort() {while (len > 1) {heapify(len)swap(0, --len)console.log('调整:' + arr)}}let len = arr.lengthheapSort()console.log('堆排序:结束：' + arr)
}

八、计数排序（countingSort）

计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。 [1] 当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(nlog(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(nlog(n)), 如归并排序，堆排序）

/*** 计数排序*/
function countingSort() {let arr = deepClone(array)console.log('--------------------')console.log('计数排序:开始：' + arr)let MAX = 0for (let i in arr) {MAX = Math.max(arr[i], MAX)}console.log('MAX：' + MAX)let countArr = new Array(MAX + 1).fill(0)for (let i in arr) {countArr[arr[i]]++}let index = 0for (let i in countArr) {while (countArr[i] > 0) {arr[index++] = icountArr[i]--}}console.log('计数排序:结束：' + arr)
}

九、桶排序（bucketSort）

桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。

  桶排序的设计思想简单明了-分治思想。如何建桶，是其关键点。

建桶：
  首先确定数据的范围，即 MAX ,MIN
  然后，确定桶的大小，通常的，桶排序内部会定义一个默认大小DEF_SIZE，再定义一个形参，用来给调用者修改这个值。当然，这一步，我这里省略了。桶的大小是很关键的，调用者需要根据实际情况决定，假如桶的大小太大了，对内存是极其浪费的。
  再然后，计算桶的数量 ，通常，公式如下：bucketCunt = (MAX - MIN) / DEF_SIZE + 1。
  最后，建立映射，将数据均匀的分入桶中，示例中映射公式如下：桶索引 = (元素值 - MIN) / DEF_SIZE。在示例中，因为元素值分布是均匀的，该公式可以保证将数据均匀的分入桶中。

/*** 桶排序*/
function bucketSort() {let arr = deepClone(array)console.log('--------------------')console.log('桶排序:开始：' + arr)/*** 插入排序*/function insertSort(arr) {let cur, tempfor (var i = 1; i < arr.length; i++) {cur = ifor (var j = i - 1; j >= 0; j--) {if (arr[j] > arr[cur]) {temp = arr[cur]arr[cur] = arr[j]arr[j] = tempcur = j} else {break}}}}let MAX = 0let MIN = 0for (let i in arr) {MAX = Math.max(arr[i], MAX)MIN = Math.min(arr[i], MAX)}console.log('(MAX,MIN)' + MAX + ',' + MIN)const DEF_SIZE = 4let bucketCunt = Math.floor((MAX - MIN) / DEF_SIZE) + 1console.log('bucketCunt:' + bucketCunt)let bucket = new Array(bucketCunt)for (let i = 0; i < bucket.length; i++) {bucket[i] = []}for (let i in arr) {let index = Math.floor((arr[i] - MIN) / DEF_SIZE)console.log('映射：' + arr[i] + '->' + index)bucket[index].push(arr[i]);}let result = []for (let i in bucket) {insertSort(bucket[i])for (let j in bucket[i]) {result.push(bucket[i][j])}}console.log('桶排序:结束：' + result)
}

十、基数排序（radixSort）

基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog®m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

  基数排序，就是每一次对针对一个数位（如个位）排序，当遍历完所有数位后，顺序也就确定了。

基数排序记忆点：
  首先寻找最大值 MAX，然后根据 MAX 计算最大位数maxDigit ，最后根据 maxDigit 构建循环，从个位其，每次循环开始，对其排序，每次循环结束，将结果写入原数组，直至排序到最大位数。

/*** 基数排序*/
function radixSort() {let arr = deepClone(array)// let arr = [8, 3, 5, 7, 2, 4, 6, 1]console.log('--------------------')console.log('基数排序:开始：' + arr)let bucket = new Array(10)for (let i = 0; i < bucket.length; i++) {bucket[i] = []}let MAX = 0for (let i in arr) {MAX = Math.max(arr[i], MAX)}// 最大位数let maxDigit = 0while (MAX > 0) {MAX = Math.floor(MAX / 10)maxDigit++}console.log('maxDigit：' + maxDigit)let mod = 10let dev = 1for (let i = 0; i < maxDigit; i++, mod *= 10, dev *= 10) {for (let a in arr) {let bucketIndex = Math.floor((arr[a] % mod) / dev)console.log('bucketIndex:' + maxDigit)bucket[bucketIndex].push(arr[a])}let arrIndex = 0for (let x in bucket) {for (let y in bucket[x]) {arr[arrIndex++] = bucket[x][y]}}}console.log('基数排序:结束：' + arr)
}

结语

  终于记录完毕了，虽然主要的工作量，不过是画了一点点图。但不得不说，这一波回手掏，还是挺有效果的，短期记忆提升成了长期记忆。理解+1。
  时间方面，从码云上传第一行代码，到现在总结记录完毕，过了20天。这让我不由得想到效率问题，值么？大学教的基础的东西。
  我想，只要以后不用再花时间热这些冷菜，便是值的。可以提升我解决问题的能力，便是值的。
  哈哈，完犊子了，刚准备到力扣检验一下成果，碰到一道题，要用到插入排序，不得不偷偷回来瞄了一眼插入排序的概念图。阿这，这不是一点效果都没有么。握草。

代码仓

码云代码仓