8.1 排序的基本概念

8.1.1 排序的定义

排序，就是重新排列表中的元素，使表中的元素满足按关键字有序的过程

算法的稳定性：对于相同关键字使用某一排序算法后不改变其相对位置，则称该算法是稳定的

排序的分类.png

对任意n个关键字排序比较次数至少为

8.2 插入排序

每次将一个待排序记录按其关键字大小插入到前面已排好的序列的子序列中，直到全部记录插入完成

8.2.1 直接插入排序

void InsertSort(int A[],int n){
    int i,j,temp;
    for (i=1;i<n;i++)
        if(A[i]<A[i-1]){
            temp=A[i];
            for(j=i-1;j>=0&&A[j]>temp;--j)
                A[j+1]=A[j];
            A[j+1]=temp;
        }
}

算法空间复杂度为O(1)，时间复杂度为O(n²)

8.2.2 折半插入排序

先⽤折半查找找到应该插⼊的位置，再移动元素

折半插入排序.png

void InsertSort(int A[], int n){
    int i,j,low,high,mid;
    for(i=2;i<=n;i++){
        A[0]=A[i];
        low=1; high=i-1;
        while(low<=high){
            mid=(low+high)/2;
            if(A[mid]>A[0]) 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];
    }
}

算法时间复杂度为O(n²)

8.2.3 希尔排序

将排序分割成若干的特殊子表，对各个子表进行直接插入排序，缩小增量d，重复上述过程，直到d=1为止

希尔排序.png

void ShellSort(int A[], int n){
    int d,i,j;
    for(d=n/2;d>=1;d=d/2)
        for(i=d+1;i<=n;++i)
            if(A[i]<A[i-d]){
                A[0]=A[i];
                for(j=i-d;j>0&&A[0]<A[j];j-=d)
                    A[j+d]=A[j];
                A[j+d]=A[0];
            }
}

算法时间复杂度为O(n²)

8.3 交换排序

8.3.1 冒泡排序

void swap(int &a, int &b){
    int temp = a;
    a=b;
    b=temp;
}

void BubbleSort(int A[], int n){
    for(int i=0; i<n-1; i++){
        bool flag = false;
        for(int j=n-1;j>i;j--)
            if (A[j-1]>A[j]){
                swap(A[j-1],A[j]);
                flag=true;
            }
        if (flag == false)
            return;
    }
}

算法时间复杂度为O(n²)

8.3.2 快速排序

int Partition(int A[], int low, int high){
    // 用第一个元素将序列分为左右两个部分
    int pirot = A[low];
    while (low<high){
        while(low<high&&A[high]>=pirot) --high; //比枢纽小的元素移到左端
        A[low]=A[high];
        while(low<high&&A[high]<=pirot) ++low; //比枢纽大的元素移到右端
        A[high]=A[low];
    }
    A[low]=pirot; //枢纽元素存放到最终位置
    return low;
}

void QuickSort(int[], int low, int high){
    if(low<high){
        int pirotpos = Partition(A,low,high);
        QuickSort(A,low,pirotpos-1);
        QuickSort(A,pirotpos+1;high);
    }
}

算法时间复杂度为O(n²)，空间复杂度O(递归层数)

但平均时间复杂度O(nlog₂n)

8.4 选择排序

选择排序：每一趟在待排元素中选取关键字最小的元素加入有序子序列

8.4.1 简单选择排序

void SelectSort(int A[], int n){
    for (i=0;i<n-1;i++){
        int min = i;
        for(j=i+1;j<n;j++)
            if(A[j]<A[min]) min=j;
        if(min!=i) swap(A[i],A[min]);
    }
}

算法时间复杂度为O(n²)

8.4.2 堆排序

n个关键字序列称为堆

• 若满足则称为大根堆

• 若满足则称为小根堆

思路：把所有⾮终端结点都检查⼀遍，是否满⾜⼤根堆的要求(根≥左、右)，如果不满⾜，则将当前结点与更⼤的⼀个孩⼦互换

