文档介绍：第三章 查找与排序(下)
本节内容
通过本单元的学****了解、掌握有关排序的:
基本概念:
排序、排序分类、算法稳定性
典型的排序算法:
插入排序、选择排序、交换排序
归并排序、基数排序
排序的基本概念
定义:将记录按关键字递增(递减)的次序排列起来,形成新的有序序列,称为排序。
描述:
设n个记录的序列为{R1,R2,…,Rn},其相应关键字序列为{K1,K2,…,Kn},需确定一种排序P1,P2,…,Pn,使其相应的关键字满足递增(升序),或递减(降序)的关系:
Kp1 Kp2 ... Kpn
或
Kp1 Kp2 …. Kpn
基本的排序技术
虽然排序算法是一个简单的问题,但是从计算机科学发展以来,已经有大量的研究在此问题上。举例而言,冒泡排序在1956年就已经被研究。虽然大部分人认为这是一个已经被解决的问题,有用的新算法仍在不断的被发明。(例子:图书馆排序在2004年被发表)
算法稳定性
21
25
49
25*
16
08
0 1 2 3 4 5
49
08
16
Exchang=1
25*
25
21
49
08
16
Exchang=1
25
25*
21
算法稳定性
当相等的元素是无法分辨的,比如像是整数,稳定性并不是一个问题。然而,假设以下的数对将要以他们的第一个数字来排序。
(4, 1) (3, 1) (3, 7) (5, 6)
(3, 1) (3, 7) (4, 1) (5, 6) (保持次序)
(3, 7) (3, 1) (4, 1) (5, 6) (次序被改变)
不稳定排序算法可能会在相等的键值中改变纪录的相对次序。
不稳定排序算法可以被特别地实现为稳定。方法是人工扩充键值的比较。然而,要记住这种次序通常牵涉到额外的空间负担。
简单起见,这里用顺序存储结构描述待排序的记录。
顺序存储结构(C语言描述):
#define N n
typedef struct record {
int key ; /* 关键字项*/
int otherterm; /* 其它项*/
} ;
typedef struct record RECORD;
RECORD file[N+1];/*RECORD型的N+1元数组*/
排序算法的数据结构
典型排序算法
冒泡排序
快速排序
简单插入排序
希尔排序
简单选择排序
堆排序
归并排序
基数排序
二叉排序树