javascript-排序算法

分手后的思念是犯贱 2021-09-14 01:36 215阅读 0赞

# 插入排序 #

![da44baba996d9c4e8ddeb43a01c2139d][]

算法描述：   
1. 从第一个元素开始，该元素可以认为已经被排序   
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描   
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置   
4. 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置   
5. 将新元素插入到该位置后   
6. 重复步骤 2~5

现有一组数组 arr = \[5, 6, 3, 1, 8, 7, 2, 4\]

[5] 6 3 1 8 7 2 4  //第一个元素被认为已经被排序
    
    [5,6]  3 1 8 7 2 4 //6与5比较，放在5的右边
    
    [3，5，6]  1 8 7 2 4 //3与6和5比较，都小，则放入数组头部
    
    [1,3,5,6]   8 7 2 4 //1与3,5,6比较，则放入头部
    
    [1,3，5，6，8]   7 2 4
    
    [1,3，5，6,7，8]  2 4
    
    [1，2,3，5，6,7，8] 4
    
    [1，2,3，4，5，6,7，8] 
     
      
       1
       2
       3
       4
       5
       6
       7
       8
       9
       10
       11
       12
       13
       14
       15
      
     
      
       1
       2
       3
       4
       5
       6
       7
       8
       9
       10
       11
       12
       13
       14
       15

编程思路：双层循环，外循环控制未排序的元素，内循环控制已排序的元素，将未排序元素设为标杆，与已排序的元素进行比较，小于则交换位置，大于则位置不动

时间复杂度O(n^2)

# 选择排序 #

![e0824efdb79268d4de42991274dcc9eb][]

算法描述：直接从待排序数组中选择一个最小（或最大）数字，放入新数组中。

[1] 5 6 3  8 7 2 4 
    [1,2] 5 6 3  8 7  4 
    [1,2,3] 5 6  8 7 2 4 
    [1,2,3,4] 5 6 8 7
    [1,2,3,4,5] 6  8 7 
    [1,2,3,4,5,6] 8 7  
    [1,2,3,4,5,6,7] 8  
    [1,2,3,4,5,6,7,8] 
     
      
       1
       2
       3
       4
       5
       6
       7
       8
      
     
      
       1
       2
       3
       4
       5
       6
       7
       8

编程思路：先假设第一个元素为最小的，然后通过循环找出最小元素，然后同第一个元素交换，接着假设第二个元素，重复上述操作即可

时间复杂度O(n^2)

# 归并排序 #

![f9fcaf0d64dcd11b9309f09062863b29][]

算法描述：   
1. 把 n 个记录看成 n 个长度为 l 的有序子表   
2. 进行两两归并使记录关键字有序，得到 n/2 个长度为 2 的有序子表   
3. 重复第 2 步直到所有记录归并成一个长度为 n 的有序表为止。

5 6 3 1 8 7 2 4
    
    [5,6] [3,1] [8,7] [2,4]
    
    [5,6] [1,3] [7,8] [2,4]
    
    [5,6,1,3] [7,8,2,4]
    
    [1,3,5,6] [2,4,7,8]
    
    [1,2,3,4,5,6,7,8]
     
      
       1
       2
       3
       4
       5
       6
       7
       8
       9
       10
       11
      
     
      
       1
       2
       3
       4
       5
       6
       7
       8
       9
       10
       11

编程思路：将数组一直等分，然后合并

时间复杂度O(nlogn)

# 快速排序 #

![ad4d6e25b6e0e91c743ae220e3d52d1e][]

算法描述：

1.  在数据集之中，选择一个元素作为”基准”（pivot）。
2.  所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。这个操作称为分区 (partition)操作，分区操作结束后，基准元素所处的位置就是最终排序后它的位置。
3.  对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

5 6 3 1 8 7 2 4
    
    pivot
    |
    5 6 3 1 9 7 2 4
    |
    storeIndex
    
    5 6 3 1 9 7 2 4//将5同6比较，大于则不更换
    |
    storeIndex
    
    3 6 5 1 9 7 2 4//将5同3比较，小于则更换
      |
      storeIndex
    
    3 6 1 5 9 7 2 4//将5同1比较，小于则不更换
        |
       storeIndex
    ...
    
    3 6 1 4 9 7 2 5//将5同4比较，小于则更换
          |
          storeIndex
    
    3 6 1 4 5 7 2 9//将标准元素放到正确位置
          |
    storeIndex pivot
     
      
       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
      
     
      
       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

上述讲解了分区的过程，然后就是对每个子区进行同样做法

上述版本会造成堆栈溢出，所以建议使用下面版本

原地分区版：主要区别在于先进行分区处理，将数组分为左小右大

时间复杂度O(nlogn)

# 冒泡排序 #

![3bcdc49661b5c8a3500463095ecc09df][]

算法描述：   
1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。   
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。   
3. 针对所有的元素重复以上的步骤，除了最后一个。   
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。5.

5 6 3 1 8 7 2 4
    
    [5 6] 3 1 8 7 2 4 //比较5和6
    
    5 [6 3] 1 8 7 2 4
    
    5 3 [6 1] 8 7 2 4
    
    5 3 1 [6 8] 7 2 4
    
    5 3 1 6 [8 7] 2 4
    
    5 3 1 6 7 [8 2] 4
    
    5 3 1 6 7 2 [8 4]
    
    5 3 1 6 7 2 4 8  // 这样最后一个元素已经在正确位置，所以下一次开始时候就不需要再比较最后一个
    
     
      
       1
       2
       3
       4
       5
       6
       7
       8
       9
       10
       11
       12
       13
       14
       15
       16
       17
       18
      
     
      
       1
       2
       3
       4
       5
       6
       7
       8
       9
       10
       11
       12
       13
       14
       15
       16
       17
       18

编程思路：外循环控制需要比较的元素，比如第一次排序后，最后一个元素就不需要比较了，内循环则负责两两元素比较，将元素放到正确位置上

时间复杂度O(n^2)

# 参考资料 #

[排序效果][Link 1]   
[常见排序算法][Link 2]   
[排序算法 维基百科][Link 3]

[da44baba996d9c4e8ddeb43a01c2139d]: /images/20210813/c05fc527e5aa4f6daf2e9ed9e91c109d.png
[e0824efdb79268d4de42991274dcc9eb]: /images/20210813/644adcb3307f43f780e20b6d05ff50ac.png
[f9fcaf0d64dcd11b9309f09062863b29]: /images/20210813/d6299a0582904df7a322d3806bb2ccf7.png
[ad4d6e25b6e0e91c743ae220e3d52d1e]: /images/20210813/3a505d14bee3465ba629df6e54689c68.png
[3bcdc49661b5c8a3500463095ecc09df]: /images/20210813/40de7276277e44bea9709541c9946197.png
[Link 1]: https://visualgo.net/zh/sorting
[Link 2]: http://bubkoo.com/tags/algorithm/
[Link 3]: https://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95