1 排序的基本概念

排序：就是将记录按关键字递增(递减)的次序排列起来,形成新的有序序列,称为排序。设n个记录的序列为{R₁,R₂,…,R_n},其相应关键字序列为{K₁,K₂,…,K_n},需确定一种排序P₁,P₂,…,P_n,使其相应的关键字满足递增(升序),或递减(降序)的关系:
Kp₁ £ Kp₂ £ ...£ Kp_n 
或
Kp₁ ³ Kp₂ ³ … ³ Kp_n

根据排序元素所在位置的不同,排序分: 内排序和外排序。
内排序：在排序过程中，所有元素调到内存中进行的排序，称为内排序。内排序是排序的基础。内排序效率用比较次数来衡量。按所用策略不同，内排序又可分为插入排序、选择排序、交换排序、归并排序及基数排序等几大类。
外排序：在数据量大的情况下，只能分块排序，但块与块间不能保证有序。外排序用读/写外存的次数来衡量其效率。

排序算法的稳定性：若待排序的序列中，存在多个具有相同关键字的记录，经过排序，这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对次序发生了改变，则称该算法是不稳定的。

排序算法的存储结构通常有三种：一维数组；链表；辅助表（如索引表）。
顺序存储结构（C语言描述）：
typedef struct {
int key ；       /* 关键字项 */
datatype other； /* 其它项 */
} rectype；
rectype R[n]；   /* R为记录类型的数组，n为文件的记录总数 */

典型排序算法：插入排序、选择排序、交换排序、快速排序、归并排序。

2 插入排序

基本思想： 将n个元素的数列分为已有序和无序两个部分。每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较,找出插入位置,将该元素插入到有序数列的合适位置中。

2.1 直接插入排序(线性插入排序，稳定)

    直接插入排序是一种最简单的排序方法。具体算法步骤：
Step1 从有序数列{a₁}和无序数列{a₂,a₃,…,a_n}开始进行排序；
Step2 处理第i个元素时(i=2,3,…,n),数列{a₁,a₂,…,a_i-1}是已有序的,而数列{a_i,a_i+1,…,a_n}是无序的。用a_i与a_i-1、a_i-2,…,a₁进行比较,找出合适的位置将a_i插入。
Step3 重复Step2，共进行n-1的插入处理，数列全部有序。

例：设有八个记录，其关键字为{47，33，61，82，72，11，25，47'}

算法描述：

算法中引进一个附加记录R[0]，其作用有两个：(1) 进入查找循环之前，它保存了R[i]的副本，使得不至于因记录的后移而丢失R[i]的内容；(2) 在while循环中“监视”下标变量j是否越界，以避免循环内每次都要检测j是否越界。

    直接插入排序的时间复杂度为O(n²)，空间复杂度为O(1)。

2.2 希尔排序(缩小增量排序，不稳定)

希尔排序是一种快速排序法，出自D.L.Shell。基本思想是：
    仍采用插入法，排序过程通过调换并移动数据项来实现。先取一个小于n的整数d₁并作为第一个增量，将文件的全部记录分成d₁个组，所有距离为d1倍数的记录放在同一个组中，在各组内进行直接插入排序；然后取第二个增量d₂<d₁，重复上述的分组和排序，直至所取的增量d_t=1(d_t<d_t-1<...<d₂<d₁)为止，此时，所有的记录放在同一组中进行直接插入排序。增量一般d按给定公式减少： d_i+1 =（d_i + 1）/2 ，直到d等于1为止。

例，有关键字序列{47，33，61，82，71，11，25，47’，57，02}，增量取5，3，1。

算法描述参见教材。

3 选择排序(不稳定)

    基本思想是：每次从待排序的记录中选出关键字最小（或最大）的记录，顺序放在已有序的记录序列的最后（或最前）面，直到全部数列有序。

例，有关键字序列{49，38，65，97，76，13，27，49’}

最大移动次数3(n-1)，时间复杂度为O(n²)。

4 交换排序

    基本思想：两比较待排序记录的关键字，发现两个记录逆序时即进行交换，直至没有逆序的记录为止。

4.1 起泡排序(冒泡排序，稳定)

    基本思想：通过两两比较待排序元素，若为逆序（递增或递减）则进行交换，将待排序元素从左至右比较一遍称为一趟“冒泡”。每趟冒泡都将待排序列中的最大关键字交换到最后（或最前）位置。直到全部元素有序为止。

    排序过程：
step1 将关键字按纵向排列，然后自下而上地对每两个相邻的关键字进行比较，若饿日为逆序(即k_j-1>k_j)，则将两个记录交换位置，这样的操作反复进行，直至全部记录都比较、交换完为止。一趟冒泡处理，就将关键字最小的记录安排在第一记录的位置上。
step2 对后n-1个记录重复同样操作，再将次小关键字记录安排在第二个记录的位置上。
Step3 重复上述过程直至没有记录需要交换为止。

例，有关键字序列{47，33，61，82，72，11，25，47’}

具体算法：

也可由大到小排序，由上至下比较、交换即可。例

算法分析：最坏情况，比较(n²-n)/2次，移动(n²-n)*3/2。算法时间复杂度O(n²)。

4.2 快速排序(不稳定)

    快速排序法是一位计算机科学家C.A.R.Hoare推出并命名的。曾被认为是最好的一种排序方法。快速排序法是对冒泡排序法的一种改进，也是基于交换排序的一种算法。因此，被称为“分区交换排序”。

    基本思想：每一步都要把要排序的表（或称做子表的表的一部分）第一个元素放到它在表中的最终位置，同时在这个元素的前面和后面个形成一个子表。在前面子表中的所有元素的关键字都比该元素的关键字小，而在后面子表中的都比它大。此后再对每个子表做这同样的一步，直至最后每个子表都只有一个元素，排序完成。

例，有关键字序列{46，55，13，42，94，5，17，70}

最坏情况的时间复杂度为O(n²)，最好情况时间复杂度为O(nlog₂n)。

5 归并排序(稳定)

    归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表：即把待排序序列分为若干个子序列，每个子序列是有序的，然后再把有序子序列合并为整体有序序列。
    将已有序的子序列合并，得到完全有序的序列：即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

归并排序具体步骤：
Step1 把待排序的n个记录看作是长度为1的有序序列。将相邻子序列两两归并为长度为2的有序序列；
Step2 把得到的n/2个长度为2的有序子序列再归并为长度为 2*2 的有序序列；
Step3 按Step2的方式，重复对相邻有序子序列进行归并操作，直到成为一个有序序列为止。

例，有关键字序列{47，33，61，82，72，11，25，47’}

算法时间复杂度为O(nlog₂n)。算法中需要辅助数组。

各种排序方法的比较。