排序技术

01-数据结构与算法 飞快学 370浏览

本节需要掌握各种排序法的特点和时间复杂度。

排序的基本概念

排序是指将一个无序序列整理成按值非递减顺序排列的有序序列,即是将无序的记录序列调整为有序记录序列的一种操作。

1、交换类排序法(方法:冒泡排序,快速排序)。

2、插入类排序法(方法:简单插入排序,希尔排序)。

3、选择类排序法(方法:简单选择排序,堆排序)。

排序算法的稳定性 若待排序的序列中,存在多个具有相同关键字的记录,经过排序, 这些记录的相对次序保持不变,则称该算法是稳定的;若经排序后,记录的相对次序发生了改变,则称该算法是不稳定的。 举个例子,假定张三同学和李四同学的成绩相等,在按照成绩排序前,张三的顺序出现在李四前面,那么如果算法是稳定的,排序后,张三的顺序还应该在李四的前面。

堆是完全二叉树

由堆的定义可以看出,堆顶元素(即第一个元素)必为最小项(小顶堆)。

若以一维数组存储一个堆,则堆对应一棵完全二叉树,且所有非叶结点的值均不大于(或不小于)其子女的值,根结点(堆顶元素)的值是最小(或最大)的。如:

(a)大顶堆序列:(96,83,27,38,11,09)
(b)小顶堆序列:(12,36,24,85,47,30,53,91)

堆是完全二叉树,而完全二叉树既可以采用数组方式(顺序)存储,也可以采用指针方式(链式)存储。

常见排序算法的特点

排序法 平均时间 最差情形 稳定度 额外空间 备注
冒泡 O(n2) O(n2) 稳定 O(1) n小时较好
交换 O(n2) O(n2) 不稳定 O(1) n小时较好
选择 O(n2) O(n2) 不稳定 O(1) n小时较好
插入 O(n2) O(n2) 稳定 O(1) 大部分已排序时较好
希尔 O(nlogn) O(ns), 1<s<2 不稳定 O(1) s是所选分组
快速 O(nlogn) O(n2) 不稳定 O(nlogn) n大时较好
O(nlogn) O(nlogn) 不稳定 O(1) n大时较好

和堆排序相比,快速排序对于Cache的利用更为充分,快速排序是实际环境下效率最高的排序方式,C语言在stdlib库中提供了快速排序函数 qsort。