交换排序算法：
1. 冒泡排序
    [算法思想]：将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。

    [算法]：
    void BubbleSort(SeqList R) {
    //R（l..n)是待排序的文件，采用自下向上扫描，对R做冒泡排序
        int i，j；
        Boolean exchange； //交换标志
        for(i=1;i<n;i++){ //最多做n-1趟排序
            exchange=FALSE； //本趟排序开始前，交换标志应为假
            for(j=n-1;j>=i；j--) //对当前无序区R[i..n]自下向上扫描
                if(R[j+1].key<R[j].key){//交换记录
                    R[0]=R[j+1]； //R[0]不是哨兵，仅做暂存单元
                    R[j+1]=R[j]；
                    R[j]=R[0]；
                    exchange=TRUE； //发生了交换，故将交换标志置为真
                }
            if(!exchange) return；//本趟排序未发生交换，提前终止算法
        } //endfor(外循环)
    } //BubbleSort

    [分析]：起泡排序的结束条件为：最后一趟没有进行“交换”。从起泡排序的过程可见，起泡排序是一个增加有序序列长度的过程，也是一个缩小无序序列长度的过程，每经过一趟起泡，无序序列的长度只缩小1。


2. 快速排序(Quick Sort)是对起泡排序的一种改进。
    [基本思想]：是通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

    [一趟快速排序]：找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序列R[s..t]将分割成两部分：R[s..i-1]和R[i+1..t],且 R[j].key≤ R[i].key ≤ R[j].key(s≤j≤i-1) 枢轴 (i+1≤j≤t) 其算法如算法9.6(a)所示。

    int Partition(SqList &L， int low， int high) {
    //交换顺序表L中子表L.r[low..high]的记录
    //使枢轴记录到位，并返回其所在位置，此时在它之前(后)的记录均不大(小)于它。
        pivotkey = L.r[low].key； //用子表的第一个记录作枢轴记录
        while(1ow<high){ //从表的两端交替地向中间扫描
            while(low<high&&L.r[high].key>pivotkey)
                --high;
            L.r[1ow] L.r[high]； //将比枢轴记录小的记录交换到低端
            while(low<high&&L.r[low].key<pivotkey)
                ++low;
            L.r[low] L.r[high]； //将比枢轴记录大的记录交换到高端
            }
        return low; //返回枢轴所在位置
    }//partition
    算法9.6(a)

    改写上述算法，先将枢轴记录暂存在r[0]的位置上，排序过程中只作r[low]或r[high]的单向移动，直至一趟排序结束后再将枢轴记录移至正确位置上。
    int Partition(SqList &L，int low，int high){
    //交换顺序表L中子表r[low．．high]的记录
    //枢轴记录到位，并返回其所在位置，此时在它之前(后)的记录均不大(小)于它。
        L.r[0]=L.r[low]； //用子表的第一个记录作枢轴记录
        pivotkey=L.r[low].key； //枢轴记录关键字
        while(low<high){ //从表的两端交替地向中间扫描
            while(1ow<high&&L.r[high].key>pivotkey) --high;
            L.r[low]=L.r[high]; //将比枢轴记录小的记录移到低端 low
            while(low<high&& L.r[low].key<pivotkey)++low;
            L.r[high]=L.r[low]; //将比枢轴记录大的记录移到高端
            }
        L.r[low]=L.r[0]; //枢轴记录到位
        return low； //返回枢轴位置
    }//Partition

    [算法]：
    递归形式的快速排序算法如算法9.7和算法9.8所示。
    void QSort(SqList &L，int low，int high){ //对顺序表l中的子序列L.r[low．．high]作快速排序
        if(low<high){ //长度大于1
            pivotloc = Partition(L，low，high); //将L.r[low..high]一分为二
            QSort(L，low，pivotloc-1); //对低子表递归排序
            QSort(L，pivotloc+1，high)； //对高于表递归排序
    }}//QSort
    算法9.7

    void QuickSort(SqList &L){ //对顺序表L作快速排序
        QSort(L，1，L.length)；
    }//QuickSort

