关于排序算法

川长思鸟来 2022-11-15 03:53 39阅读 0赞

### 关于排序算法 ###

### 文章目录 ###

*   *   *  关于排序算法
         *   *  比较排序算法的时间复杂度、性能
             *  快排原理
             *  很大数组筛选重复数字，并行方式和串行方式。

#### 比较排序算法的时间复杂度、性能 ####

*  常见的排序算法（内排序）：冒泡、直接插入、选择排序、希尔排序、快排、基数排序、堆排序、归并

<table> 
 <thead> 
  <tr> 
   <th align="center">排序算法</th> 
   <th align="center">特征</th> 
   <th align="center">其他</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">冒泡排序</td> 
   <td align="center">n<sup>2</sup></td> 
   <td align="center"></td> 
  </tr> 
  <tr> 
   <td align="center">直接插入</td> 
   <td align="center">n<sup>2</sup>，对于接近有序的情况性能比较高</td> 
   <td align="center"></td> 
  </tr> 
  <tr> 
   <td align="center">希尔排序</td> 
   <td align="center">n<sup>1.4</sup>，同上，复杂度不太好计算，最坏的情况接近n<sup>2</sup></td> 
   <td align="center"></td> 
  </tr> 
  <tr> 
   <td align="center">选择排序</td> 
   <td align="center">n<sup>2</sup></td> 
   <td align="center"></td> 
  </tr> 
  <tr> 
   <td align="center">快排</td> 
   <td align="center">nlogn，不稳定，但是平均最快的算法</td> 
   <td align="center"></td> 
  </tr> 
  <tr> 
   <td align="center">基数排序</td> 
   <td align="center">这个和位数有关，比如：3位,每位的范围为0～k，复杂度为O(3(n+k))</td> 
   <td align="center"></td> 
  </tr> 
  <tr> 
   <td align="center">堆排序</td> 
   <td align="center">nlogn，不稳定</td> 
   <td align="center"></td> 
  </tr> 
  <tr> 
   <td align="center">归并</td> 
   <td align="center">nlogn，稳定</td> 
   <td align="center"></td> 
  </tr> 
 </tbody> 
</table>

#### 快排原理 ####

*  快排通过对比双指针大小+交换，每次将一位放到最终位置，使得左右两侧为比他大（或小）的两个集合，然后将问题分解成左右集合的快排，递归下去直到两个数的快排完成，整个快排就完成了，所有数都找到了最终位置。

#### 很大数组筛选重复数字，并行方式和串行方式。 ####

*  对于筛选数字，一个比较好用的数据结构就是Map，典型的有HashMap；而并行和串行的区别就是，串行不需要考虑线程安全的问题，而并行需要，因此我们只需要采用线程安全的数据结构即可，这种方式兼容串行和并行。
    
     *  在Java中有线程安全版的HashMap，叫ConcurentHashmap，我记得它的实现是在原有的Hashmap（数组+列表（红黑树））的基础上再在数组上加锁，好像叫段锁，这样可以保证一个线程在修改这个key下的值的时候其他线程不会同时修改，从而保证了线程安全。