排序算法系列

概述

---

概念 排序是计算机内经常进行的一种操作，其目的是将一组 “无序”的记录序列调整为 “有序”的记录序列。

排序分为内部排序和外部排序。

若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。

反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。

 

 

排序分类

---

如果按照策略来分类，大致可分为：交换排序、插入排序、选择排序、归并排序和基数排序。如 图-排序策略分类图 所示。

图-排序策略分类图

 

 

 

 

算法分析

---

下表给出各种排序的基本性能，具体分析请参看各排序的详解。

  排序类别排序方法时间复杂度空间复杂度稳定性复杂性平均情况最坏情况最好情况交换排序冒泡排序O(n²)O(n²)O(n)O(1)稳定简单快速排序O(nlog₂n)O(n²)O(nlog₂n)O(nlog₂n)不稳定较复杂插入排序直接插入排序O(n²)O(n²)O(n)O(1)稳定简单希尔排序O(nlog₂n)O(n^1.5) O(1)不稳定较复杂选择排序简单选择排序O(n²)O(n²)O(n²)O(1)不稳定简单堆排序O(nlog₂n)O(nlog₂n)O(nlog₂n)O(1)不稳定较复杂归并排序归并排序O(nlog₂n)O(nlog₂n)O(nlog₂n)O(n)稳定较复杂基数排序基数排序O(d(n+r))O(d(n+r))O(d(n+r))O(n+r)稳定较复杂

 

 

 

系列文章

---

 

排序一 冒泡排序

排序二 快速排序

排序三 直接插入排序

排序四 希尔排序

排序五 简单选择排序

排序六 堆排序

排序七 归并排序

排序八 基数排序