#define MAXSIZE 20    //设记录不超过20个
typedef int KeyType;    //设关键字为整型量（int型）

Typedef struct{        //定义每个记录（数据元素）的结构
    KeyType key;        //关键字
    InfoType otherinfo;    //其它数据项
}RedType;

Typedef struct{                //定义顺序表的结构
    RedType r[MAXSIZE+1];    //存储顺序表的向量    r[0]一般作哨兵或缓冲区
    int length;                //顺序表的长度
}SqList;

插入排序

直接插入排序

①复制插入元素

②记录后移，查找插入位置

③插入到正确位置

带哨兵的情况

1.复制为哨兵 L.r[o] = L.r[i]

2. 记录后移，查找插入位置

3.哨兵的元素插入到正确位置

void InsertSort(SqList &L){
    int i,j;
    for(i=2;i<=L.length;++i){
        if(L.r[i].key < L.r[i-1].key){    //若“<”，需将L.r[i]插入有序子表
            L.r[0] = L.r[i];            //复制为哨兵
            for(j=i-1;L.r[0].key < L.r[j].key;--j){
                L.r[j+1] = L.r[j];        //记录后移
            }
            L.r[j+1] = L.r[0];            //插入到正确位置
        }
    }
}

算法特点

①稳定排序

②算法简单，且容易实现

③适用于链式存储结构，只是在单链表上无需移动记录，只需修改相应的指针

④更适合于初始记录基本有序的情况，当初始记录无序，n较大时，此算法时间复杂度较高

折半插入排序

void BInsertSort(SqList &L){
    for(i=2;i <= L.length;++i){    //依次插入第2-第n个元素
        L.r[0] = L.r[i];    //当前插入元素存到“哨兵”位置
        low = 1;high = i-1;    //采用二分查找法查找插入位置
        while(low <= high){
            mid = (low+high)/2;
            if(L.r[0].key < L.r[mid].key)    high = mid-1;
            else low = mid+1;
        }
        for(j=i-1;j >= high+1;--j)    L.r[j+1] = L.r[j];    //移动元素
        L.r[high+1] = L.r[0];
    }
}

折半查找比顺序查找块，所以折半插入排序就平均性能来说比直接插入排序要快

折半插入排序的对象移动次数与直接插入排序相同，依赖于对象的初始排列

①减少了比较次数，但没有减少移动次数

②平均性能优于直接插入排序

时间复杂度为O(n^2) 空间复杂度为O(1) 稳定的排序方法

算法排序

①稳定排序

②因为要进行折半查找，所以只能用于顺序结构，不能用于链式结构

③适合初始记录无序、n较大时的情况

希尔排序

基本思想：先把整个待排序列分割成若干子序列，分别进行直接插入排序，待整个系列中的记录“基本有序”时，再对全体记录进行一次直接插入排序

void ShellInsert(SqList &L,int dk){
    //对顺序表L做一趟增量是dk的希尔插入排序
    for(i=dk+1;i <= L.length;++i)
        if(r[i].key < r[i-dk].key){
            r[0] = r[i];
            for(j=i-dk;j>0&&(r[0].key<r[j].key);j=j-dk)
                r[j+dk]=r[j];        //记录后移
            r[j+dk]=r[0];            //将r[0]即原r[i],插入到正确位置
        }
}

void ShellSort(SqList &L,int dt[];int t){    //增量dk存放在dt[]数组中
    for(k=0;k<t;++k)
        ShellInsert(L.dt[k]);    //一趟增量为dt[t]的希尔插入排序
}

时间复杂度为O(n^1.3) 空间复杂度为O(1)

算法特点

①记录跳跃式地移动导致排序方法是不稳定的

②只能用于顺序结构，不能用于链式结构

③增量序列可以有各种取法，但应该使增量序列中的值没有除1之外的公因子，并且最后一个增量值必须等于1

④记录总的比较次数和移动次数都比直接插入排序要少，n越大时，效果越明显。所以适合初始记录无序，n较大时的情况

交换排序

冒泡排序

n个元素总共需要n-1趟

第m趟需要比较n-m次

void bubble_sort(SqList &L){    //冒泡排序算法
    int m,i,j;    RedType x;    //交换时临时存储
    for(m=1;m <= n-1;m++){        //总共需m趟
        for(j=1;j <= n-m;j++)
            if(L.r[j].key > L.r[j+1].key){    //发生逆序
                x=L.r[j];    L.r[j]=L.r[j+1];    L.r[j+1]=x;    //交换
            }
    }
}

优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素

改进后的冒泡排序

