（未完待续）
这篇文章总结了排序的多种常见的方法，每种方法都给了一个动图方便理解（计划中，未完成），并且会在Leetcode上找到使用该方法或近似方法的例题帮助理解（计划中，未完成）。
完成这篇文章借鉴了很多前辈们的Blogs，我会在本文末尾向他们致谢。
排序算法分类
一些术语
-
稳定排序和不稳定排序
稳定排序：对于值相同的a和b两个数，如果排序前后他们的相对位置没变，则称排序算法是稳定的。通俗一点，也就是说，假如排序前a在b前面，排序后a仍然在b前面，那么这种排序算法就是稳定的。
- 不稳定排序：反之，如果排序前后，值相同的a和b的相对位置可能发生了变化，那么这种排序算法就是不稳定的。
原地排序和非原地排序
- 原地排序：排序过程中不需要申请额外的存储空间，也叫就地排序。
- 非原地排序：排序过程需要申请额外的存储空间来辅助完成排序。
时间复杂度和空间复杂度
- 时间复杂度：算法运行消耗的时间（数量级），一般可以用O(n)来描述（n代表输入数据量）。
- 空间复杂度：算法执行需要的内存空间的大小。
关于swap()函数
- 由于下面排序算法中可能经常需要交换两个变量的值，因此首先在这里抽象出一个
swap()函数；// 交换数组array中下标为a, b位置的值function swap(array, a, b) {let temp = array[a];array[a] = array[b];array[b] = temp;}
交换排序
冒泡排序
核心思想
- 不断比较相邻的两个元素，查看他们的大小顺序是否符合结果；
- 若符合，再比较下一对；若不符合，则交换他们的位置；
遍历数组，每次遍历可以将最小（大）值找出并移动到末尾的位置。
动图演示
JavaScript代码
function bubbleSort(array) {// 不断比较相邻两者，从而找出一次遍历中的最小值for (let i = 0; i < array.length - 1; i++) {for (let j = 0; j < array.length - 1 - i; j++) {// 如果两者大小顺序有误if (array[j] > array[j + 1]) {// 就交换他们俩swap(array, j, j + 1);}}}return array;}
分析
关于冒泡排序没啥好分析的，应该是大部分人所接触的第一个排序算法吧，思路挺清晰但是效率相对较低。
快速排序
快速排序需要考虑的东西相对较多，主要涉及优化的问题，优化中最关键的就是提高最坏时间复杂度。 快速排序水很深，限于水平有限，更多地还是一个总结性的东西，代码部分难免有疏漏。
快速排序初探
核心思想
- 取中间值（pivot）：先在所有需要排序的元素中选择一个基准元素；
- 分区（Partition）：所有比基准元素小的元素都放在它的左边，所有比基准元素大的元素都放在它的右边；
- 递归：对中间值左右两边的数据分别重复1、2两个步骤；
JavaScript代码
```javascript function quickSort(array, startIndex = 0, endIndex = array.length - 1) { // 排序已经完成 if (startIndex >= endIndex) {
} // 获得基准元素 let pivotIndex = partition(array, startIndex, endIndex); // 对基准元素两侧进行快速排序，分而治之 // 左侧（小于当前pivot的所有元素） quickSort(array, startIndex, pivotIndex - 1); // 右侧（大于当前pivot的所有元素） quickSort(array, pivotIndex + 1, endIndex); return array; }return array;
function partition(array, startIndex, endIndex) { // 取第一个位置元素为基准元素pivot let pivot = array[startIndex]; // mark用于记录分区时分割的位置 let mark = startIndex; for (let i = startIndex + 1; i <= endIndex; i++) { if (array[i] < pivot) { mark++; swap(array, mark, i); } } swap(array, startIndex, mark); // 此时数组mark位置左侧的值都小于pivot，mark右侧的值都大于pivot // mark作为下一次递归时左侧区域的末尾/右侧区域的开始 return mark; }
<a name="QPM3A"></a>#### 快速排序的优化> 这一节主要观点来自：[快速排序算法的优化思路总结 - 周骅](https://juejin.im/post/5aa94ca6518825558252120c)- 在上一个小节中我们完成了快速排序的JavaScript实现，不过上述一段代码仍然存在一些问题。- 例如我们之前是选择第一个元素作为pivot，这在数组已经或接近排好序的情况下会大大降低算法的执行效率，**最坏时间复杂度甚至会降到O(n2)**，这显然是我们不想看到的。- 所以下面我们看看究竟有哪些地方可以继续优化，这里只阐述观点，不给出实际代码。<a name="H1y0A"></a>##### pivot的选择- 如果只是简单地选择第一个或者最后一个元素作为pivot的话，对于已经有序或者非常接近有序的数组来说，快速排序的效率会很大程度地降低，甚至接近O(n2)。- 比较理想的情况是**对于我们每次所选择的元素，比它小的元素和比它大的元素的数量差不多，即达到平衡**。- 上述这种理想的情况其实很难达到，不过我们还是可以通过一些方式来避免过于不平衡的情况的发生。- 例如我们可以每次**随机选择**一个元素作为pivot。- 也可以在首尾两个元素以及中间的某个元素**三者之间对比选择**中位数作为pivot。- 而V8引擎选择pivot的方式也值得借鉴：V8引擎认为超过1000项的数组是大数组，每隔200左右（不固定）选出一个元素，从这些元素中找出中位数，再加入首尾两个元素，从这些元素中找出中位数作为pivot。<a name="fZXC4"></a>##### 更快速地分区- 在刚刚的JS实现中，对于数组 `[2, 1, 3, 1, 3, 1, 3]` ，选择2作为pivot，那么如果从左到右每次发现比2小的值都交换一次的话，需要交换三次。而事实上，只要第一个3和最后一个1交换就可以达到同样的效果。- 下面要提到的[二路快排👇](#i0pOJ)很好地解决了这个问题。<a name="51ZUs"></a>##### 处理重复元素- 我们来考虑一种特殊情况，如果数组中所有值都相等，那么使用快速排序会发生什么？- 这样的话，不管我们怎么选择pivot，都会使得分区时一边极大而另一边极小。- 下面要提到的[三路快排👇](#oQrql)较好地解决了这个问题。<a name="fT6jD"></a>##### 针对小数组- 对于规模很小的数组，其实快速排序的又是并不明显，甚至还会有额外开销；- 所以可以设置一个阈值，当快速排序分区的**规模达到阈值以下**时，可以用一些类似插入排序等的排序算法来替代快速排序；<a name="i0pOJ"></a>#### 双路快排- 双路快排通过减少交换的次数从而加快了分区操作。- 将小于pivot的元素和大于pivot的元素分别放在数组两端，并使用两个索引来记录他们的边界。- 左右两个索引同时向中间靠拢，，任意一侧指针找到需要交换的值先停下等待另一侧，如果另一侧也有需要交换的值，就可以进行一次交换了，这样可以很大程度地减少交换的次数。- 下面给出代码：<a name="CiBs9"></a>#### 三路快排- 三路快排将重复元素单独分出来，在处理重复元素比较多的数组时比较有效。<a name="O1lpw"></a>## 选择排序<a name="FirXZ"></a>### 简单选择排序<a name="piFkN"></a>##### 核心思想- 找到数组中最小的值并放在第一位，找到第二小的值并放在第二位，以此类推。<a name="f0J7r"></a>##### 具体步骤- 将数组分成两部分，即**已排序部分**（最初长度为0）和**未排序部分**（最初长度为原数组长度）；- **循环遍历未排序部分**，每次从中找出**最小值**，并**插入到已排序部分的末尾**；- 当遍历结束时，已排序部分数组长度变为原数组长度，未排序部分长度变为0；- 最后得到的已排序部分数组就是原数组有小到大排序后的结果。<a name="FpT2t"></a>##### 动图演示<a name="U2tRV"></a>##### JavaScript代码```javascriptfunction selectionSort(array) {// 存放每一次遍历时最小值在未排序部分数组中的位置(下标)let minIndex = 0;// 循环遍历未排序数组中每一个值for (let i = 0; i < array.length; i++) {// 找到未排序数组中最小值的下标for (j = i; j < array.length; j++){// 如果当前值小于之前的最小值if (array[j] < array[minIndex]) {// 就将minIndex的值更换为当前值的下标minIndex = j;}}// 如果本次遍历中最小值不在已排序数组的末尾if (minIndex !== i) {// 就将它放到已排序数组的末尾swap(array, i, minIndex);}}return array;}
堆排序
插入排序
简单插入排序
希尔排序
归并排序
计数排序
桶排序
基数排序
若有收获，就点个赞吧
0 人点赞
