软考软件设计师专题讲义九：数据结构相关算法

 　　3. 数据结构相关算法

　　3.1排序算法

　　基本概念

　　排序(Sorting)是计算机程序设计中的一种重要操作，其功能是对一个数据元素集合或序列重新排列成一个按数据元素某个项值有序的序列。作为排序依据的数据项称为"排序码"，也即数据元素的关键码。为了便于查找，通常希望计算机中的数据表是按关键码有序的。如有序表的折半查找，查找效率较高。还有，二叉排序树、B-树和B+树的构造过程就是一个排序过程。若关键码是主关键码，则对于任意待排序序列，经排序后得到的结果是唯一的;若关键码是次关键码，排序结果可能不唯一，这是因为具有相同关键码的数据元素，这些元素在排序结果中，它们之间的的位置关系与排序前不能保持。

　　若对任意的数据元素序列，使用某个排序方法，对它按关键码进行排序：若相同关键码元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的;而不能保持一致的排序方法则称为不稳定的。

　　排序分为两类：内排序和外排序。

　　内排序：指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。

　　外排序：指排序过程中还需访问外存储器，足够大的元素序列，因不能完全放入内存，只能使用外排序。

　　对于有n个结点的线性表(e0，e1，…，en-1)，将结点中某些数据项的值按递增或递减的次序，重新排列线性表结点的过程，称为排序。排序时参照的数据项称为排序码，通常选择结点的键值作为排序码。

　　若线性表中排序码相等的结点经某种排序方法进行排序后，仍能保持它们在排序之前的相对次序，称这种排序方法是稳定的;否则，称这种排序方法是不稳定的。

　　在排序过程中，线性表的全部结点都在内存，并在内存中调整它们在线性表中的存储顺序，称为内排序。在排序过程中，线性表只有部分结点被调入内存，并借助内存调整结点在外存中的存放顺序的排序方法成为外排序。

　　下面通过一个表格简单介绍几种常见的内排序方法，以及比较一下它们之间的性能特点。