7.2 插入排序（p284）

7.2.1 直接插入排序（p284）

void InsertSort(ElemType A[], int n) {
//直接插入排序
    int i, j;
    for (i = 2; i <= n; i++)                    //依次将A[2]～A[n]插入到前面已排好的序列
        if (A[i].key < A[i - 1].key) {          //若A[i]的关键码小于其前驱，需将A[i]插入有序表
            A[0] = A[i];                        //复制为哨兵，A[0]不存放元素
            for (j = i - 1; A[0].key < A[j].key; --j)   //从后往前查找待插入位置
                A[j+1] = A[j];                  //向后挪位
            A[j + 1] = A[0];                    //复制到插入位置
        }
}

7.2.2 折半插入排序（p285）

void InsertSort(ElemType A[], int n) {
//折半插入排序
    int i, j, low, high, mid;
    for (i = 2; i <= n; i++) {                  //依次将A[2]～A[n]插入到前面已排序序列
        A[0] = A[i];                            //将A[i]暂存到A[0]
        low = 1; high = i - 1;                  //设置折半查找的范围
        while (low <= high) {                   //折半查找（默认递增有序）
            mid = (low + high) / 2;             //取中间点
            if (A[mid].key > A[0].key) high = mid - 1;  //查找左子表
            else low = mid + 1;                 //查找右子表
        }
        for (j = i - 1; j >= high + 1; --j)
            A[j + 1] = A[j];                    //统一后移元素，空出插入位置
        A[high + 1] = A[0];                     //插入操作
    }
}

7.2.3 希尔排序（p286）

void ShellSort(ElemType A[], int n) {
//希尔排序，对顺序表做希尔插入排序，比直接插入排序有如下修改
//1.前后记录的增量是dk，不是1
//2.r[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到
    int i, j, dk;                               //dk为步长
    for (dk = n / 2; dk >= 1; dk = dk / 2)      //步长变化
        for (i = dk + 1; i <= n; ++i)
            if (A[i].key < A[i - dk].key) {     //需将A[i]插入有序增量子表
                A[0] = A[i];                    //暂存在A[0]
                for (j = i - dk; j > 0 && A[0].key < A[j].key; j -= dk)
                    A[j + dk] = A[j];           //记录后移，查找插入的位置
                A[j + dk] = A[j];               //插入
            }//if
}

7.3 交换排序（p290）

7.3.1 冒泡排序（p290）

void BubbleSort(ElemType A[], int n) {
//用冒泡排序法将序列A中的元素按从小到大排列
    bool flag;
    for (int i = 0; i < n - 1; i++) {
        flag = false;                //表示本趟冒泡是否发生交换的标志
        for (int j = n - 1; j > i; j--)    //一趟冒泡过程
            if (A[j - 1].key > A[j].key) {    //若为逆序
                swap(A[j - 1], A[j]);    //交换
                flag = true;
            }
        if (flag == true)
            return;                //本趟遍历后没有发生交换，说明表已经有序
    }
}

7.3.2 快速排序（p291）

void QuickSort(ElemType A[], int low, int high) {
//快速排序
    if (low < high) {                           //递归跳出的条件
    //Partition()就是划分操作，将表A[low...high]划分为满足上述条件的两个子表
        int pivotpos = Partition(A, low, high); //划分
        QuickSort(A, low, pivotpos - 1);        //依次对两个子表进行递归排序
        QuickSort(A, pivotpos + 1, high);
    }
}
int Partition(ElemType A[], int low, int high) {
//严版教材中的划分算法（一趟排序过程）
    ElemType pivot = A[low];                    //将当前表中第一个元素设为枢轴值，对表进行划分
    while (low < high) {                        //循环跳出条件
        while (low < high && A[high] >= pivot)
            --high;
        A[low] = A[high];                       //将比枢轴值小的元素移动到左端
        while (low < high && A[low] <= pivot)
            ++low;
        A[high] = A[low];                       //将比枢轴值大的元素移动到右端
    }
    A[low] = pivot;                             //枢轴元素存放到最终位置
    return low;                                 //返回存放枢轴元素的位置
}