插入排序算法：
1. 直接插入排序。

    [思想]：基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。

    [算法]：void InsertSort (SqList&L){ //对顺序表L作直接插入排序。
        for(i=2；i<=L.1ength；++i)
            if LT(L.r[i].key，L.r[i-1].key){ //“<”，需将L.r[i]插入有序子表
                L.r[0]=L.r[i] //复制为哨兵
            for( j=i-1 ; LT(L.r[0].key，L.r[j].key); --i)
                L.r[j+1]=L.r[j]； //记录后移
            L.r[j+1]=L.r[0] // 插入到正确位置
            }
      }//Insertsort
    算法 9.1


2. 折半插入排序
    [思想]：因为R[1..i-1]是一个按关键字有序的有序序列，则可以利用折半查找实现“在R[1..i-1]中查找R[i]的插入位置”，如此实现的插入排序为折半插入排序。

    [算法]：
    void BInsertSort (SqList &L){ //对顺序表L作折半插入排序。
        for(i=2；i<L.1ength；++i){
            L.r[0]=L.r[i] //L.r[i]暂存到L.r[0]
            low=1; high=i-1; //在r[low..high]中折半查找有序插入的位置
            while(low<=high ){
                m=(low+high)/2 //折半
                if LT(L.r[0].key , L.r[m].key) high=m-1； //插入点在低半区
                else low=m+1; //插入点在高半区
            }//while
            for (j=i-1; j>=high+1; --j) L.r[j+1]=L.r[j]; //记录后移
            L.r[high+1]=L.r[0]; //插入
        }//for
    }//BInsertSort
    算法9.2

    [分析]：折半插入排序比直接插入排序明显地减少了关键字间的“比较”次数，但记录“移动”的次数不变。


3. 希儿排序。
    [基本思想]：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

    [算法]：
    void ShellInsert (SqList &L，int dk) {
    //对顺序表L作一趟希尔插入排序。本算法是和一趟直接插入排序相比，作了以下修改：
    //1、前后记录位置的增量是dk，而不是1；
    //2、r[0]只是暂存单元，不是哨兵。当j<=0时，插入位置已找到。
        for (i=dk+1；i<=L.1ength；++i)
            if LT(L.r[i].key，L.r[i-dk].key){ //需将L.r[i]插入有序增量子表
                L.r[0]=L.r[i]； //暂存在L.r[0]
                for(j=i-dk； j>0&&LT(L.r[0].key，L.r[j].key)； j-=dk)
                    L.r[j+dk]=L.r[j] //记录后移，查找插入位置
                L.r[j+dk]=L.r[0]； //插入
            }//if
    }//ShellInsert
    算法9.4

    void ShellSort (Sqlist &L，int dlta[]，int t){ //按增量序列dlta[0..t-1]对顺序表L作希尔排序。
        for(k=0；k<t；++t)
            ShellInsert(L，dlta[k])； //一趟增量为dlta[k]的插入排序
    }//ShellSort

选择排序算法：
1. 简单选择排序。
    [思想]：一趟简单选择排序的操作为：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第(1≤i≤n)个记录交换之。显然，对L.r[1..n]中记录进行简单选择排序的算法为：令i从1至n-1，进行n- 1趟选择操作，如算法9.9所示。

    [算法]：
    void SelectSort (SqList &L){ //对顺序表L作简单选择排序。
        for(i=1;i<L.1ength；++i) { //选择第i小的记录，并交换到位
            j=SelectMinKey(L，i)；//在L.r[i..L.1ength]中选择key最小的记录
            if(i!=j) L.r[i] L.r[j]； //与第i个记录交换
        }
    } //算法9.9

2. 树形选择排序(TreeSelectionSort)，又称锦标赛排序(TournamentSort)，是一种按照锦标赛的思想进行选择排序的方法。首先对n个记录的关键字进行两两比较，然后在其中ceil(n/2)个较小者之间再进行两两比较，如此重复，直至选出最小关键字的记录为止。这个过程可用一棵有n个叶子结点的完全二叉树表示。