void bubble_sort(SqList &L){    //改进后的冒泡排序算法
    int m,i,j; flag=1; RedType x;    //flag作为是否有交换的标记
    for(m=1;m <= n-1&&flag==1;m++){        //总共需m趟
        flag = 0;
        for(j=1;j <= m;j++)
            if(L.r[j].key > L.r[j+1].key){    //发生逆序
                flag = 1;    //发生交换，flag置为1，若本趟没有发生交换，flag保持为0
                x=L.r[j];    L.r[j]=L.r[j+1];    L.r[j+1]=x;    //交换
            }
    }
}

最好情况（正序）：比较次数为n-1 移动次数为0

最坏情况（逆序）：比较次数为 (n^2-n) / 2 移动次数为 3(n^2-n) / 2

快速排序

不适于对原本有序或基本有序的记录序列进行排序（无论正序还是逆序）

基本思想

任取一个元素为中心（pivot为枢轴、中心点）
所有比它小的元素一律前放，比它大的元素一律后放，形成左右两个子表；
对各子表重新选择中心元素并依此规则调整
直到每个子表的元素只剩一个

void main(){
    QSort(L,1,L.length);
}

//QSort()的时间复杂度为O(log2n)
void QSort(SqList &L,int low,int high){    //对顺序表L快速排序
    if(low < high){    //长度大于1
        pivotloc = Partition(L,low,high);
            //将L.r[low……high]一分为2，pivotloc为枢轴元素排好序的位置
        QSort(L,low,pivotloc-1);    //对低子表递归排序
        QSort(L,pivotloc+1，high);    //对高子表递归排序
    }
}

//Partition()的时间复杂度为O(n)
int Partition(SqList &L,int low,int high){
    L.r[0] = L.r[low];
    pivotloc = L.r[low].key;
    while(low < high){
        while(low < high && L.r[high].key >= pivotloc)    --high;
        L.r[low] = L.r[high];
        while(low < high && L.r[high].key <= pivotloc)    ++low;
        L.r[high] = L.r[low];
    }
    L.r[low] = L.r[0];
    return low;
}

①划分元素的选取是影响时间性能的关键

②输入数据次序越乱，所选划分元素值的随机性越好，排序速度越快，快速排序不是自然排序方法

③最坏情况下，快速排序的时间复杂性总是O(n^2)

选择排序

简单选择排序

基本思想：在待排序的数据中选出最大（小）的元素放在其最终的位置

n个元素需要n-1趟操作才能形成最后的排序

void SelectSort(SqList &L){
    //对顺序表L做简单选择排序
    for(i=1;i<L.length;++i){
        k = i;
        for(j=i+1;j <= L.length;++j)
            if(L.r[j],key<L.r[k].key)    k=j;    //k指向此趟排序中关键字最小的记录
        if(k!=i){
            t=L.r[i];    L.r[i]=L.r[k];    L.r[k]=t;
        }
    }
}

记录移动次数最好情况：O 最坏情况：3(n-1)

比较次数：n(n-1) / 2

可用于链式存储结构

堆排序

堆的实质是完全二叉树：二叉树中任一非叶子结点均大于（小于）它的孩子结点

若在输出堆顶的最小值（最大值）后，使得剩余n-1个元素的序列重新又建成一个堆，则得到n个元素的次小值（次大值）。之后便能得到一个有序序列，这个过程称为堆排序

堆的调整

1.输出根并以最后一个元素代替之

2.比较其左右孩子值的大小，并与其中最小者交换（小根堆）

void HeapAdjust(SqList &L,int s,int m){    //调整为以R[s]为根的大根堆
    rc = L.r[s];
    for(j=2*s;j<=m;j*=2){    //沿key较大的孩子结点向下筛选
        if(j<m && L.r[j].key<L.r[j+1].key)    ++j;
        if(rc >= L.r[j].key)    break;
        L.r[s] = L.r[j];    s=j;        //rc应插入在位置s上
    }
    L.r[s] = rc;
}

建初堆

void CreateHeap(SqList &L){
    n = L.length;
    for(i=n/2;i>0;--i)    //从最后一个非叶子结点向前
        HeapAdjust(L,i,n);
}

堆排序

void HeapSort(SqList &L){
    CreateHeap(L);            //将无序序列L.r[1,2……n-1]建成大根堆
    for(i=L.length;i>1;--i){
        x = L.r[1];
        L.r[1] = L.r[i];
        L.r[i] = x;
        HeapAdjust(L,1,i-1);    //将L.r[1,2……n-1]重新调整为大根堆
    }
}