0 排序的基本概念与分类

Wu Jun 2019-12-25 15:59:04
01 数据结构与算法 > 数据结构 > 04 排序

1 排序的基本概念

假设含有 n 个记录的序列为{r1,r2,…,rn} ,其相应的关键字分别为{k1,k2,…,kn} ,需确定 1,2,…,n 的一种排列 p1,p2,…,pn,使其相应的关键字满足 kpl<=kp2<=…<=kpn (非递减或非递增) 关系,即使得序列成为一个按关键字有序的序列{rp1,rp2,…,rpn},这样的操作就称为排序 。

2 排序的稳定性

在待排序的文件中,若存在多个关键字相同的记录,经过排序后这些具有相同关键字的记录之间的相对次序保持不变,该排序方法是稳定的;若相对次序发生变化,则称这种排序方法是不稳定的。

3 排序的分类

4 各种内部排序算法的比较

排序方法 平均情况 最好情况 最坏情况 辅助空间 稳定性
冒泡排序 O(n2) O(n) O(n2) O(1) 稳定
直接选择排序 O(n2) O(n) O(n2) O(1) 稳定
直接插入排序 O(n2) O(n) O(n2) O(1) 稳定
希尔排序 O(nlogn)~O(n2) O(n1/3) O(n2) O(1) 不稳定
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定
快速排序 O(nlogn) O(nlogn) O(n2) O(logn)~O(n) 不稳定

从平均情况来看,显然最后 3 种改进算法要胜过希尔排序,并远远胜过前 3 种简单算法。

从最好情况看,反而冒泡和直接插入排序要更胜一筹,也就是说,如果你的待排序序列总是基本有序,反而不应该考虑 4 种复杂的改进算法。

从最坏情况看,堆排序与归并排序又强过快速排序以及其他简单排序。