7.4 选择排序（p300）

7.4.1 简单选择排序（p300）

void SelectSort(ElemType A[], int n) {
//对表A进行简单的选择排序，A[]从0开始存放元素
    for (int i = 0; i < n - 1; i++) {           //一共进行n-1趟
        int min = i;                            //记录最小元素位置
        for (int j = i + 1; j < n; j++)         //在A[1...n-1]中选择最小的元素
            if (A[j] < A[min]) min = j;         //更新最小元素的位置
        if (min != i) swap(A[i], A[min]);       //与第i个位置互换
    }
}

7.4.2 堆排序（p301）

建立大根堆
void BuildMaxHeap(ElemType A[], int len) {
    //建立大根堆
    for (int i = len / 2; i > 0; i--)           //从i=[n/2]～1，反复调整堆
        AdjustDown(A, i, len);
}
void AdjustDown(ElemType A[], int k, int len) {
//函数AdjustDown将元素k向下进行调整
    A[0] = A[k];                                //A[0]暂存
    for (int i = 2 * k; i <= len; i *= 2) {     //沿key较大的子结点向下筛选
        if (i < len && A[i] < A[i + 1])
            i++;                                //取key较大的子结点的下标
        if (A[0] >= A[i]) break;                //筛选结束
        else {
            A[k] = A[i];                        //将A[i]调整到双亲结点上
            k = i;                              //修改k值，以便继续向下筛选
        }
    }//for
    A[k] = A[0];                                //被筛选结点的值放入最终位置
}
堆排序算法
void HeapSort(ElemType A[], int len) {
    //堆排序
    BuildMaxHeap(A, len);                       //建立初始堆
    for (int i = len; i > 1; i--) {             //n-1趟的交换和建堆过程
        swap(A[i], A[1]);                       //输出堆顶的元素（和堆底元素交换）
        AdjustDown(A, 1, i - 1);                //整理，把剩余的i-1个元素整理成堆
    }
}
向上调整堆的算法
void AdjustUp(ElemType A[], int k) {
//参数k为向上调整的结点，也为堆的元素个数
    A[0] = A[k];
    int i = k / 2;                      //若结点值大于双亲结点,则将双亲结点下调，并继续向上比较
    while (i > 0 && A[i] < A[0]) {      //循环退出条件
        A[k] = A[i];                    //双亲结点下调
        k = i;
        i = k / 2;                      //继续向上比较
    }//while
    A[k] = A[0];                        //复制到最终位置
}

7.5 归并排序和基数排序（p308）

7.5.1 归并排序（p308）

ElemType *B=(ElemType *)malloc((n+1)*sizeof(ElemType));    //辅助数组B
void Merge(ElemType A[],int low,int mid,int high){
    //表A的两端A[low...mid]和A[mid+1...high]各自有序，将它们合并成一个有序表
    for(int k=low;k<=high;k++)
    B[k]=A[k];              //将A中所有元素复制到B中
    for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
    if(B[i]<=B[j])        //比较B的左右两段中的元素
        A[k]=B[i++];    //将较小值复制到A中
    else
        A[k]=B[j++];
    }//for
    while(i<=mid)
        A[k++]=B[i++];        //若第一个表未检测完，复制
    while(j<=high)
        A[k++]=B[j++];        //若第二个表未检测完，复制
}
void MergeSort(ElemType A[],int low,int high){
    if(low < high){
        int mid=(low+high)/2;    //从中间划分两个子序列
    MergeSort(A,low,mid);    //对左侧子序列进行递归排序
        MergeSort(A,mid+1,high);//对右侧子序列进行递归排序
    Merge(A,low,mid,high);    //归并
    }//if
}