全屏显示专题章节

假设含n个记录的序列为{R₁，R₂，…，R_n}，其相应的键值序列为{k₁，k₂，…，k_n}。这样一些记录重新排列为{R_i1，R_i2，…，R_in}，使得相应的键值满足条件k_i1≤k_i2≤…≤k_in,这样一种运算称为排序。

稳定排序和不稳定排序：假定待排序的序列中存在多个记录具有相同的键值。若经过排序，这些记录的相对次序仍然保持不变(即在原序列中k_i=k_j，且i＜j；而在拓序后的序列中，R_i仍在R_j之前)，则称这种排序方法是稳定的，否则称为不稳定的。

排序的分类：插入排序，交换排序，选择排序，归并排序。

(1) 直接插入排序。基本思想是，依次将每个记录插入到一个有序中去。排序性能：该方法是稳定的，时间复杂性为O(n²)；空间复杂度为O(1)。

(2) 折半插入排序。插入排序的基本操作是在一个有序表中进行查找和插入，查找可以用折半查找来实现，就可以称折半插入排序；排序的时间复杂度是O(n²)。

(3) 2路插入排序。基本思想是另设一个和L.r同类型的数组d，首先将L.r[1]赋值给d[1]，并将d[1]看成是在排好序的序列中处于中间位置的记录，然后从L.r中第2个记录起依次插入到d[1]之前或之后的有序序列中。先将待插记录的关键字和d[1]的关键字进行比较，若Lr[i].key＜d[1].key，则将L.r[i]插入到d[1]之前的有序表中。反之，则将L.r[i]插入到d[1]之后的有序表中。

(4) 表插入排序。就是通过链接指针，按关键码的大小，实现从小到大的链接过程，为此需增设一个指针项。操作方法与直接插入排序类似，所不同的是直接插入排序要移动记录，而表插入排序是修改链接指针.

(5) 希尔排序。基本思想是先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。希尔排序方法是一种不稳定的排序方法。

(1) 起泡排序。基本做法是首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序(即L.r[1].key＞L.r[2].key)，则将两个记录交换之，然后比较第二个记录和第三个记录的关键字。依次类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。最好情况下，待排序的序列为正序，时间复杂度为O(n)；最坏情况下，待排序的序列为逆序，时间复杂度为O(n²)；平均情况下排序的时间复杂度为O(n²)。

(2) 快速排序。基本思想是通过一趟排序将待排序记录分割成独立的两部分，其中一部分的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。最好情况下，每次划分轴值的左侧子序与右侧子序的长度相同，时间复杂度为O(nlog₂n);最坏情况下，待排序的序列为正序或逆序，时间复杂度为O(n²)；平均情况下排序的时间复杂度为O(nlog₂n)。

(1) 简单选择排序。基本思想是：第i趟通过n-i次关键码的比较，在n-i+1(1≤i≤n-1) 个记录中选取关键码最小的记录，并和第i个记录交换作为有序序列的第i个记录。最好、最坏、平均的时间复杂度都是O(n²)。

(2) 树形选择排序。一种按照锦标赛的思想进行选择排序的方法。首先对n个记录的关键字进行两两比较，然后在其中[n/2]个较小者之间再进行两两比较，如此重复，直至选出最小关键字的记录为止。时间复杂度为O(nlog₂n)。

(3) 堆排序。基本思想是，首先将待排序的记录序列构造成一个堆，并选出了堆中所有记录的最大者即堆顶记录，然后将它从堆中移走，并将剩余的记录再调整为堆，这样就找出了次大的记录，以此类推，直到堆中只有一个记录为止。最好、最坏、平均的时间复杂度都是O(nlog₂n)。

归并是将两个或两个以上的有序表合并成一个新的有序表。

2路归并的基本思想是将若干个有序表进行归并，直至所有待排序记录都在一个有序序列为止。最好、最坏、平均的时间复杂度都是O(nlog₂n)。

基数排序是借助“分配”和“收集”两种操作对单逻辑关键字进行内部排序的方法。

(1) 多关键字的排序。有最高优先法(MSD)和最低优先法(LSD)两种。

(2) 链式基数排序。基本过程：若关键字是数值，且其值都在0≤K≤999范围内，则可把每一个十进数字看成一个关键字，即可认为K由三个关键字(K⁰，K¹，K²)组成，其中K⁰是百位数K¹是十位数，K²是个位数；又若关键字K是由五个字母组成的单词，则可看成是由五个关键字(K⁰，K¹，K²，K³，K⁴)组成，由于如此分解而得的每个关键字长K^j都在相同的范围内，则按LSD进行排序更为方便，只需从最低数位关键字起，按关键字的不同值将序列中记录“分配”到RADIX个队列中后再“收集”之，如此重复d次。