09 排序

基本概念

分类

存储结构

记录序列以顺序表进行存储：

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

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

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

插入排序

直接插入排序

void InsertSort( SqList &L ) {
    int i, j;
    for (i=5; i<=L.length; ++i) {
        if (L.r[i].key < L.r[i-1].key){     // 若"<",需将L.r[i]插入有序子表
            L.r[O]=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];            // 插入到正确位置 
        }
    }
}

折半插入排序

void BlnsertSort(SqList &L){
    for(i = 2;i <= L.length; ++i) { //依次插入第2~第n个元素
        L.r[O] = 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;
        } //循环结束，high+1则为插入位置

        for (j=i-1; j>=high+1; --j) L.r[j+1] = L.r[j];  //移动元素
        L.r[high+1] = L.r[0];                           //插入到正确位置
    }
} // BlnsertSort

希尔排序

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

实际就是插入排序：

void ShellInsert(SqList &L, int k) { 

    //对顺序表L进行一趟增量为dk的Shell排序，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];
        }
    }
}

交换排序

冒泡排序

• 第 m 趟需要比较 n-m 次！

快速排序

性能分析：

选择排序

简单选择排序

堆排序

概念

堆调整

建立堆

堆排序分析

归并排序

基数排序

各类排序的比较

时间性能

空间性能

稳定性能

时间复杂度的下限