js排序的时间复杂度_一文搞懂常见排序

女爷i 2023-01-05 03:57 96阅读 0赞

![034a5cbe70b36e3bed6996031e0ca088.png][]

## 排序分类 ##

排序算法主要分两大类：

*  比较类排序

通过比较来决定元素之间的相对次序，由于其时间复杂度无法突破O(nlogn),因此也叫做 非线性时间比较类排序。比如js的sort(comparator)

*  非比较类排序

不通过比较来决定元素之间的相对次序，可突破基于比较排序的时间下界，以线性时间运行，线性时间非比较类排序。

![d9dea3ac438ea1099c5a88f1bbf90911.png][]

### 特性 ###

<table> 
 <tbody> 
  <tr> 
   <td>排序方法</td> 
   <td>平均时间复杂度</td> 
   <td>最坏时间复杂度</td> 
   <td>最好时间复杂度</td> 
   <td>空间复杂度</td> 
   <td>稳定性</td> 
  </tr> 
  <tr> 
   <td>插入排序</td> 
   <td>O(n^2)</td> 
   <td>O(n^2)</td> 
   <td>O(n)</td> 
   <td>O(1)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>希尔排序</td> 
   <td>O(n^1.3)</td> 
   <td>O(n^2)</td> 
   <td>O(n)</td> 
   <td>O(1)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>选择排序</td> 
   <td>O(n^2)</td> 
   <td>O(n^2)</td> 
   <td>O(n^2)</td> 
   <td>O(1)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>堆排序</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>O(1)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>冒泡排序</td> 
   <td>O(n^2)</td> 
   <td>O(n^2)</td> 
   <td>O(n)</td> 
   <td>O(1)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>快速排序</td> 
   <td>O(nlogn)</td> 
   <td>O(n^2)</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>归并排序</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>O(nlogn)</td> 
   <td>O(n)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>记数排序</td> 
   <td>O(n+k)</td> 
   <td>O(n+k)</td> 
   <td>O(n+k)</td> 
   <td>O(n+k)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>桶排序</td> 
   <td>O(n+k)</td> 
   <td>O(n^2)</td> 
   <td>O(n)</td> 
   <td>O(n+k)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>基数排序</td> 
   <td>O(n*k)</td> 
   <td>O(n*k)</td> 
   <td>O(n*k)</td> 
   <td>O(n+k)</td> 
   <td>稳定</td> 
  </tr> 
 </tbody> 
</table>

### 初级排序 ###

平均时间复杂度 O(n^2)。

*  选择排序 Selection Sort

每次选择最小值，然后放到待排序数组的起始位置。

![fd2122cedcdd3c4a5d2627393938d454.png][]

![f9852111aeb0ff91b6ab536999d526af.gif][]

*  插入排序 Insertion Sort

从前往后逐渐构建有序序列，对于未排序数据，在已排序数据中从后往前扫描，找到合适位置进行插入。即保证前半部分是有序的。

![4bd82121dc3cc2f8660d4f37f51e7b05.png][]

![fc82c623a6404fb39d13a0d1f0e96c12.gif][]

*  冒泡排序 Bubble Sort

嵌套循环，每次查看相邻元素，如果逆序，那么则交换。

![d9408ef8664570c8c69ecccf6a9b865a.png][]

![ce9822e97b2e9324a32a2592a19eb9ef.gif][]

### 高级排序 ###

### 快速排序 ###

数组取标杆pivot，将小元素放在pivot左边，大元素放在pivot右边，然后依次对左右子数组进行快排，最后达到整个数组有序。

*  快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）
 *  从数列中挑出一个元素，称为 “基准”（pivot）
 *  重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作
 *  递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序

![aeeabebb95e28ae98e5d1032f2fe134e.gif][]

[034a5cbe70b36e3bed6996031e0ca088.png]: /images/20221119/5977e4de54a2481888eba7bdf1a46650.png
[d9dea3ac438ea1099c5a88f1bbf90911.png]: https://img-blog.csdnimg.cn/img_convert/d9dea3ac438ea1099c5a88f1bbf90911.png
[fd2122cedcdd3c4a5d2627393938d454.png]: https://img-blog.csdnimg.cn/img_convert/fd2122cedcdd3c4a5d2627393938d454.png
[f9852111aeb0ff91b6ab536999d526af.gif]: https://img-blog.csdnimg.cn/img_convert/f9852111aeb0ff91b6ab536999d526af.gif
[4bd82121dc3cc2f8660d4f37f51e7b05.png]: https://img-blog.csdnimg.cn/img_convert/4bd82121dc3cc2f8660d4f37f51e7b05.png
[fc82c623a6404fb39d13a0d1f0e96c12.gif]: https://img-blog.csdnimg.cn/img_convert/fc82c623a6404fb39d13a0d1f0e96c12.gif
[d9408ef8664570c8c69ecccf6a9b865a.png]: https://img-blog.csdnimg.cn/img_convert/d9408ef8664570c8c69ecccf6a9b865a.png
[ce9822e97b2e9324a32a2592a19eb9ef.gif]: https://img-blog.csdnimg.cn/img_convert/ce9822e97b2e9324a32a2592a19eb9ef.gif
[aeeabebb95e28ae98e5d1032f2fe134e.gif]: https://img-blog.csdnimg.cn/img_convert/aeeabebb95e28ae98e5d1032f2fe134e.gif