3. 堆排序的算法。
    [思想]：堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。

    具体作法是：
    ① 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区
    ② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key
    ③ 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。
    ……
    直到无序区只有一个元素为止。

    所谓“筛选”就象过筛子一样，把较小的关键字逐层筛下去，而将较大的关键字逐层选上来。具体指的是对一棵左/右子树均为堆的完全二叉树，“调整”根结点使整个二叉树为堆。筛选的算法如算法9.10所示。
 
    [算法]：
    void HeapAdjust(SqList ＆H， int s， int m) {
    //已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义，
    //本函数调整H.r[s]的关键字，使H.r[s..m]成为一个大顶堆
        rc = H.r[s];
        for (j=2*s; j<=m; j*=2) { //沿key较大的孩子结点向下筛选,j为key较大的记录的下标
            if(j<m&&LT(H.r[j].key, H.r[j+1].key)) ++j;
            if(!LT(rc.key，H.r[j].key)) break; //rc应插入在位置s上
            H.r[s]=H.r[j]； s=j；
            }
        H.r[s] = rc; //插入
    }//HeapAdjust
    算法9.10

    void HeapSort (HeapType &H){ //对顺序表H进行堆排序。
        for(i=H.1ength/2; i>0; --i) //把H.r[1.. length]建成大顶堆
        HeapAdjust(H，i，H.length);
        for(i=H.length；i>1; --i){
            H.r[1] H.r[i]； //将堆顶记录和当前未经排序子序列Hr.[1..i]中最后一个记录相互交换
            HeapAdjust(H, 1, i-1 ); //将H.R[1..i-1]重新调整为大顶堆
            }
    }//HeapSort

归并排序算法：

    归并排序(Merging Sort)是又一类不同的排序方法。“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。它的实现方法早巳为读者所熟悉，无论是顺序存储结构还是链表存储结构，都可在O(m+n)的时间量级上实现。利用归并的思想容易实现排序。

    在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的有序子序列归并为一个有序序列。

    [思想]：假设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n/2]个长度为2或1的有序子序列；再两两归并，……，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2-路归并排序。

    图为2-路归并排序的一个例子。
        
    [算法]：2-路归并排序中的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列，其算法(类似于算法2.7)如算法10.12所示。
    void Merge(RcdType SR[ ]，RcdType &TR[ ]，int i，int m，int n){
    //将有序的SR[i..m]和SR[i+1..n]归并为有序的TR[i..n]
      for(j=m+1，k=i; i<=m && j<=n；++k){ //将SR中记录由小到大地并入TR
        if LQ(SR[i].key，SR[j].key) TR[k]=SR[i++];
        else TR[k]=SR[j++]; }
      if (i<=m) TR[k..n]=SR[i..m]; // 将剩余的SR[i..m]复制到TR
      if (j<=n) TR[k..n]=SR[j..n]; // 将剩余的SR[j..n]复制到TR
    }//merge

1. 多关键字的排序。
    [思想]：
    最高位优先MSD法：先对K0进行排序，并按K0的不同值将记录序列分成若干子序列之后，分别对K1进行排序，…，依次类推，直至最后对最次位关键字排序完成为止。

    最低位优先LSD法：先对Kd-1进行排序，然后对Kd-2进行排序，依次类推，直至对最主位关键字K0排序完成为止。排序过程中不需要根据“前一个”关键字的排序结果，将记录序列分割成若干个(“前一个”关键字不同的)子序列。




    [算法]：
    void SelectSort (SqList &L){ //对顺序表L作简单选择排序。
        for(i=1;i<L.1ength；++i) { //选择第i小的记录，并交换到位
            j=SelectMinKey(L，i)；//在L.r[i..L.1ength]中选择key最小的记录
            if(i!=j) L.r[i]L.r[j]； //与第i个记录交换
        }
    } //算法9.9

2. 链式基数排序
    [思想]：在计算机上实现基数排序时，为减少所需辅助存储空间，应采用链表作存储结构，即链式基数排序，具体作法为：
    1. 待排序记录以指针相链，构成一个链表；
    2. “分配”时，按当前“关键字位”所取值，将记录分配到不同的“链队列”中，每个队列中记录的“关键字位”相同；
    3. “收集”时，按当前关键字位取值从小到大将各队列首尾相链成一个链表;
    4. 对每个关键字位均重复2)和3)两步。

    [提醒注意]：
    1. “分配”和“收集”的实际操作仅为修改链表中的指针和设置队列的头、尾指针；
    2. 为查找使用，该链表尚需应用算法Arrange将它调整为有序表。