数据结构c语言版纲要：第十章 内部排序

10.1 概述 10.2.1 直接插入排序 10.2.2 其他插入排序

10.2 插入排序

10.2.3 希尔排序

内 部 排 序

10.3 快速排序 10.4.1 简单选择排序 10.4 选择排序 10.4.2 树形选择排序 10.4.3 堆排序 10.5 归并排序 10.6.1 多关键字的排序 10.6.2 链式基数排序 10.7 各种内部排序方法的比较讨论

10.6 基数排序

排序：讲一个数据元素的任意序列，重新排列成一个按关键字有序的序列。排序方法是稳定的：排序前后，两相同的元素，前后相对位置不变。 排序方法是不稳定的：排序前后，两相同的元素，前后相对位置改变。 插入排序 交换排序 选择排序 归并排序 计数排序 简单的排序 先进的排序 基数排序

概 述

按方法分类 内部排序： 按所需工作量区分

外部排序

直接插入排序：

将一个记录插入到已排好的有序表中， 得到新的长度增加1的有序表

插 入 排 序 与 快 速 排 序

折半插入排序 其他插入排序： 2-路插入排序 表插入排序 希尔排序(缩小增量排序)

起泡排序

枢轴(支点)

简单选择排序

通过n-i次关键字间的比较，从ni+1个记录中选出关键字最小的记 录，与第i个记录交换。

选 择 排 序

树形选择排序(锦标赛排序):

N个关键字两两比较，如此重复， 直到选出最小关键字的记录位止。

堆排序

只需要一个记录大小的辅助空间， 每一个待排序的记录仅占有一个存 储空间。

归 并 排 序 与 基 数 排 序

基数排序：借助多关键字排序的思想对单逻辑关键字 进行排序的方法。

多关键字排序：最高位优先/最低位优先

链式基数排序：分、收->分、收->分、收->……

排序方法

最好时间

平均时间

最坏时间

辅助空间

稳定性

直接插入排 序折半插入排 序 希尔排序 快速排序

O(1)O(1) O(1) O(1)

O(n2)O(n2) O(n2/3) O(nlogn)

O(n2)O(n2) O(n2/3) O(n2)

O(1)O(1) O(1) O(logn)

稳定稳定 不稳定 不稳定

简单选择排 序树形选择排 序 堆排序 归并排序

O(1)O(1) O(1) O(1)

O(n2)O(nlogn) O(nlogn) O(nlogn)

O(n2)O(nlogn) O(nlogn) O(nlogn)

O(1)O(n) O(1) O(n)

不稳定不稳定 不稳定 稳定

基数排序

O(1)

O(d (n+rd))

O(d (n+rd))

O(rd)

稳定