基本概念
排序：将一组无序的数据元素按其关键字的非递减（或非递增）次序排列成有序序列。
稳定：相同的元素在排序前后的相对位置不发生改变。
不稳定：相同的元素在排序前后的相对位置发生改变。
内部排序：将排序记录序列全部读入内存中处理。
外部排序：仅有部分记录在内存中，还要对外村中的记录进行访问。
评价算法的效率主要有两条：
（1）时间开销，主要消耗在元素之间的比较和记录的移动上。
（2）存储空间
插入排序
基本思想：将第一个记录看作一个有序序列，然后每次将下一个待排序的记录有序插入已排好的有序序列中，使有序序列逐渐扩大，直至所有记录都加到有序序列中。
本文主要介绍三种：直接插入排序、折半插入、希尔排序
直接插入排序
记录序列为R[0…n-1]，首先将第一个记录R[0]看作一个有序子序列，然后依次将记录R[i]插入有序子序列R[0…i-1]中，使记录的有序子序列从R[0…i-1]变为R[0…i]
例：8个待排序记录，{36,80,45,66,22,9,16,36}
template <class Type>
void straightInsertSort(Type R[], int size){
int pos,j; //pos为待插入记录位置
Type tmp;
for(pos=1;pos<size;pos++){ //取初始序列的元素
tmp=R[pos]; //将待插入记录放进临时变量中
for(j=pos-1; tmp<R[j]&&j>=0; j--) //在有序序列中，从后向前查找插入位置
R[j+1]=R[j]; //将大于待插入记录向后移动
R[j+1]=tmp; //待插入记录放到合适位置
}
}
直接插入是一种稳定排序。
基本操作有两种：比较关键字和移动记录
平均时间复杂度O(n2), 空间复杂度O(1)
折半插入排序
对直接插入排序算法进行改进，可以从减少比较和移动次数这两个方面入手。
当前面i-1个有序记录序列时，要插入第i个记录，可以利用折半查找方式确定插入位置。
template <class Type>
void binaryInsertSort(Type R[],int size){
int pos, j, low, high, mid;
Type tmp;
for(pos=1;pos<size;high=pos-1;){ //假定第一个记录有序
tmp=R[pos]; //将待排序记录R[pos]暂存到tmp中
low=0;
high=pos-1; //设置折半查找的范围
while(low<=high){ //在R[low...high]中折半查找有序插入位置
mid=(low+high)/2; //计算中间位置
if(tmp<R[mid]) high=mid-1; //插入点在低半区
else low=mid+1; //插入区在高半区
}
for(j=pos-1;j>=low;j==)
R[j+1]=R[j]; //记录后移
R[low]=tmp; //插入待排序记录
}
}
折半插入排序减少了关键字间的比较次数，但记录移动的次数不变，时间复杂度为O(n2)
希尔排序
又称为缩小增量排序。
对“减少记录个数”和“基本有序”两方面对直接插入排序进行了排序。
基本思想：将待排序的记录划分成几组，间距相同的记录分在一个组中，对各组分别实施直接插入排序。当经过几次分组排序后，记录的排序已经基本有序，再对所有的记录试试最后的直接插入排序。
template <class Type>
void shellSort(Type R[], int size){
int gap, pos, j;
Type tmp;
for(gap=size/2;gap>0;gap/=2){ //gap为希尔增量，即步长
for(pos=gap;pos<size;pos++){ //pos为待插入记录位置
tmp=R[pos];
for(j=pos-gap;j>=0&&R[j]>tmp;j-=gap)
R[j+gap]=R[j]; //记录后移
R[j+gap]=tmp; //将待插入记录放到合适位置
}
}
}
希尔排序适用于待排序的记录数量较大的情况，是一种不稳定的排序方法。
其时间性能与选定的增量序列有关，时间复杂度约O(n1.3)，空间复杂度O(1)。
交换排序
冒泡排序
基本思想：对所有相邻的关键字进行比较，若发现记录逆序，则交换。
template <class Type>
void bubbleSort(Type R[], int size){
int i,j ;
bool flag=true; //记录一趟排序后是否发生过交换
for(i=1;i<size&&flag;++i){
flag=false; //假定本次排序没有交换
for(j=0;j<size-i;++j)
if(R[j+1]<R[j]) { //逆序
swap(R[j],R[j+1]) //调用STL中的swap进行交换
flag=true;
}
}
}
冒泡排序是一种稳定的排序方法，关键字的比较次数和记录的交换次数的初始顺序有关。
平均时间复杂度为O(n2),空间复杂度为O(1).
快速排序
又称为分区交换排序，是对，冒泡排序的改进
基本思想：
（1）在序列中选取一个记录作为枢轴，并以该记录的关键字为基准。
（2）凡是关键字小于枢轴记录的均移动值枢轴之前，凡是关键字大于枢轴记录的均移动值枢轴之后。一趟排序后，记录序列分为两个子序列L和R，使得L中所有记录的关键字都小于等于key，R中均大于key,枢轴位于二者之间，且刚好在最终位置上。
（3）对子序列L和R进行快速排序。
一趟快速排序的具体做法：
（1）设置两个指针low和high分别用来指示将要与枢轴进行比较的左侧记录和右侧记录。
（2）先从high所指位置开始向前查找关键字小于枢轴关键字的记录，将其与之交换，再从low所指位置开始向后查找关键字大于枢轴关键字的记录，将其与之交换。重复上述步骤直到low与high相等。
一次划分后，枢轴两侧记录数量越接近，排序速度将越块。
以最左侧记录作为枢轴的快速排序：
template <class Type>
int partition(Type S[], int low, int high){
Type tmp=S[low]; //暂存枢轴
while(low!=high){ //开始分割
while(low<high&&S[high]>=tmp) high--; //大下标端小于枢轴的记录
if(low<high) {S[low]=S[high]; low++;} //记录移动到小下标端
while(low<high&&S[low]<=tmp) low++; //小下标端大于枢轴的记录
if(low<high) {S[high]=S[low]; high--;} //记录移动到大下标端
}
S[low]=tmp; //把枢轴回填到分界位置上
return low; //返回枢轴位置
}
递归快速排序
template <class Type>
void quickSort(Type S[], int low, int high){
int pivot;
if(low>=high) return;
pivot=partition(S,low,high); //一次划分，返回枢轴位置
quickSort(S,low,pivot-1); //枢轴左边一半快速排序
quickSort(S,pivot+1,high); //枢轴右边一半快速排序
}
快速排序的接口函数
template <class Type>
void quickSort(Type S[], int size){ //待排序序列，序列大小
quickSort(S,0,size-1);
}
快速排序的平均时间复杂度为O(nlogn)，就平均时间而言，是被认为目前最好的内部排序算法。
是一种不稳定的算法，适用于较多且基本无序的情况。
选择排序
基本思想：
依次将待排序记录中选出关键字最小（或最大）的记录、关键字次之的记录…并分别将它们定位到序列左侧（或右侧）的第1个位置、第2个位置…。直至序列中只剩下一个最小（或最大）的记录位置。
本文介绍两种选择排序方法：直接选择排序、堆排序
直接选择排序
基本思想：第1趟从n个记录中选取关键字最小的记录与第1个记录互换；第2趟从剩余的n-1个记录中选取关键字最小的记录与第2个记录互换…第i趟从剩余的n-i+1个记录中选取关键字最小的记录与第i个记录互换.
template <class Type>
void straightSelectSort(Type R[],int size){
int pos, min, j; //min为一趟排序中最小记录的下标
for(pos=0;pos<size-1;pos++){ //pos为待存放当前最小记录的位置
min=pos;
for(j=pos+1;j<size;++j)
if(R[j]<R[min]) //查找最小记录
min=j;
if(pos!=min) //调用STL中的swap，头文件algorithm
swap(R[pos],R[min]); //把无序序列中的最小值换到前面有序序列中
}
}
直接排序是一种不稳定的排序方法。
关键字的比较次数和记录的顺序无关。
平均时间复杂度O(n2)，空间复杂度O(1)
堆排序
基本思想：
（1）由存储于数组的序列，建成一个大根堆（或小根堆）
（2）将堆顶的最大（或最小）记录与序列中最后一个记录交换，最大（或最小）记录存放在数组末尾的有序段中。
（3）将序列中除末尾的有序段之外的剩余记录重新调整为堆。
（4）重复步骤三四共n-1次，若初始建立的是大根堆，则得到一个非递减序列；若建立的是小根堆，则得到一个非递增序列。
向下调整堆：
template <class Type>
void siftDown(Type R[], int pos, int size){ //待排序序列，要调整的结点编号，序列大小
int child;
Type tmp=R[pos]; //暂存“根”记录
for(;pos*2+1<size;pos=child){
child=pos*2+1;
if(child!=size-1 && R[child+1]>R[child])
child++; //选取两个孩子的大者
if(R[child]>tmp) //较大的孩子比双亲大
R[pos]=R[child];
else
break;
}
R[pos]=tmp; //被调整结点放入正确位置
}
堆排序：
template <class Type>
void headSort(Type R[], int size){
int i;
for(i=size/2-1; i>=0; i--) //初始建堆，从最后一个非叶结点开始调整堆
siftDown(R,i,size);
for(i=size-1; i>0; i--){ //共size-1趟排序（删除堆顶元素后反复调整堆）
swap(R[0],R[i]); //堆顶元素与子序列中最后一个元素交换
siftDown(R,0,i); //将R[0..i]重新调整为大根堆
}
}
堆排序过程中存在大幅度的数据移动，是一种不稳定的排序方法
时间复杂度为O(nlogn)，空间复杂度O(1)
快速排序和堆排序经常用于排在前面的若干最大（或最小）记录
归并排序
归并是指将两个或两个以上的有序表合并成一个新的有序表。
在内部排序中，采用的是2-路归并排序。
2-路归并排序的基本思想：
将一个具有n个待排序记录的序列看成n个长度为1的有序序列，然后将相邻的子序列进行两两归并，得到[n/2]个长度为2的有序子序列，继续对相邻子序列进行两两合并。得到[n/4]个长度为4的有序子序列.重复此过程，直到得到一个长度为n的有序序列为止。
归并相邻两个有序子序列。将有序序列R[low…mid-1]和R[mid…high]归并为有序序列R[low…high]:
template <class Type>
void merge(Type R[], Type tmp[], int low,int mid,int high){
int i=low, j=mid,k=0;
while(i<mid && j<=high) //R中记录由小到大复制到tmp中
if(R[i]<R[j]) tmp[k++]=R[i++]; //将R[i]和R[j]中的小者复制到tmp[k]中
else tmp[k++]=R[j++];
while(i<mid) tmp[k++]=R[i++]; //将剩余的R[i...mid-1]复制到tmp中
while(j<=high) tmp[k++]=R[j++]; //将剩余的R[j...high]复制到tmp中
for(i=0,k=low;k<=high;)
R[k++]=tmp[i++]; //排好序的记录由tmp复制回R中
}
递归2-路归并排序。
通过递归调用实现对子序列R[low…high]的排序过程，将其归并为有序段。
template <class Type>
void mergeSort(Type R[],Type tmp[],int low, int high){
if(low==high) return;
int mid=(low+high)/2;
mergeSort(R,tmp,low,mid);
mergeSort(R,tmp,mid+1,high); //递归地对子序列R[mid+1...high]进行归并排序
merge(R,tmp,low,mid+1,high); //归并两个子序列
}
2-路归并排序的接口函数
template <class Type>
void mergeSort(Type R[], int size){
Type *tmp=new Type[size]; //辅助数组
mergeSort(R,tmp,0,size-1);
delete [] tmp;
}
归并排序是一种稳定的排序方法。
时间复杂度O(nlogn),空间复杂度O(n)
各内部排序方法的比较
习题（含408真题）
1.【408】下列选项中，不可能是快速排序第2趟排序结果是（）
A.2,3,5,4,6,7,9
B.2,7,5,6,4,3,9
C.3,2,5,4,7,6,9
D.4,2,3,5,7,6,9
每趟快速排序后，至少一个记录找到最终位置。选C
2.【408】数据元素序列11,12,13,7,8,9,12,4,5,是采用下列排序方法之一得到的第2趟排序后的结果，该算法只能是（）
A.冒泡排序
B.插入排序
C.选择排序
D.2-路归并排序
冒泡排序在第2趟至少排好了前两个最大值
选择排序在第2趟至少排好了前两个最小值
2-路归并排序的子序列应该是有序的，找不到这种有序的子序列。
选B.
3.下面4种排序方法中，排序过程中的比较次数与排序方法无关的是（）
A.选择排序法
B.插入排序法
C.快速排序法
D.堆排序法
选A
4.分别采用堆排序、快速排序、冒泡排序和归并排序，对初态为有序的表，则最省时间的是（），最费时间的是（）
冒泡排序；快速排序