大根堆.png

//建立大根堆
void BuildMaxHeap(int A[], int len){
    for (int i=len/2;i>0; i--)
        HeadAdjust(A,i,len);
}

//将以k为根的子树调整为大根堆
void HeadAdjust(int A[],int k; int len){
    A[0]=A[k];  //A[0]存放子树根节点
    for(int i=2*k; i<=len; i*=2){
        if (i<len&&A[i]<A[i+1]) i++;    //取key较大子结点下标
        if (A[0] >= A[i]) break;
        else{
            A[k]=A[i];  //将A[u]调整到双亲结点上
            k=i;    //修改k值，继续筛选
        }
    }
    A[k]=A[0];  //被筛选结点放入最终位置
}

//堆排序算法
void HeadSort(int A[], int len){
    BuildMaxHeap(A,len);
    for(i=len;i>1;i--){
        swap(A[i], A[1]);   //堆顶元素与堆底元素交换
        HeadAdjust(A,1,i-1);    //把剩余i-1个元素整理成堆
    }
}

时间复杂度O(nlog₂n)

关键字对比次数不超过4n

8.5 归并排序和基数排序

8.5.1 归并排序

归并：把两个或多个已经有序的序列合并成一个

n个记录可视为n个有序子表，两两归并，直到得到长度为n的有序表

int *B = (int *)malloc(n*sizeof(int)); //辅助数组B
void Merge(int A[], int low,int mid, int high){
    int i,j,k;
    for(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]) A[k]=B[i++]; //将较小值复制到A中
        else A[k]=B[j++];
    }
    while(i<=mid) A[k++]=B[i++]; //若第一个表未检测完 复制；
    while(j<=high) A[k++]=B[j++]; //若第二个表未检测完 复制；
}

n个元素归并并排序，需要归并躺

时间复杂度O(nlog₂n) ，空间复杂度为O(n)

8.5.2 基数排序

基数排序不基于比较和移动排序，而基于关键字各位的大小进行排序

递减序列过程：

1. 初始化：设置r个空队列
2. 按照各个关键字位权重递增的次序，对d个关键字位分别做分配和收集
3. 收集，把各个队列的结点依次出队并连接

空间复杂度O(r),时间复杂度O(d(m+n))

8.6 外部排序

8.6.1 外部排序的原理

使用归并排序，最小只需在内存中分配3块大小的缓冲区，即可对任意一个大文件进行排序

归并排序要求各个子序列有序，每次读入两个块内容进行内部排序后写回磁盘

1. 构造初始归并端，需要16*2=32次读写
2. 第一趟归并，需要16*2=32次读写
3. 第二躺归并，需要16*2=32次读写
4. 第三躺归并，需要16*2=32次读写

外部排序的时间开销=读写外村时间+内部排序时间+内部归并时间

读写磁盘次数=32*3+32=128次读写，其中3为归并躺数，可以采用多路归并减小归并趟数，即减小IO次数

对于k叉树(k路归并)，若树高为h，

8.6.2 败者树

败者树如比赛图，可以视为一颗完全二叉树

对于k路归并使用败者树选出最小元素需要比较次

8.6.3 置换选择排序

用于内部排序的内存工作区WA可容纳l个记录，则每个初始归并段也只能包含l个记录，若文件右n个记录，则归并段数量

使用置换排序可以摆脱这个限制

1. 从FI输出w个记录到工作区WA
2. 从WA选择关键字最小记录，记为MINIMAX
3. 输出到FO
4. 若FI不空，FI输入到WA中
5. 从WA中所有比MINIMAX大且关键字最小的输出，直到选不出为止，得到一个归并段，输出到FO

8.6.4 最佳归并树

归并过程中的I/O次数=归并数的WPL2*

对于k叉归并，段数量无法构成严格k叉归并树，则需要补充n个长度为0的虚段，再进行k叉哈夫曼树的构造

初始归并段数量+虚段数量=n₀

若

则补充(k-1)-u个虚段