排序算法性能分析和海量数据排序问题

╰半夏微凉° 2022-11-17 05:29 176阅读 0赞

### 排序算法性能分析 ###

*  时间和空间复杂度
 *  快速排序的优化
 *  海量数据排序问题：

# 时间和空间复杂度 #

整理：

<table> 
 <thead> 
  <tr> 
   <th>排序</th> 
   <th></th> 
   <th></th> 
   <th>稳定性</th> 
   <th>时间复杂度</th> 
   <th>空间度复杂度</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td></td> 
   <td>最好</td> 
   <td>最坏</td> 
   <td></td> 
   <td>最好/平均/最坏</td> 
   <td>最好/平均/最坏</td> 
  </tr> 
  <tr> 
   <td>冒泡排序</td> 
   <td>有序</td> 
   <td>逆序</td> 
   <td>稳定</td> 
   <td>O(n) / O(n<sup>2</sup>) / O(n<sup>2</sup>)</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>插入排序</td> 
   <td>有序</td> 
   <td>逆序</td> 
   <td>稳定</td> 
   <td>O(n) / O(n<sup>2</sup>) / O(n<sup>2</sup>)</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>选择排序</td> 
   <td></td> 
   <td></td> 
   <td>不稳定</td> 
   <td>O(n<sup>2</sup>) / O(n<sup>2</sup>) / O(n<sup>2</sup>)</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>希尔排序</td> 
   <td></td> 
   <td></td> 
   <td>不稳定</td> 
   <td>O(n * log(n)) / O(n * log(n)) / O(n*log(n))</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>堆排序</td> 
   <td></td> 
   <td></td> 
   <td>不稳定</td> 
   <td>O(n * log(n)) / O(n * log(n)) / O(n * log(n))</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>快速排序</td> 
   <td>完全二叉树</td> 
   <td>单支树</td> 
   <td>不稳定</td> 
   <td>O(n * log(n)) / O(n * log(n)) / O(n<sup>2</sup>)</td> 
   <td>O(log(n)~O(n)</td> 
  </tr> 
  <tr> 
   <td>归并排序</td> 
   <td></td> 
   <td></td> 
   <td>稳定</td> 
   <td>O(n * log(n)) / O(n * log(n)) / O(n*log(n))</td> 
   <td>O(n)</td> 
  </tr> 
 </tbody> 
</table>

# 快速排序的优化 #

*  基准值的选择方法  
    三数取中  
    随机选择  
    双基准值
 *  进行partition的过程中，将基准值归拢在一起
 *  递归->非递归
 *  数据量较小时，使用插排代替

# 海量数据排序问题： #

关于海量数据做排序——这是一个外部排序（需要用到非内存的存储，例如：硬盘）

*  将文件平均分割，保证每个小文件的大小足够进行内部排序（内存放得下）
 *  分别针对每个小文件进行独立的排序：m个有序的小文件（数组）
 *  进行多路归并——合并多个有序数组变成一个有序数组。