[科普中国]-排序关键字

基本概念

排序:将数据表(datalist)中无规律数据按关键码在一定的规律顺次下排列起来。

关键码(key):通常数据对象有多个属性域，即多个数据成员组成，其中有一个属性域可用来区分对象，作为排序依据。该域即为关键码。每个数据表用哪个属性域作为关键码，要视具体的应用需要而定。即使是同一个表，在解决不同问题的场合也可能取不同的域做关键码。

主关键码:如果在数据表中各个对象的关键码互不相同，这种关键码即主关键码。按照主关键码进行排序，排序的结果是唯一的。

次关键码:数据表中有些对象的关键码可能相同，这种关键码称为次关键码。按照次关键码进行排序，排序的结果可能不唯一。

排序算法的稳定性:如果在对象序列中有两个对象:f[i]和:f[j]，它们的关键码k[i] - k[j]，且在排序之前，对象:r[i]排在r[j]前面。如果在排序之后，对象r[i]仍在对象r[j]的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的。

内排序与外排序:内排序是指在排序期间数据对象全部存放在内存的排序;外排序是指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。

排序的时间开销:排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。

静态排序:排序的过程是对数据对象本身进行物理地重排，经过比较和判断，将对象移到合适的位置。这时，数据对象一般都存放在一个顺序的表中。

动态排序:给每个对象增加一个链接指针，在排序的过程中不移动对象或传送数据，仅通过修改链接指针来改变对象之间的逻辑顺序从而达到排序的目的。1

算法直接插人排序算法思想:将一个待排序的记录插入到已排好序的有序表中的适当位置，从而得到一个新的、记录数增1的有序表。

希尔排序算法思想:希尔排序是对直接插入排序改进后提出的，又称“缩小增量排序”。先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

冒泡排序算法思想:对待排序的记录关键字进行两两比较，若两个记录是反序的，则进行交换，直到无反序的记录为止。

快速排序算法思想:是对冒泡排序的一种改进、通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，已达到整个序列有序。

简单选择排序算法思想:每一趟排序是通过进行n-i次关键字的比较，从n-i+ 1个待排序记录中选出关键字最小的记录后和第i个记录进行交换，直到待排序的数据元素有序为止。

堆排序算法思想:堆排序是一种树形选择排序。首先需要将待排序记录按排序关键字建成一个小(或大)顶堆，即子结点的关键字总是小于(或者大于)它的父节点。然后输出堆顶的元素，把剩余n-1个元素的序列重新调整成一个堆，重复此过程，直到待排序的数据元素有序为止。

归并排序算法思想:“归并”是将两个或两个以上的有序表合并成一个新的有序表。若待排序记录有n个，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到个长度为2或1的有序子序列;再两两归并，如此重复，直至得到一个长度为n的有序序列为止、2

算法比较对常用排序算法进行了比较，分别给出了不同算法的时间复杂度、空间复杂度、稳定性和复杂性的分析。2