第十章
内部排序(在内存中进行的排序不需要访问外存的)外部排序(排序量很大，通过分批的读写外存，最终完成排序)
稳定排序和非稳定排序：看相同记录的相对次序是否回发生改变。主要看在排序过程中的比较是不是相邻记录，如果是相邻比较，一定是稳定的排序。如果不是相邻的比较，就是不稳定的。
内排序方法 截止目前，各种内排序方法可归纳为以下五类：
(1)插入排序;(2)交换排序;(3)选择排序;(4)归并排序; (5)基数排序。
插入排序：包括直接插入排序和希尔排序
直接插入排序：(稳定的)
算法描述
void Insort (sqList &L) ∥对顺序文件F直接插入排序的算法∥
{ int i,j;
for (i=2;i<=L.len;i++) ∥插入n-1个记录∥
{
if(L.R[i].key
{ L.R[0]=L.R[i]; ∥待插入记录先存于监视哨∥
L.R[i]=L.R[i-1];
for(j=i-2;L.R[0].key
L.R[j+1]=L.R[j]; ∥记录顺序后移∥
L.R[j+1]=L.R[0]; ∥原R[i]插入j+1位置∥
}
}
}
算法分析
设排序中key比较次数为C，C最小时记为Cmin，最大时记为Cmax。
(1)当原来就有序(正序)时，每插入一个R[i]只需比较key一次，即：
(2)当原本逆序(key从大到小)时，每插入一个R[i]要和子表中i-1个key比较，加上同自身R[0]的比较，此时比较次数最多，即：
(3)记录总的移动次数m(m最小时记为mmin，最大时记为mmax)
正序时，子表中记录的移动免去，即：
逆序时，插入R[i]牵涉移动整个子表。移动次数为2+(i-1)=i+1，此时表的移动次数最大，即：
排序的时间复杂度取耗时最高的量级，故直接插入排序的T(n)=O(n2)。
Shell(希尔)排序又称“缩小增量”排序(不稳定的)
交换类的排序：(起泡排序和快速排序)
起泡排序算法描述
void Bubsort (sqList &L)
{ int i,flag; ∥flag为记录交换的标记∥
Retype temp;
for (i=L.len;i>=2;i--) ∥最多n-1趟排序∥
{ flag=0; //记录每一趟是否发生了交换
for (j=1;j<=i-1;j++) ∥一趟的起泡排序∥
if (L.R[j].key>L.R[j+1].key) ∥两两比较∥
{ temp=L.R[j]; ∥R[j] Û R[j+1]∥
L.R[j]=L.R[j+1];
L.R[j+1]=temp;
flag=1;
}
if (flag==0) break; ∥无记录交换时排序完毕∥
}
}
算法分析
设待排长度为n，算法中总的key比较次数为C。若正序，第一趟就无记录交换，退出循环，Cmin=n-1=O(n);若逆序，则需n-1趟排序，每趟key的比较次数为i-1(2≤i≤n)，故：
同理，记录的最大移动次数为：
故起泡排序的时间复杂度T(n)=O(n2)。并且是稳定的。
快速排序：(不稳定的，时间复杂度O(nlogn))，不需要辅助空间，但有最好和最差之分
分割算法
int Partition(Sqlist&L,int low,int high)
{ L.R[0]=L.R[low];
pivotkey=L.R[low].key;
while(low
{ while(low=pivotkey)
--high;
L.R[low]=L.R[high];
while(low
++low;
L.R[high]= L.R[low];
}
return low;
}
总控函数：
void QSort(Sqlist&L,int low,int high)
{ if(low
{
pivotloc=Partition(L,low,high);
QSort(L,low,pivotloc-1);
QSort(L,pivotloc+1,high);
}
}
调用方法：QSort(L,1,L,lenght);
考研有疑问、不知道如何总结考研考点内容、不清楚考研报名当地政策，点击底部咨询官网，免费领取复习资料：
https://www.87dh.com/xl/