基本概念；插入排序；交换排序；选择排序；归并排序；排序的选择
基本概念
排序:是计算机程序设计中的一项重要操作，其功能是指一个数据元素集合或 序列重新排列成一个按数据元素某个数据项值有序的序列。
排序码(关键码):排序依据的数据项。 稳定排序:排序前与排序后相同关键码元素间的位置关系，保持一致的排序方法。
不稳定排序:排序前与排序后相同关键码元素间的相对位置发生改变的排序方法
排序分为两类：
（1）内排序:指待排序列完全存放在内存中所进行的排序。内排序大致可分为五类：（本章主要讨论内排序。）
- 插入排序
- 交换排序
- 选择排序
- 归并排序
- 配排序。
（2）外排序：指排序过程中还需访问外存储器的排序。 为了以后讨论方便，我们直接将排序码写成一个一维数组的形式，并且在没有声明的情形下，所有排序都按排序码的值递增排列。
插入排序
基本思想
每次将一个待排序的元素，按其关 键字的大小插入到前面已经排好序的子文件的适 当位置，直到全部记录插入完成为止。
直接插入排序
直接插入排序的基本思想是：把n个待排序的元素 看成为一个有序表和一个无序表，开始时有序表中只包 含一个元素，无序表中包含有n-1个元素，排序过程中 每次从无序表中取出第一个元素，把它的排序码依次与 有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
void D-InsertSort(datatype R[ ],int n)
/*待排序的n个元素放在数组R中，用直接插入法进行排序*/
{ for ( i=2; i<=n; i++) /*i控制第i-1次插入,最多进行n-1次插入*/
if (R[i].key<R[i-1].key) /*小于时,需将R[i]插入有序表*/
{ R[0]=R[i]; /*为统一算法设置监视哨*/
for ( j=i-1; R[0].key<R[j].key;j--) R[j+1]=R[j]; /*元素后移*/
R[j+1]= R[0]; /*将放在R[0]中的第i个元素插入到有序表中*/
}
}
直接插入排序的效率分析
首先从空间来看，它只需要一个元素的辅助空间，用于元素的位置交换。从时间分析，首先外层循 环要进行n-1次插入, 每次插入最少比较一次(正序), 移动0次;最多比较i次(包括同监视哨R[0]的比较),移 动i＋1次(逆序)(i=2,3,…,n)。
直接插入算法的元素移动是顺序的，该方法是 稳定的。
交换排序
主要是通过排序表中两个记录关键码的比较，若与排序要求相逆（不符合 升序或降序），则将两者交换。
冒泡排序
基本思想
冒泡排序的基本思想：通过对待排序序列从前向后，依次比较相邻元素的排 序码，若发现逆序则交换，使排序码较大的元素逐渐从前部移向后部。
因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进 行过交换，就说明序列有序，因此要在排序过程中设置一个标志swap判断元素是 否进行过交换。从而减少不必要的比较。
具体过程
若序列中有 n 个元素，通常进行 n - 1 趟。第 1 趟，针对第R[1] 至R[n]个 元素进行。第 2 趟，针对第 R[1] 至 R[n－1] 个元素进行。…… 第 n-1 趟，针 对第 R[1] 至 R[2] 个元素进行。
每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。若相邻的 元素的相对位置不正确,则进行交换；否则继续比较下面两个相邻的元素。
结束条件：在任何一趟进行过程中，未出现交换。
如: 将序列 49、38、65、97、76、13、27、49 用起泡排序的方法进行 排序
算法实现
void Bubble-sort( datatype R[],int n)
{
int i, j, swap; /* 当swap为0则停止排序 */
for ( i=1; i<n; i++) /* i 表示趟数，最多n-1趟 */
{
swap=0; /* 开始时元素未交换 */
for ( j=1; j<=n-i; j++)
if (R[j].key>R[j+1].key) /* 发生逆序 */
{
R[0]=R[j];R[j]=R[j+1];R[j+1]=R[0];
swap=1;
} /* 交换，并标记发生了交换 */ if(swap==0) break;
}
}
效率分析
快速排序(分区交换排序)
基本思想
快速排序（Quick Sorting）是迄今为止所有内排序算法中速度最快的一种。
它的基本思想是：
- 任取待排序序列中的某个元素作为标准（也称为支点、界点，一般取第一个元素），通过一次划分，将待排元素分为左右两个子序列
- 左子序列元素的排序码均小于基准元素的排序码，右子序列的排序码则大于或等于基准元素的排序码
- 然后分别对两个子序列继续进行划分，直至每一个序列只有一 个元素为止。
- 最后得到的序列便是有序序列。
算法实现
void Quick_Sort(datatype R[],int s,int t) /* 对R[s]到R[t]的元素进行排序*/
{
if (s<t){
i=Partition(R,s,t); Quick_Sort(R,s,i-1); Quick_Sort(R,i+1,t);
}
}
int Partition(datatype R[],int low,int high)
{
R[0]=R[low]; /* 暂存界点元素到R[0]中*/
while(low<high) /* 从表的两端交替地向中间扫描 */
{
while(low<high&&R[high].key>=R[0].key)
high--;
if(low<high){
R[low]=R[high];
low++;
}
while(low<high&&R[low].key<R[0].key)
low++;
if (low<high) {
R[high]=R[low]; high--;
}
}
R[low]=R[0]; /* 将界点元素放到其最终位置 */
return low; /* 返回界点元素所在的位置*/
}
快速排序的递归树
快速排序的递归过程可用一棵二叉树形象地 给出。下图为待排序列49、38、65、97、76、13、27、49所对应的快速排序递归调用过 程的二叉树(简称为快速排序递归树)。
从快速排序算法的递归树可知, 快速排序的趟数取决于递归树的高度。
时间复杂度
如果每次划分对一个对象定位后，该对象的左子序列与右子序列的长度相同, 则下一步将是对两个长度减半的子序列进行排序, 这是最理想的情况。
快速排序的空间复杂度及稳定性
选择排序
基本原理
将待排序的元素分为已排序( 初始为空)和未排序两组，依次将未排序的元素中值最小的元素放入已排序的组中。
两种常见的选择排序
- 简单选择排序
- 堆排序
简单选择排序
简单选择排序的基本过程为：
- 在一组元素R[i]到R[n]中选择具有最小关键码的元素
- 若他不是这组元素的第一个元素，则将它与这组元素中的第一个元素对调
- 出去具有最小关键字的元素，在剩下的元素中重复（1）、（2）步，直至剩余元素只有一个为止
算法实现
//简单选择排序
public static void SelectSort(int R[],int n){
int k = 1;
for(int i=1;i<n;i++){
k=i;
for(int j=i;j<=n;j++){
if(R[j]<R[k]){
k=j;
}
}
if(k!=i){
R[0]=R[k];
R[k]=R[i];
R[i]=R[0];
}
}
}
效率分析
堆排序
堆排序是简单选择排序的改进。用 直接选择排序从n个记录中选出关键字值最小的记录要做n-1次比较，然后从其余n-1个记录中选出最小者要作n-2次比较
- 显然，相邻两趟中某些比较是重复的
- 为了避免重复比较，可以采用树形选 择排序比较。
堆的定义
若将此排序码按顺序组成一棵完全二叉树
则（a）称为小顶堆（二叉 树的所有结点值小于或等于左右孩子的值）
（b）称为大顶堆（二叉树的所有结点值大于或等于左右孩子的值）。
基本思想
建初始堆
将排序码k1，k2，k3，…，kn表示成一棵完全二叉树，然后从第⎣n/2⎦个排序码(即树的最后一个非终端结点)开始筛选，使由该结点作根结点组成的子二叉树符合堆的定义，然后从第⎣n/2⎦-1个排序码重复刚才操作，直到第一个排序码止。这时候，该二叉树符合堆的定义，初始堆已经建立。
堆排序
将堆中第一个结点（二叉树根结点）和最后一个结点的数据进行交换（k1与kn），再将k1~kn-1重新建堆，然后k1和kn-1交换，再将k1~kn-2重新建堆，然后k1和kn-2交换，如此重复下去，每次重新建堆的元素个数不断减1，直到重新建堆的元素个数仅剩一个为止。这时堆排序已经完成，则排序码k1，k2，k3，…，kn已排成一个有序序列。
两大步骤
- 根据初始输入数据形成初始堆
- 通过一系列的元素交换和重新调整堆进行排序。
Heapify
调整堆内的子树位置，将三个中的较大的值置于父节点；
设当前节点数为i；则它的父节点为(i-1)/2；它的子节点数为2i-1、2i+1；
利用递归调整它的子树满足大堆顶的形式
public static void Heapify(int tree[],int n, int i){
if(i >= n){
return;
}
int c1 = 2 * i + 1;
int c2 = 2 * i + 2;
int max = i;
if(c1 < n && tree[c1] > tree[max]){
max = c1;
}
if(c2 < n && tree[c2] > tree[max]){
max = c2;
}
if(max != i){
swap(tree,max,i);
Heapify(tree, n, max);
}
}
heapSort
最后一个节点为(arr.length-1)；它所在的父节点位置为(arr.length-2)/2；由此开始递减即可创建初始堆。
每次建堆完成后，将最后一个节点与堆顶元素互换，并将下次建堆的长度-1，即选择出的最大值不参与下次的建堆操作。
public static void heapSort(int tree[],int n){
for(int i = (n - 2)/2;i >= 0;i--){
Heapify(tree,n,i);
}
int i;
for(i = n - 1;i>=0;i--){
swap(tree,i,0);
Heapify(tree,i,0);
}
}
效率分析
归并排序
路归并排序
基本思想
将两个有序表合并成一个有序表。
例如，将下列两个已排序的顺序表合并成一个已排序表。顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另 一表为止。
代码实现
public static void sort(int []arr){
int []temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
sort(arr,0,arr.length-1,temp);
}
private static void sort(int[] arr,int left,int right,int []temp){
if(left<right){
int mid = (left+right)/2;
sort(arr,left,mid,temp);//左边归并排序，使得左子序列有序
sort(arr,mid+1,right,temp);//右边归并排序，使得右子序列有序
merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
}
}
private static void merge(int[] arr,int left,int mid,int right,int[] temp){
int i = left;//左序列指针
int j = mid+1;//右序列指针
int t = 0;//临时数组指针
while (i<=mid && j<=right){
if(arr[i]<=arr[j]){
temp[t++] = arr[i++];
}else {
temp[t++] = arr[j++];
}
}
while(i<=mid){//将左边剩余元素填充进temp中
temp[t++] = arr[i++];
}
while(j<=right){//将右序列剩余元素填充进temp中
temp[t++] = arr[j++];
}
t = 0;
//将temp中的元素全部拷贝到原数组中
while(left <= right){
arr[left++] = temp[t++];
}
}
效率分析
基数排序
基数排序是和前面所述的各种排序方法完全不同的一种排序方法。前面介绍的几种排序 方法，都是根据关键字之间的比较和移动记录 来实现的，基数排序不需要进行记录关键字间 的比较，而是根据组成关键字的各位值，即借 助于多关键字排序的思想，用“分配”和“收 集”的方法进行排序。
两种作法:
最高位优先MSD法：先对K0进行排序，并按K0的 不同值将记录序列分成若干子序列之后，分别 对K1进行排序，…，依次类推，直至最后对最 次位关键字排序完成为止。
最高位优先MSD法：先对K0进行排序，并按K0的 不同值将记录序列分成若干子序列之后，分别 对K1进行排序，…，依次类推，直至最后对最 次位关键字排序完成为止。
比较MSD法和LSD法，一般来讲，LSD法要比MSD法来得简单，因为LSD 法是从 头到尾进行若干次分配和收集，执行的 次数取决于构成关键字值的成分为多少；而MSD 法则要处理各序列与子序列的独立排序问题，就可能复杂一些。
链式基数排序
假如多关键字的记录序列中，每个关键字的取值 范围相同，则按LSD法进行排序时，可以采用“分 配-收集”的方法，其好处是不需要进行关键字间 的比较。
对于数字型或字符型的单关键字，可以看成是由 多个数位或多个字符构成的多关键字，此时可以 采用这种“分配-收集”的办法进行排序，称作基数 排序法。
在计算机上实现基数排序时，应采用链表作存 储结构，即链式基数排序，具体作法为：
- 待排序记录以指针相链，构成一个链表；
- “分配”时，按当前“关键字位”所取值，将记 录分配到不同的“链队列”中，每个队列中记 录的“关键字位”相同；
- “收集”时，按当前关键字位取值从小到大将 各队列首尾相链成一个链表;
- 对每个关键字位均重复2)和3)两步。
链式基数排序分析
链式基数排序算法对数据进行d趟扫描，每趟需 时间O(n+j)。因此总的计算时间为O(d(n+j))。对 于不同的基数j所用的时间是不同的。当n较大或d 较小时，这种方法较为节省时间。 基数排序适用于链式存储结构的记录的排序，它要 求的附加存储量是j个队列的头、尾指针。所以， 需要O(n+j)辅助空间。 基数排序是一种稳定的排序方法。
外排序
如果待排序的记录数很大，无法将所有记录都装入内存，只能将它们 存放在外存上，我们称这时的排序为外排序。
外存信息的存取——磁带
磁带是涂上一层磁性材料的窄带，磁带 卷在带盘上，带盘安装在磁带驱动器的转轴上。驱动器控制磁带盘转动，带动磁带移动，通过读/写磁头进行读/写信息的操作。
磁盘存取信息时，首先要确定信息所在的柱面，再将磁头移动到所需磁道的位置上，移动磁 头所需的时间称为磁头定位时间或称为寻道时 间。然后等待磁道上的信息所在位置随着磁盘 的转动而转到磁头下面，这段时间称为等待时 间。由于磁盘高速运转（2400~3600转/分）， 所以，等待时间是极短的。磁盘的存取时间主 要花在磁头定位时间上。
外部排序的基本方法
外排序的基本方法是归并排序。由两个阶段组成：第一阶段，产生顺串。即把 要排序的元素分成若干组，把每一组装入内存，进行内排序，每一组经过内排序后 再写到外存上，我们把经过内排序的每一组叫一个顺串，这样在外存上就产生了许 多顺串。第二阶段，归并。可用两路或多路进行归并（可用三台磁带机或磁盘机实 现两路归并、也可用四台磁带机或磁盘机实现三路归并等），使顺串的长度逐渐由小至大，直至变成一个顺串（即使所有元素按关键码有序）为止。
外部排序的基本方法
一般可依据所使用的外存设备将外部排序分为磁盘文件排序和磁带文件排序。磁盘排序 和磁带排序基本相似，区别在于初始归并段在 外存储介质中的分布方式不同。磁盘是直接存 取设备，而磁带是顺序存储设备，读取信息块 的时间与所读信息块的位置关系极大。故在磁 带上进行文件排序时，研究归并段信息块的分 布是个极为重要的问题。
最简单的归并排序方法与内排序中的二路归并 类似。假设一具有n个记录的文件，先把该文件 看作是由n个长度为1的顺串组成，然后在此基 础上进行两两归并。经过log2n趟归并后，当文 件中只含有一个长度为n的顺串时，整个文件的 排序就完成了。在每一躺排序过程中都需要进 行记录的内、外存交换。
还有一种常用的外部排序方法是多路归并排序。由于 在外部排序过程中，数据的内外存交换所需的时间比 记录的内部归并所需的时间大得多，所以可以通过减 少数据内外存交换的次数来提高外部排序的效率。为了不增加内部归并时所需进行关键字比较的次数，在 具体实现时通常不用选择排序的方法，而用“败者树”来实现。
小结
各种内部排序方法性能比较
- 从平均时间而言：快速排序最佳。但在最坏情况下时间性能不如堆排序和归并排序。
- 从算法简单性看：由于直接选择排序、直接插入排序和冒泡排序的算法比较简单，将其认为是简单算法，都包含在上图中的“简单排序”中。对于希尔排序、堆排序、快速排序和归并排序算法，其算法比较复杂，认为是复杂排序。
- 从稳定性看：直接插入排序、冒泡排序和归并排序是稳定的；而希尔排序、直接选择排序、快速排序和堆排序是不稳定排序。
- 从待排序的记录数n的大小看，n较小时，宜采用简单排序；而n较大时宜采用 改进排序。
选择排序的方法
- 当待排序记录数n 较大时，若要求排序稳定， 则采用归并排序。
- 当待排序记录数n 较大，关键字分布随机，而 且不要求稳定时，可采用快速排序；
- 当待排序记录数n 较大，关键字会出现正、逆 序情形，可采用堆排序（或归并排序）。
- 当待排序记录数n 较小，记录已接近有序或随 机分布时，又要求排序稳定，可采用直接插入排序。
- 当待排序记录数n 较小，且对稳定性不作要求 时，可采用直接选择排序。