排序

知识框架

No.1排序的基本概念

一、排序定义

• 排序，就是重新排列表中的元素，使表中的元素满足按关键字有序的过程。为了查找方便，通常希望计算机中的表是按关键字有序的。排序的确切定义如下：
  1. 输入：n个记录R 1 , R 2 , . . . , R n，对应的关键字为k 1 , k 2 , . . . , k n。
  2. 输出：输入序列的一个重排R 1 ′ , R 2 ′ , . . . , R n ′ ，使得k 1 ′ ≤ k 2 ′ ≤ . . . ≤ k n ′ （其中“≤”可以换成其他比较大小的符号）
• 排序的稳定性。假设k i = k j ( 1 ≤ i ≤ n , 1 ≤ j ≤ n , i ! = j ) ，且在排序前的序列中R i领先于R j(即i < j)。如果排序后R i仍领先于R j，则称所用的排序方法是稳定的；反之，若可能使得排序后的序列中R j领先于R i，则称所用的排序方法是不稳定的。
  需要注意的是，算法是否具有稳定性并不能衡量一个算法的优劣，它主要是对算法的性质进行描述。如果待排序表中的关键字不允许重复，则排序结果是唯一的，那么选择排序算法时的稳定与否就无关紧要。
• 内排序和外排序。内排序是在排序整个过程中，待排序的所有记录全部被放置在内存中。外排序是由于排序的记录个数太多，不能同时放置在内存,整个排序过程需要在内外存之间多次交换数据才能进行。

二、内部排序方法的分类

• 通常可以将排序算法分为插入排序、交换排序、选择排序、归并排序和基数排序五大类。每种排序算法都有各自的优缺点，适合在不同的环境下使用，就其全面性能而言，很难提出一种被认为是最好的算法。内部排序算法的性能取决于算法的时间复杂度和空间复杂度，空间复杂度由排序算法所需的辅助空间决定，而时间复杂度一般是由比较和移动的次数决定的。
• 内部排序的过程是一个逐步扩大记录的有序序列长度的过程。在排序的过程中，可以将排序记录区分为两个区域：有序序列区和无序序列区。
• 使有序区中记录的数目增加一个或者几个的操作称为一趟排序。

1.插入类

• 将无序子序列中的一个或几个记录插入有序序列，从而增加记录的有序子序列的长度。主要包括：
  1. 直接插入排序。
  2. 折半插入排序。
  3. 希尔排序。
• 直接插入排序(将当前值直接插入到以排序好的序列中)，折半插入排序(采用二分法查找插入位置)，希尔排序(利用缩小增量减少记录个数和使关键字基本有序)。

2.交换类

• 通过交换无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入有序子序列中，以此方法增加记录的有序子序列的长度。主要包括：
  1. 冒泡排序。
  2. 快速排序。
• 冒泡排序(交换相邻的位置，每次使最大的归位)，快速排序(跳跃式比较、交换两个数)。

3.选择类

• 从记录的无序子序列中选择关键字最小或最大的记录，并将它加入有序子序列中，以此方法增加记录的有序子序列的长度。主要包括：
  1. 选择排序。
  2. 树形选择排序。
  3. 堆排序。
• 简单选择排序(每次找出最小，让其归位)，堆排序(利用二叉树，减少比较次数)。

4.归并类

• 通过归并两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。主要包括：2-路归并是主要的归并排序方法。
• 将两个或两个以上有序表合并成一个有序表的过程。

5.分配类

• 是唯一一类不需要进行关键字比较的排序方法，排序时主要利用分配和收集两种基本操作来完成。基数排序是主要的分配排序方法。
• 不比较关键字大小，通过对待排序记录进行若干趟“分配”和“收集”

三、待排序记录的存储方式

• 顺序表：记录之间的次序关系由其存储位置决定，实现排序需要移动记录。
• 链表：记录之间的次序关系由指针决定，实现排序不需要移动记录，仅需修改指针。
• 待排序记录本身存储在一组地址连续的存储单元内，同时另设一个指示各个记录存储位置的地址向量，在排序过程中不移动记录本身，而移动地址向量中这些记录的“地址”，在排序结束之后按照地址向量中的值调整记录的存储位置。

#define MAXSIZE 10	//用于要排序数组个数最大值，可根据需要修改
typedef int KeyType;
typedef struct {
    KeyType key;                // 关键字项
}RedType;

typedef struct{ 
	RedType r[MAXSIZE + 1 ];	//用于存储要排序的数组，r[0]闲置用作哨兵单元
	int length;	            //用于记录顺序变的长度
}SqList;

四、排序算法效率和评价指标

• 就排序方法的全面性能而言，很难提出一种被认为是最好的方法。目前，评价排序算法好坏的指标主要有两点。
• 执行时间
  1. 对于排序操作，时间主要消耗在关键字之间的比较和记录的移动上(这里,只考虑以顺序表方式存储待排序记录)，排序算法的时间复杂度由着两个指标决定。因此可以认为，高效率的排序算法的比较次数和移动次数都应该尽可能地少。
• 辅助空间
  1. 空间复杂度由排序算法所需的辅助空间决定。辅助空间是除了存放待排序记录占用的空间之外，执行算法所需要的其他存储空间。理想的空间复杂度为O(1),即算法执行期间所需要的辅助空间与待排序的数据量无关。

No.2插入排序

• 插入排序的基本思想是：每一趟将一个待排序的记录，按其关键字的大小插入已经排好序的一组记录的适当位置，直到所有待排序记录全部插入为止。

一、直接插入排序

• 直接插入排序(Straight Insertion Sort)的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。

1.算法

• 设待排序的记录存放在数组r[1..n]中，r[1]是一个有序序列。
• 循环n-1次，每次使用顺序查找法，查找r[i](i=2, ... ,n)在已排好序的序列r[1..i-1]中的插入位置，然后将r[i]插入表长为i-1的有序序列r[1..i-1]，直到将r[n]插入表长为n-1的有序序列r[1..n-1]，最后得到一个表长为n的有序序列。
• 具体实现r[i]向前面的有序序列插入时，有两种方法：
  1. 一种是将r[i]与r[1]，r[2]，...，r[i-1]从前向后顺序比较。
  2. 另一种是将r[i]与r[i-1]，r[i-2]，...，r[1]从后向前顺序比较。
  3. 这里采用后一种方法，和顺序查找类似，为了在查找插入位置的过程中避免数组下标出界，在r[0]处设置监视哨。在自i-1起往前查找插入位置的过程中，可以同时后移记录。

void InsertSort(SqList* L) {
    int i, j;
    //依次将r[2]~r[n]插入到前面已排序序列，r[1]为默认排好序的序列，r[0]作为哨兵不存放元素
    for (i = 2; i <= L->length; ++i) {
        if (L->r[i].key < L->r[i - 1].key) {
            L->r[0] = L->r[i];     //将待插入元素暂存到哨兵位置
            L->r[i] = L->r[i-1];   //r[i-1]后移
            for (j = i - 2; L->r[0].key < L->r[j].key; --j)
                L->r[j + 1] = L->r[j]; //向后挪位
            L->r[j + 1] = L->r[0]; //插入待排序元素到正确位置
        }
    }
}

2.性能分析

• 时间复杂度
  1. 从时间来看，排序的基本操作为：比较两个关键字的大小和移动记录。
  2. 在平均情况下，直接插入排序的关键字的比较次数和记录移动次数均为n^{2/4.由此，直接插入的时间复杂度为O(n}2).
• 空间复杂度
  1. 直接插入排序只需要一个记录的辅助空间r[0]。
  2. 所以空间复杂度为O(1)。
• 算法特点
  1. 是稳定排序。
  2. 算法简便，且容易实现。
  3. 也适用于链式存储结构，只是在单链表上不是移动记录，而是修改相应的指针。
  4. 更适合于初始记录基本有序(正序)的情况，当初始化记录无序,n较大时，此算法时间复杂度较高，不宜采用。

3.完整代码

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 10 //用于要排序数组个数最大值，可根据需要修改
typedef int KeyType;
typedef struct {
    KeyType key; // 关键字项
} RedType;

typedef struct {
    RedType r[MAXSIZE + 1]; //用于存储要排序的数组，r[0]闲置用作哨兵单元
    int length;             //用于记录顺序变的长度
} SqList;

void InsertSort(SqList* L) {
    int i, j;
    //依次将r[2]~r[n]插入到前面已排序序列，r[1]为默认排好序的序列，r[0]作为哨兵不存放元素
    for (i = 2; i <= L->length; ++i) {
        if (L->r[i].key < L->r[i - 1].key) {
            L->r[0] = L->r[i];     //将待插入元素暂存到哨兵位置
            L->r[i] = L->r[i - 1];   //r[i-1]后移
            for (j = i - 2; L->r[0].key < L->r[j].key; --j)
                L->r[j + 1] = L->r[j]; //向后挪位
            L->r[j + 1] = L->r[0]; //插入待排序元素到正确位置
        }
    }
}

int main() {
    SqList list;
    list.length = 8;
    list.r[1].key = 49;
    list.r[2].key = 38;
    list.r[3].key = 65;
    list.r[4].key = 97;
    list.r[5].key = 76;
    list.r[6].key = 13;
    list.r[7].key = 27;
    list.r[8].key = 49;

    printf("排序前：");
    for (int i = 1; i <= list.length; i++) {
        printf("%d ", list.r[i].key);
    }
    printf("\n");

    InsertSort(&list);

    printf("排序后：");
    for (int i = 1; i <= list.length; i++) {
        printf("%d ", list.r[i].key);
    }
    printf("\n");

    return 0;
}

二、折半插入排序

• 直接插入排序采用顺序查找法查找当前记录在已排好序的序列中插入位置，这个“查找”操作可利用“折半查找”来实现，由此进行的插入排序称之为折半插入排序(Binary Insertion Sort)。

1.算法

• 将待排序的记录存放在数组r[1..n]中，r[1]是一个有序序列。
• 循环n-1次，每次使用折半查找法，查找r[i]插入表长为i-1的有序序列r[1..i-1]，直到将r[n]插入表长为n-1的有序序列r[1..n-1]，最后得到一个表长为n的的有序序列。

void HalfInsertSort(SqList *L){
	int i,j,low,high,mid;
	//依次将r[2]~r[n]插入前面的已排序序列
	for(i=2; i<=L->length;i++){
		L->r[0] = L->r[i];	//将r[i]暂存到r[0]
		low=1; high=i-1;	//设置折半查找的范围
		//折半查找（默认递增有序）
		while(low <= high){
			mid = (low + high) / 2;	//取中间点
			if(L->r[mid].key > L->r[0].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];	//插入操作
	}
}

2.性能分析

• 时间复杂度
  1. 从时间上比较，折半查找比顺序查找块，所以就平均性能来说，折半插入排序优于直接插入排序。
  2. 折半插入排序所需要的关键字比较次数与待排序序列的初始排列无关，仅依赖于记录的个数。不论初始序列情况如何，在插入第i个记录时，需要经过log2i+1次比较，才能确定它应插入的位置。所以当记录的初始排序为正序或接近正序时，直接插入排序比折半插入排序执行的关键字比较次数要少。
  3. 折半插入排序的对象移动次数与直接插入排序相同，依赖于对象的初始排列。在平均情况下，折半插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。因此，折半插入排序的时间复杂度仍为(n^2)。
• 空间复杂度
  1. 折半插入排序所需附加存储空间和直接插入排序相同，只需要一个记录的辅助空间r[0]。
  2. 所以空间复杂度为O(1)。
• 算法特点
  1. 是稳点排序。
  2. 因为要进行折半查找，所以只能用于顺序结构，不能用于链式结构。
  3. 适合初始记录无序、n较大时的情况。

3.完整代码

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 10 //用于要排序数组个数最大值，可根据需要修改
typedef int KeyType;
typedef struct {
    KeyType key; // 关键字项
} RedType;

typedef struct {
    RedType r[MAXSIZE + 1]; //用于存储要排序的数组，r[0]闲置用作哨兵单元
    int length;             //用于记录顺序变的长度
} SqList;

void HalfInsertSort(SqList* L) {
    int i, j, low, high, mid;
    //依次将r[2]~r[n]插入前面的已排序序列
    for (i = 2; i <= L->length; i++) {
        L->r[0] = L->r[i];	//将r[i]暂存到r[0]
        low = 1; high = i - 1;	//设置折半查找的范围
        //折半查找（默认递增有序）
        while (low <= high) {
            mid = (low + high) / 2;	//取中间点
            if (L->r[mid].key > L->r[0].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];	//插入操作
    }
}

int main() {
    SqList list;
    list.length = 8;
    list.r[1].key = 49;
    list.r[2].key = 38;
    list.r[3].key = 65;
    list.r[4].key = 97;
    list.r[5].key = 76;
    list.r[6].key = 13;
    list.r[7].key = 27;
    list.r[8].key = 49;


    printf("排序前：");
    for (int i = 1; i <= list.length; i++) {
        printf("%d ", list.r[i].key);
    }
    printf("\n");

    HalfInsertSort(&list);

    printf("排序后：");
    for (int i = 1; i <= list.length; i++) {
        printf("%d ", list.r[i].key);
    }
    printf("\n");

    return 0;
}

三、希尔排序

• 希尔排序又称“缩小增量排序”(Diminishing Incerment Sort)，是插入排序的一种，因D.L.Shell于1959年提出而得名。
• 当待排序的记录个数较少且待排序序列的关键字基本有序时，直接插入排序效率较高。
• 希尔排序基于以上两点，从“减少记录个数”和“序列基本有序”两个方面对直接插入排序进行了改进。
• 希尔排序的算法实现如下所示，预设好的增量序列保存在数组dt[0..t-1]中，整个希尔排序算法需执行t趟。从下面排序过程可见，直接插入排序算法可以看成一趟增量是1的希尔排序，所以可以改写直接排序算法，得到一趟希尔排序ShellInsert。在ShellInsert中，具体改写主要有两处：
  1. 前后记录位置的增量是dk，而不是1。
  2. r[0]只是暂存单元，不是哨兵。当j<=0，插入位置已找到。
• 例如：已知待排序记录的关键字序列为{49,38,65,97,76,13,27,49,55,04}，请给出用希尔排序排序法进行排序的过程。
  1. 第一趟取增量d1=5，所有间隔为5的记录分在同一组，全部记录分成5组，在各个组中分别进行直接插入排序，排序结果如图第2行所示。
  2. 第一趟取增量d2=3，所有间隔为3的记录分在同一组，全部记录分成3组，在各个组中分别进行直接插入排序，排序结果如图第3行所示。
  3. 第三趟取增量d3=1，对整个序列进行一趟直接插入排序，排序完成。

1.算法

• 希尔排序实质上是采用分组插入的方法。先将整个待排记录序列分割成几组，从而减少参与直接插入排序的数据量，对每组分别进行插入排序，然后增加每组的数据量，重新分组，这样当经过几次分组排序后，整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
• 希尔对记录的分组，不是简单地“逐段分割”，而是将相隔某个“增量”的记录分成一组。
  1. 第一趟取增量d1(d1<n)把全部记录分成d1个组，所有间隔为d1的记录分在同一组，在各个组中进行直接插入排序。
  2. 第二趟取增量d2(d2<d1)，重复上述的分组和排序。
  3. 依次类推，直到所有的增量dt=1(dt<d(t-1)<...<d2<d1)，所有记录在用一组中进行直接插入排序为止。

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

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

2.性能分析

• 时间复杂度
  1. 当增量大于1时，关键字较小的记录就不是一步步地挪动，而是跳跃式地移动，从而使得在进行最后一趟增量为1的插入排序中，序列已基本有序，只要作记录的少量比较和移动即可完成排序，因此希尔排序的时间复杂度较直接插入排序地。当要具体分析，则是一个复杂的问题。
• 空间复杂度
  1. 从空间来看，希尔排序和前面两种排序方法一样，也只需要一个辅助空间r[0],空间复杂度为O(1)
• 算法特点
  1. 记录跳跃式地移动导致排序方法是不稳定的。
  2. 只能用于顺序结构，不能用于链式结构。
  3. 增量序列可以有各种取法，当应该使增量序列中的值没有除1之外的公因子，并且最后一个增量必须等于1。
  4. 记录总的比较次数和移动次数都比直接插入排序要少，n越大时，效果越明显。所以适合以初始记录无序、n较大时的情况。

3.完整代码

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 20 //用于要排序数组个数最大值，可根据需要修改
typedef int KeyType;
typedef struct {
    KeyType key; // 关键字项
} RedType;

typedef struct {
    RedType r[MAXSIZE + 1]; //用于存储要排序的数组，r[0]闲置用作哨兵单元
    int length;             //用于记录顺序变的长度
} SqList;

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

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

int main() {
    SqList list;
    list.length = 10;
    list.r[1].key = 49;
    list.r[2].key = 38;
    list.r[3].key = 65;
    list.r[4].key = 97;
    list.r[5].key = 76;
    list.r[6].key = 13;
    list.r[7].key = 27;
    list.r[8].key = 49;
    list.r[9].key = 55;
    list.r[10].key = 4;

    int t = 3;
    int dt[3] = { 5,3,1 };


    printf("排序前：");
    for (int i = 1; i <= list.length; i++) {
        printf("%d ", list.r[i].key);
    }
    printf("\n");

    ShellSort(&list,dt,t);

    printf("排序后：");
    for (int i = 1; i <= list.length; i++) {
        printf("%d ", list.r[i].key);
    }
    printf("\n");

    return 0;
}

No.3交换排序

• 交换排序的基本思路：两两比较待排序记录的关键字，一旦发现两个记录不满足次序要求时则进行交换，直到整个序列全部满足要求为止。

一、冒泡排序

• 冒泡排序是基于交换排序的一种排序，交换排序的基本思想，是两两比较待排序记录的关键字，一旦发现两个记录不满足次序要求时则进行交换，直到整个序列全部满足要求为止。 冒泡排序是一种最简单的交换排序方法，它通过两两比较相邻记录的关键字，如果发生逆序，则进行交换，从而使关键字小的记录如气泡一般逐渐往上“漂浮”(左移)，或者使关键字大的 记录如石块一样逐渐向下“坠落”(右移)。

1.算法

• 设待排序的记录存放在数组r[1..n]中。首先将第一个记录的关键字和第一个记录的关键字进行比较，若为逆序，即r[1]>r[2]，则交换两个记录。然后比较第二个记录和第三个记录的关键字。依次类推，直到第n-1个记录和第n个记录的关键字进行过比较为止。上述过程称为第一趟起泡排序，其结果使得关键字最大的记录被安置到最后一个记录的位置上。
• 然后进行第二趟起泡排序，对前n-1个记录进行同样操作，其结果是使得关键字次大的记录被安置到第n-1个记录的位置上。
• 重复上述比较和交换过程，第i趟是从r[1]到r[n-i+1]依次比较相邻两个记录的关键字，并在“逆序”时交换相邻记录，其结果是这n-i+1个记录中关键字最大的记录被交换到第n-i+1的位置上。直到某一趟排序过程中没有进行交换记录的操作，说明序列已全部达到排序要求，则完成排序。

void BubbleSort(SqList* L) {
    int m = L->length;
    int flag = 1;      //表示本趟冒泡是否发生交换的标志
    while ((m > 0) && (flag == 1))
    {
        flag = 0;      //flag置为0，如果本趟排序没有发生交换，则不会执行下一趟排序
        for (int j = 1; j < m; j++) // 注意这里应该是 j < m 而不是 j <= m
            if (L->r[j].key > L->r[j + 1].key)   //若为逆序
            {
                flag = 1;     //flag置为1,表示本趟排序发生了交换
                //交换
                RedType t = L->r[j];
                L->r[j] = L->r[j + 1];
                L->r[j + 1] = t;
            }
        --m;
    }
}

2.性能分析

• 时间复杂度
  1. 最好情况(初始序列为正序)：只需进行一趟排序，在排序过程中进行n-1次关键字减的比较，且不移动记录。
  2. 最坏情况(初始序列为逆序)：需进行n-1趟排序，总的关键字比较次数KCN和记录移动次数RMN(每次交换都要移动3次记录)分别为 KCN=n(n-1)/2=(n^2)/2 RMN=3n(n-1)/2=3(n^2)/2
  3. 所以在平均情况下，冒泡排序关键字的比较次数和记录移动次数分别约为(n^2)/4和3(n2)/4，时间复杂度为O(n^2)。
• 空间复杂度
  1. 冒泡排序只有在两个记录交换位置时需要一个辅助空间用做暂存记录。
  2. 所以空间复杂度为O(1)。
• 算法特点
  1. 是稳点排序。
  2. 可用于链式存储结构。
  3. 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时，此算法不宜采用。

3.完整代码

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 20 //用于要排序数组个数最大值，可根据需要修改
typedef int KeyType;
typedef struct {
    KeyType key; // 关键字项
} RedType;

typedef struct {
    RedType r[MAXSIZE + 1]; //用于存储要排序的数组，r[0]闲置用作哨兵单元
    int length;             //用于记录顺序变的长度
} SqList;

void BubbleSort(SqList* L) {
    int m = L->length;
    int flag = 1;      //表示本趟冒泡是否发生交换的标志
    while ((m > 0) && (flag == 1))
    {
        flag = 0;      //flag置为0，如果本趟排序没有发生交换，则不会执行下一趟排序
        for (int j = 1; j < m; j++)    // 注意这里应该是 j < m 而不是 j <= m
            if (L->r[j].key > L->r[j + 1].key)   //若为逆序
            {
                flag = 1;     //flag置为1,表示本趟排序发生了交换
                //交换
                RedType t = L->r[j];
                L->r[j] = L->r[j + 1];
                L->r[j + 1] = t;
            }
        --m;
    }
}

int main() {
    SqList list;
    list.length = 8;
    list.r[1].key = 49;
    list.r[2].key = 38;
    list.r[3].key = 65;
    list.r[4].key = 97;
    list.r[5].key = 76;
    list.r[6].key = 13;
    list.r[7].key = 27;
    list.r[8].key = 49;

    printf("排序前：");
    for (int i = 1; i <= list.length; i++) {
        printf("%d ", list.r[i].key);
    }
    printf("\n");

    BubbleSort(&list);

    printf("排序后：");
    for (int i = 1; i <= list.length; i++) {
        printf("%d ", list.r[i].key);
    }
    printf("\n");

    return 0;
}

二、快速排序

• 快速排序是由冒泡排序改进而得的。在冒泡排序过程中，只对相邻的两个记录进行比较，因此每次交换两个相邻记录时只能消除一个逆序。如果能通过两个(不相邻)记录的依次交换，消除多个逆序,则会大大加快排序的速度。快速排序方法中的一次交换可能消除多个逆序。

1.算法

• 在待排序的n个记录中任取一个记录(通常取第一个记录)作为枢轴(或支点)，设其关键字为pivotkey。经过一趟排序后，把所有关键字小于pivotkey的记录交换到前面，把所有关键字大于pivotkey的记录交换到后面，结果将待排序记录分成两个子表，最后将枢轴放置在分界处的位置。然后，分别对左、右子表重复上述过程，直至每一子表只有一个子记录时，排序完成。又是分治的思想，分解，解决，合并。
• 其中，一趟快速排序的具体做法如下。
  1. 附设两个指针low和high，初始时分别指向表的下界和上界，设枢轴记录的关键字为pivotkey(第一趟时，low=1;high=L.length;)
  2. 从表的最右侧位置，依次向左搜索找到第一个关键字小于pivotkey的记录和枢轴记录交换。具体操作是:当low<high时，若high所指的关键字大于等于pivotkey,则向左移动指针high,(执行操作--high);否则将high所指记录与枢轴记录交换。
  3. 然后再从表的最左侧位置，依次向右搜索找到第一个关键字大于pivotkey的记录和枢轴记录交换。具体操作是：当low<high时，若low所指的关键字小于等于pivotkey,则向右移动指针low(执行操作++low);否则将low所指记录与枢轴记录交换。
  4. 重复步骤(2)和步骤(3),直到low与high相等为止。此时low或high的位置即为枢轴在此趟排序中的最终位置，原表被分成两个子表。
• 在上述过程中，记录的交换都是与枢轴之间发生，每次交换都要移动3次记录，可以先将枢轴记录暂存在r[0]的位置上，排序过程中只移动要与枢轴交换的记录，即只做r[low]或r[high]的单向移动，直至一趟排序记录结束后再将枢轴记录移至正确的位置上。

int Partition(SqList* L, int low, int high)
{
    //对顺序表L中的子表r[low..high]进行一趟排序,返回枢轴位置
    RedType pivotkey = L->r[low];  //枢轴记录关键字保存在pivotkey中
    while (low < high)    //从表的两端交替地向中间扫描
    {
        //将比枢轴记录小的记录移到低端
        while (low < high && L->r[high].key >= pivotkey.key) --high;
        L->r[low] = L->r[high];

        //将比枢轴记录大的记录移到高端
        while (low < high && L->r[low].key <= pivotkey.key) ++low;
        L->r[high] = L->r[low];
    }
    L->r[low] = pivotkey;        //枢轴记录到位
    return low;
}

void Qsort(SqList* L, int low, int high)
{
    //调用前置初值：low = 1; high = L->length;
    //对顺序表L中的子序列L[low..high]做快速排序
    if (low < high)       //长度大于1
    {
        int pivotloc = Partition(L, low, high);    //将L[low..high]一分为二，pivotloc是枢轴位置
        Qsort(L, low, pivotloc - 1);               //对左子表递归排序
        Qsort(L, pivotloc + 1, high);              //对右子表递归排序
    }
}

void QuickSort(SqList* L)
{
    Qsort(L, 1, L->length);
}

2.性能分析

• 时间复杂度
  1. 最好O(nlog2n)。
  2. 最坏O(n^2)。
  3. 平均O(nlog2n)。
• 空间复杂度
  1. 快速排序是递归的，执行时需要一个栈来存放相应的数据。
  2. 最大递归调用次数与递归树的深度一致。
  3. 最好情况下为O(log2n)
  4. 最坏情况下为O(n)。

3.完整代码

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 20 //用于要排序数组个数最大值，可根据需要修改
typedef int KeyType;
typedef struct {
    KeyType key; // 关键字项
} RedType;

typedef struct {
    RedType r[MAXSIZE + 1]; //用于存储要排序的数组，r[0]闲置用作哨兵单元
    int length;             //用于记录顺序变的长度
} SqList;

int Partition(SqList* L, int low, int high)
{
    //对顺序表L中的子表r[low..high]进行一趟排序,返回枢轴位置
    RedType pivotkey = L->r[low];  //枢轴记录关键字保存在pivotkey中
    while (low < high)    //从表的两端交替地向中间扫描
    {
        //将比枢轴记录小的记录移到低端
        while (low < high && L->r[high].key >= pivotkey.key) --high;
        L->r[low] = L->r[high];

        //将比枢轴记录大的记录移到高端
        while (low < high && L->r[low].key <= pivotkey.key) ++low;
        L->r[high] = L->r[low];
    }
    L->r[low] = pivotkey;        //枢轴记录到位
    return low;
}

void Qsort(SqList* L, int low, int high)
{
    //调用前置初值：low = 1; high = L->length;
    //对顺序表L中的子序列L[low..high]做快速排序
    if (low < high)       //长度大于1
    {
        int pivotloc = Partition(L, low, high);    //将L[low..high]一分为二，pivotloc是枢轴位置
        Qsort(L, low, pivotloc - 1);               //对左子表递归排序
        Qsort(L, pivotloc + 1, high);              //对右子表递归排序
    }
}

void QuickSort(SqList* L)
{
    Qsort(L, 1, L->length);
}

int main() {
    SqList list;
    list.length = 8;
    list.r[1].key = 49;
    list.r[2].key = 38;
    list.r[3].key = 65;
    list.r[4].key = 97;
    list.r[5].key = 76;
    list.r[6].key = 13;
    list.r[7].key = 27;
    list.r[8].key = 49;

    printf("排序前：");
    for (int i = 1; i <= list.length; i++) {
        printf("%d ", list.r[i].key);
    }
    printf("\n");

    QuickSort(&list);

    printf("排序后：");
    for (int i = 1; i <= list.length; i++) {
        printf("%d ", list.r[i].key);
    }
    printf("\n");

    return 0;
}

No.4选择排序

• 选择排序的基本思想：每一趟从待排序的记录中选出关键字最小的记录，按顺序将其放在已排好序的记录序列的最后，直到全部排完为止。

一、简单选择排序

• 简单选择排序(Simple Selection Sort)也称作直接选择排序。

1.算法

• 设待排序的记录存放在数组r[1..n]中。第一趟从r[1]开始，通过n-1次比较，从n个记录中选出关键字最小的记录，记为r[k]，交换r[1]和r[k]。
• 第二趟从r[2]开始，通过n-2次比较，从n-1个记录中选出关键字最小的记录，记为r[k]，交换r[2]和r[k]。
• 依次类推，第i趟从r[i]开始，通过n-i次比较，从n-i+1个记录中选出关键字最小的记录，记为r[k]，交换r[i]和r[k]。
• 经过n-1趟，排序完成。

void SelectSort(SqList* L)
{//对顺序r做简单选择排序
    int k, t;
    for (int i = 1; i < L->length; ++i) {	   //在r[i..Length-1]中选择关键字最小的记录
        k = i;	//记录最小元素位置
        for (int j = i + 1; j <= L->length; ++j) {
            if (L->r[j].key < L->r[k].key) {	//在R[i...n-1]中选择最小的元素
                k = j;	//k指向此趟排序中关键字最小的记录
            }
        }
        if (k != i)
        {//交换r[i]与r[k]
            RedType t = L->r[i];
            L->r[i] = L->r[k];
            L->r[k] = t;
        }
    }
}

2.性能分析

• 时间复杂度
  1. 简单选择排序过程中，所需进行记录移动的次数较少。最好情况(正序)：不移动；最坏情况(逆序)：移动3(n-1)次。然而，无论记录的初始排列如何，所需进行的关键字间的比较次数相同，均为 KCN=n(n-1)/2=(n^2)/2。
  2. 因此，简单选择排序的时间复杂度也是O(n^2)。
• 空间复杂度
  1. 同冒泡排序一样，只有在两个记录交换时需要一个辅助空间.
  2. 所以空间复杂度为O(1)。
• 算法特点
  1. 由于算法以“交换记录”来实现“字前最小记录到位”，就有可能改变关键字相同记录的前后顺序，使得原来稳点的排序方法产生“不稳定”想象。
  2. 可用于链式存储结构。
  3. 移动记录次数较少，当每一记录占用的空间较多时，此方法比直接插入排序快。

3.完整代码

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 20 //用于要排序数组个数最大值，可根据需要修改
typedef int KeyType;
typedef struct {
    KeyType key; // 关键字项
} RedType;

typedef struct {
    RedType r[MAXSIZE + 1]; //用于存储要排序的数组，r[0]闲置用作哨兵单元
    int length;             //用于记录顺序变的长度
} SqList;

void SelectSort(SqList* L)
{//对顺序r做简单选择排序
    int k, t;
    for (int i = 1; i < L->length; ++i) {	   //在r[i..Length-1]中选择关键字最小的记录
        k = i;	//记录最小元素位置
        for (int j = i + 1; j <= L->length; ++j) {
            if (L->r[j].key < L->r[k].key) {	//在R[i...n-1]中选择最小的元素
                k = j;	//k指向此趟排序中关键字最小的记录
            }
        }
        if (k != i)
        {//交换r[i]与r[k]
            RedType t = L->r[i];
            L->r[i] = L->r[k];
            L->r[k] = t;
        }
    }
}

int main() {
    SqList list;
    list.length = 8;
    list.r[1].key = 49;
    list.r[2].key = 38;
    list.r[3].key = 65;
    list.r[4].key = 97;
    list.r[5].key = 76;
    list.r[6].key = 13;
    list.r[7].key = 27;
    list.r[8].key = 49;

    printf("排序前：");
    for (int i = 1; i <= list.length; i++) {
        printf("%d ", list.r[i].key);
    }
    printf("\n");

    SelectSort(&list);

    printf("排序后：");
    for (int i = 1; i <= list.length; i++) {
        printf("%d ", list.r[i].key);
    }
    printf("\n");

    return 0;
}

二、堆排序

• 从简单选择排序可见，选择排序的主要操作是进行关键字间的比较，因此改进简单选择排序应从如何减少“比较”出发考虑。显然，在n个关键字中选出最小值， 至少进行n-1次比较，然而，进行在剩余的n-1个关键字中选择次小值并一定要进行n-2次比较，若能利用前n-1次比较所得信息，则可减少以后各趟排序中所用的比较次数。

• 堆排序就是基于这种思想，对简单选择排序进行了改进。 堆排序是一种树形选择排序，在排序过程中，将待排序的记录r[1..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系， 在当前无序的序列中选择关键字最大(或最小)的记录。

• 首先给出堆的定义。 n个元素的序列{k1,k2,..,kn}称之为堆，当且仅当满足以下条件时：

  1. k(i) >= k(2i)且k(i) >= k(2i+1)
  2. k(i) <= k(2i)且k(i) <= k(2i+1)

• 若将和此序列对应的一维数组(即以一维数组做此序列的存储结构)看成一个完全二叉树，则堆实质上是满足如下性质的完全二叉树：树中所有非终端结点的值均不大于(或不小于)其左、右孩子结点的值。

• 显然，在这两种堆中，堆顶元素(或完全二叉树的根)必须为序列中n个元素的最大值(或最小值)，分别称之为大根堆和小根堆。

• 堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得当前无序的序列中选择关键最大(或最小)的记录变得简单。下面讨论用大根堆进行排序，堆排序的思想如下：
  1. 按堆的定义将待排序序列r[1..n]调整为大根堆(这个过程称为建初堆)，交换r[1]和r[n]，则r[n]为关键字最大的记录。
  2. 将r[1..n-1]重新调整为堆，交换r[1]和r[n-1]，则r[n-1]为关键字次大的记录。
  3. 循环n-1次，直到交换了r[1]和r[2]为止，得到一个非递减的有序序列r[1..n]。
• 同样，可以通过构造小根堆得到一个非递增的有序序列。由此，实现堆排序需要解决如下两个问题：
  1. 建初堆：如何将一个无序序列建成一个堆？
  2. 调整堆：去掉堆顶元素，在堆顶元素改变之后，如何调整剩余元素成为一个新的堆？
• 因为建初堆要用到调整堆的操作，所以先讨论调整堆的实现。

1.调整堆算法

• 先看一个例子，图(a)是一个堆，将堆顶元素97和堆中最后一个元素交换后，如图(b)所示。由于此时除根结点外，其余结点均满足堆的性质，由此仅需要自上至下进行一条路径上的结点调整即可。首先以堆顶元素38和其左右子树根结点的值进行比较，由于左子树根结点的值大于右子树根结点的值且大于根结点的值，则将38和76交换；由于38代替了76之后破坏了左子树的“堆”，则需进行上述相同的调整，直至叶子结点，调整后的状态如图(c)所示。重复上述过程，将堆顶元素76和堆中最后一个元素27交换且调整，得到图(d)所示的新的堆。

• 上述过程就像过筛子一样，把较小的关键字逐层筛下去，而较大的关键字逐层选上来。因此，称此方法为“筛选法”。假设r[s+1..m]已经是堆的情况下，按“筛选法”将r[s..m]调整为以r[s]为根的堆，算法实现如下。
• 从r[2s]和r[2s+1]中选出关键字较大者，假设r[2s]的关键字较大，比较r[s]和r[2s]的关键字。
  1. 若r[s]>=r[2s]，说明r[s]为根的子树已经是堆，不必做任何调整。
  2. 若r[s]<r[s2]，交换r[s]和r[2s]。交换后，以r[2s+1]为根的子树仍是堆，如果以r[2s]为根的子树不是堆，则重复上述过程，将以r[2s]为根的子树调整为堆，直至进行到叶子结点为止。

void HeadAdjust(SqList* L, int s, int m)
{//假设r[s+1..m]已经是堆，将r[s..m]调整为以r[s]为根的大根堆
    RedType rc = L->r[s];
    for (int j = 2 * s; j <= m; j *= 2)     //沿key较大的孩子结点向下筛选
    {
        if (j < m && L->r[j].key < L->r[j + 1].key) ++j;       //j为key较大的记录的下标
        if (rc.key >= L->r[j].key) break;             //rc应插入到位置s上
        L->r[s] = L->r[j];
        s = j;                  //重复上述过程              
    }
    L->r[s] = rc;
}

2.建初堆算法

• 要建立一个无序序列调整为堆，就必须将其所对应的完全二叉树中以每一结点的子树都调整为堆，显然，只有一个结点的树必为堆，而在完全二叉树中，所有序号大于 [n/2]的结点都是叶子，因此这些结点为根的子树均已是堆，这样，只需利用筛选法，从最后一个分支点[n/2]，依次将序号为[n/2]、[n/2]-1...、1的结点左为根的子树都调整为堆即可。算法实现如下。
• 对于无序序列r[1..n]，从i=n/2开始，反复调用筛选法HeapAdjust(r,i,n),依次将r[i]，r[i-1]，...，r[1]为根的子树调整为堆。

   void CreatHeap(SqList *L) 
   {//把无序序列r[1..n]建成大根堆
		int n = L->length;
		for(int i=n/2; i>0; --i) //反复调用HeapAdjust
		{
			HeapAdjust(L,i,n);
		}
   }

3.堆排序算法排序

• 根据前面堆排序算法思想的描述，可知堆排序就是将无序序列建成初堆以后，反复进行交换和堆调整。在建初堆和调整堆算法实现的基础上，下面给出堆排序算法的实现。
• 例如：已知待排序记录的关键字序列为{49,38,65,97,76,13,27,49}，给出堆排序法进行排序的过程。
• 首先将无序序列建初堆，过程如上图3所示。在初始大根堆的基础上，反复交换堆顶元素和最后一个元素，然后重新调整堆，直至最后得到一个有序序列，整个堆排序过程如下图4所示。

void HeapSort(SqList *L)
{
	//对顺序表r进行堆排序
	CreatHeap(L);           //把无序序列r[1..Lenght-1]建成大根堆
	int x;                           
	for(int i=L->length-1; i>1; --i)           
	{ 
		x=L->r[1];                    //将堆顶记录和当前未经排序子序列r[1..i]中最后一个记录互换
		L->r[1]=L->r[i];                
		L->r[i]=x;
		HeapAdjust(L,1,i-1); 		//将r[1..i-1]重新调整为大根堆
	}
}

4.性能分析

• 时间复杂度
  1. 堆排序的运行时间主要耗费在建初堆和调整堆时的反复“筛选”上。
  2. 设有n个记录的初始序列所对应的完全二叉树的深度为h，建初堆时，每个非终端结点都要自上而下进行筛选。由于第i层上的结点数小于2^(i-1),且第i层结点最大下移的深度为h-i，每下移一层要做两次比较，所以建初堆时关键字总的比较次数为 (推理)<=4n。
  3. 调整建新推时要做n-1次“筛选”，每次“筛选”都要将根结点下移到合适的位置。n个结点的完全二叉树深度[log2(n)]+1，则重建堆时关键字总的比较次数不超过 2([log2(n-1)]+[log2(n-2)+...+log2(2)])<2n([log2(n)])
  4. 由此，堆排序在最坏情况下，其时间复杂度也为O(nlog2(n))。实验研究表明，平均性能接近于最坏性能。
• 空间复杂度
  1. 仅需一个记录大小供交换用的辅助存储空间，所以空间复杂度为O(1)。
• 算法特点
  1. 是不稳定排序。
  2. 只能用于顺序结构，不能用于链式结构。
  3. 初始建堆所需的比较次数较多，因此记录数少时不宜采用。堆排序在最坏情况下时间复杂度为O(nlog2(n))，相对于快速排序最坏情况下的O(n^2)而言是一个优点，当记录较多时较为高效。

5.完整代码

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 20 //用于要排序数组个数最大值，可根据需要修改
typedef int KeyType;
typedef struct {
    KeyType key; // 关键字项
} RedType;

typedef struct {
    RedType r[MAXSIZE + 1]; //用于存储要排序的数组，r[0]闲置用作哨兵单元
    int length;             //用于记录顺序变的长度
} SqList;

void HeadAdjust(SqList* L, int s, int m)
{//假设r[s+1..m]已经是堆，将r[s..m]调整为以r[s]为根的大根堆
    RedType rc = L->r[s];
    for (int j = 2 * s; j <= m; j *= 2)     //修正这里的循环条件
    {
        if (j < m && L->r[j].key < L->r[j + 1].key) ++j;   //为key较大的记录的下标
        if (rc.key >= L->r[j].key) break;      //rc应插入到位置s上
        //重复上述过程
        L->r[s] = L->r[j];
        s = j;
    }
    L->r[s] = rc;
}

void CreatHeap(SqList* L)
{//把无序序列r[1..n]建成大根堆
    int n = L->length;
    for (int i = n / 2; i > 0; --i)//反复调用HeapAdjust
    {
        HeadAdjust(L, i, n);
    }
}

void HeapSort(SqList* L)
{
    CreatHeap(L);//把无序序列r[1..Lenght-1]建成大根堆
    for (int i = L->length; i >= 1; --i)
    {//堆顶记录和当前未经排序子序列r[1..i]中最后一个记录互换
        RedType x = L->r[1];
        L->r[1] = L->r[i];
        L->r[i] = x;
        HeadAdjust(L, 1, i - 1);//将r[1..i-1]重新调整为大根堆
    }
}

int main() {
    SqList list;
    list.length = 8;
    list.r[1].key = 49;
    list.r[2].key = 38;
    list.r[3].key = 65;
    list.r[4].key = 97;
    list.r[5].key = 76;
    list.r[6].key = 13;
    list.r[7].key = 27;
    list.r[8].key = 49;

    printf("排序前：");
    for (int i = 1; i <= list.length; i++) {
        printf("%d ", list.r[i].key);
    }
    printf("\n");

    HeapSort(&list);

    printf("排序后：");
    for (int i = 1; i <= list.length; i++) {
        printf("%d ", list.r[i].key);
    }
    printf("\n");

    return 0;
}

No.5归并排序

一、归并排序

• 归并排序就是将两个或两个以上的有序表合并成一个有序表的过程。将两个有序表合并成一个有序表的过程称为2-路归并。
• 假设初始序列含有n个记录，则可看成n个有序的子序列，每个字序列的长度为1，然后两两归并，得到[n/2]个长度为2或1的有序子序列；再两两归并，...，如此重复，直到一个长度为n的有序序列为止。
• 例如：已知待排序记录的关键字序列为{49,38,65,97,76,13,27}，给出2-路归并排序法进行排序的过程
• 2-路归并排序中的核心操作是，将待排序序列中前后相邻的两个有序序列归并为一个有序序列。

1.相邻两个有序子序列的归并算法

• 设两个有序表存放在同一数组中相邻的位置上：R[low..mid]和R[mid+1..high]，每次分被从两个表中取出一个记录进行关键字的比较，将较小者放入T[low..high]中，重复此过程，直至其中一个表为空，最后将另一非空表中余下的部分直接复制到T中。
• 假设每个子序列的长度为h，则一趟归并排序需要调用[n/2h]次算法merge进行两两归并，得到前后相邻、长度为2h的有序段，整个归并排序序进行[log2n]趟。与快速排序类似，2-路归并排序也可以利用划分为子序列的方法递归实现。首先把整个待排序序列划分为两个长度大致相等的子序列，对这两个子序列分别递归地进行排序，然后再把他们归并。典型的分治思想，分解，解决，合并。

void Merge(RedType R[], RedType T[], int low, int mid, int high)
{
    //将有序表R[low..mid]和R[mid+1..high]归并为有序表T[low..high]
    int i = low;
    int j = mid + 1;
    int k = low;
    while (i <= mid && j <= high)    //将R中记录由小到大的并入T中
    {
        if (R[i].key <= R[j].key) T[k++] = R[i++];
        else T[k++] = R[j++];
    }
    while (i <= mid) T[k++] = R[i++];//将剩余的R[i..mid]复制到T中
    while (j <= high) T[k++] = R[j++];//将剩余的R[j..high]复制到T中
}

2.归并排序算法

• 2-路归并排序将R[low..high]中的记录归并排序后放入T[low..high]中。当序列长度等于1时，递归结束，否则：
  1. 将当前序列一分为二，求出分裂点mid=(low+high)/2。
  2. 对子序列R[low..mid]递归，进行归并排序，结果放入S[low..mid]中。
  3. 对子序列R[mid+1..high]递归，进行归并排序，结果放入S[mid+1..high]中。
  4. 调用算法Merge，将有序的两个子序列S[low..mid]和S[mid+1..high]归并为一个有序的序列T[low..high];

void MSort(RedType R[], RedType T[], int low, int high)
{
    //R[low..high]归并排序后放入T[low..high]中
    int S[101];  //辅助数组
    if (low == high)
        T[low] = R[low];
    else
    {
        int mid = (low + high) / 2;           //将当前序列一分为二,求出分裂点mid
        MSort(R, S, low, mid);         //对子序列R[low..mid]递归归并排序,结果放入S[low..mid]
        MSort(R, S, mid + 1, high);      //对子序列R[mid+1..high]递归归并排序,结果放入S[mid+1..high]
        Merge(S, T, low, mid, high);    //将S[low..mid]和S[mid+1..high]归并到T[low..high]
    }
}

void MergeSort(SqList* L)
{
    MSort(L->r, L->r, 1, L->length);
}

3.性能分析

• 时间复杂度
  1. 当有n个记录时，需进行[log2n]趟归并排序，每一趟归并，其关键字比较次数不超过n，元素移动次数都是n。
  2. 因此,归并排序的时间复杂度为O(nlog2n)。
• 空间复杂度
  1. 用顺序表实现归并排序时，需要和待排序记录个数相等的辅助存储空间。
  2. 所以空间复杂度为O(n)。

4.完整代码

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 20 //用于要排序数组个数最大值，可根据需要修改
typedef int KeyType;
typedef struct {
    KeyType key; // 关键字项
} RedType;

typedef struct {
    RedType r[MAXSIZE + 1]; //用于存储要排序的数组，r[0]闲置用作哨兵单元
    int length;             //用于记录顺序变的长度
} SqList;

void Merge(RedType R[], RedType T[], int low, int mid, int high)
{
    //将有序表R[low..mid]和R[mid+1..high]归并为有序表T[low..high]
    int i = low;
    int j = mid + 1;
    int k = low;
    while (i <= mid && j <= high)    //将R中记录由小到大的并入T中
    {
        if (R[i].key <= R[j].key) T[k++] = R[i++];
        else T[k++] = R[j++];
    }
    while (i <= mid) T[k++] = R[i++];//将剩余的R[i..mid]复制到T中
    while (j <= high) T[k++] = R[j++];//将剩余的R[j..high]复制到T中
}

void MSort(RedType R[], RedType T[], int low, int high)
{
    //R[low..high]归并排序后放入T[low..high]中
    int S[101];  //辅助数组
    if (low == high)
        T[low] = R[low];
    else
    {
        int mid = (low + high) / 2;           //将当前序列一分为二,求出分裂点mid
        MSort(R, S, low, mid);         //对子序列R[low..mid]递归归并排序,结果放入S[low..mid]
        MSort(R, S, mid + 1, high);      //对子序列R[mid+1..high]递归归并排序,结果放入S[mid+1..high]
        Merge(S, T, low, mid, high);    //将S[low..mid]和S[mid+1..high]归并到T[low..high]
    }
}

void MergeSort(SqList* L)
{
    MSort(L->r, L->r, 1, L->length);
}

int main() {
    SqList list;
    list.length = 8;
    list.r[1].key = 49;
    list.r[2].key = 38;
    list.r[3].key = 65;
    list.r[4].key = 97;
    list.r[5].key = 76;
    list.r[6].key = 13;
    list.r[7].key = 27;
    list.r[8].key = 49;

    printf("排序前：");
    for (int i = 1; i <= list.length; i++) {
        printf("%d ", list.r[i].key);
    }
    printf("\n");

    MergeSort(&list);

    printf("排序后：");
    for (int i = 1; i <= list.length; i++) {
        printf("%d ", list.r[i].key);
    }
    printf("\n");

    return 0;
}

No.6基数排序

• 基数排序是和前面所述各类排序方法完全不相同的一种排序方法。前述各类排序方法都是建立在关键字比较的基础上，而基数排序不比较关键字的大小，它是根据关键字中各位的值，通过对待排序记录进行若干趟“分配”与“收集”来实现排序的，是一种借助于多关键字排序的思想对单关键字排序的方法。

一、基数排序

1.多关键字的排序

• 先看一个具体例子。已知扑克牌中52张牌的次序关系为
  ♣2<♣3<...<♣A<♦2<♦3<...<♦A<♥2<♥3<...<♥A<♠2<♠3<...<♠A
• 每一张牌有两个“关键字”:花色(♣<♦<♥<♠)和面值(2<3<...<A)，且“花色”的地位高于“面值”，在比较任意两种牌面的大小时，必须先比较“花色”，若“花色”相同，则再比较面值。
• 由此，将扑克牌整理成如上所述次序关系时，有以下两种排序法：
  1. 最高位优先法：先按不同“花色”分成有次序的4堆，每一堆的牌均具有相同的“花色”，然后分别对每一堆按“面值”大小整理有序
  2. 最低位优先法：这是一种“分配”与“收集”交替进行的方法。
• 先按不同“面值”分成13堆。
• 然后将这13堆牌自小至大叠在一起(“3”在“2”之上，“4”在“3”之上，...，最上面的4张“A”)。
• 然后将每堆按照面值的次序收集到一起，再重新对这些牌按不同“花色”分成4堆。
• 最后将这4堆牌按花色的次序再收集到一起(♣在最下面，♠在最上面)。

2.链式基数排序

• 基数排序的思想类似于上述“最低位优先法”的洗牌过程，是借助“分配”和“收集”两种操作对单逻辑关键字进行排序的一种内部排序方法。有的逻辑关键字可以看成由若干个关键字复合而成的。
• 例如，若关键字是数值，且其值都在0<=K<=999范围内，则可把每一个十进制数字看成一个关键字，即可认为K由3个关键字(K0,K1,K2)组成，其中K0是百位数，K1是十位数，K2是个位数；又若关键字K是由5个字母组成的单词，则可看成是由5个关键字(K0,K1,K2,K3,K4)组成，其中K(j-1)是(自左至右的)第j个字母。由于如此分解而得的每个关键字Kj都在相同范围内(对数字，0<=Kj<=9，对字母‘A’<=Kj<=‘Z’)，故可以按照“分配”和“收集”的方法进行排序。
• 假设记录的逻辑关键字由d个“关键字”组成，每个关键字可能去rd个值。只要从最低数位关键字起，按关键字的不同值将序列中记录“分配”到rd个队列中后再“收集”之，如此重复d次完成排序。按照这种方法实现排序称之为基数排序，其中“基”指的是rd的取值范围，在上述两种关键字的情况下，rd分别为“10”和“26”。
• 具体实现时，一般采用链式基数排序。
• 先看一个具体的例子。首先以链表存储n个待排记录，并令表头指针指向第一个记录，如图(a)所示，然后通过以下三趟“分配”和“收集”操作来完成排序。
• 在第一趟分配对最低数位关键字(个位数)进行，改变记录的指针值将链表中的记录分配到10个链队列中去，每个队列中的关键字的个数相等，如图(b)所示，其中f[i]和e[i]分别为第i队列的头指针和尾指针；第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列中的记录链成一个链表，如图(c)所示；
• 第二趟分配和第二趟收集是对十位数进行的，其过程和个位数相同。分配和收集结果分别如图(d)和图(e)所示。
• 第三趟分配和第三趟收集是对百位数进行的，过程同上，分配和收集结果分别如图(f)和图(g)所示。至此排序完毕

• 算法实现时采用静态链表，以便于更有效地存储和重排记录。相关数据类型的定义如下：

#define MAXNUM_KEY 8          /* 关键字项数的最大值 */
#define RADIX 10              /* 关键字基数，此时是十进制整数的基数 */
#define MAX_SPACE 10000
typedef int KeyType;
typedef int InfoType;

typedef struct
{
	KeyType keys[MAXNUM_KEY];    /* 关键字 */
	InfoType otheritems;          /* 其他数据项 */
	int next;
}SLCell;                      /* 静态链表的结点类型*/
typedef struct
{
	SLCell r[MAX_SPACE];      /* 静态链表的可利用空间，r[0]为头结点*/
	int keynum;               /* 记录的当前关键字个数 */    
	int recnum;               /* 静态链表的当前长度 */
}SLList;                      /* 静态链表类型 */ 
typedef int ArrType[RADIX]    /* 指针数组类型 */

3.基数排序算法

int ord(KeyType key) {
    return key % RADIX; // 简单的取余操作，用于将关键字映射到[0..RADIX-1]
}

int succ(int j) {
    return j + 1; // 简单的后继操作，用于找到下一个子表
}

/* 分配 */
void Distribute(SLCell* r, int i, ArrType f, ArrType e)
{
    /* 静态链表L的r域中记录已按(keys[0],...,keys[i-1])有序 */
    /* 本算法按照第i个关键字建立RADIX个子表，使同一子表中记录的keys[i]相同 */
    /* f[0..RADIX-1]和e[0..RADIX-1]分别指向各子表中第一个和最后一个记录 */
    for (int j = 0; j < RADIX; ++j)          /* 各子表初始化为空表 */
        f[j] = 0;
    for (int p = r[0].next; p; p = r[p].next)
    {
        int j = ord(r[p].keys[i]);      /* ord将记录中第i个关键字映射到[0..RADIX-1] */
        if (!f[j])
            f[j] = p;
        else
            r[e[j]].next = p;
        e[j] = p;                   /* 将p所指的结点插入第j个子表中 */
    }
}

/* 收集 */
void Collect(SLCell* r, int i, ArrType f, ArrType e)
{
    /* 本算法按keys[i]自小至大地将f[0..RADIX-1]所指各子表依次链接成一个链表 */
    /* e[0..RADIX-1]为各子表的尾指针 */
    int j;
    for (j = 0; !f[j]; j = succ(j));      /* 找到第一个非空子表，succ为求后继函数 */
    r[0].next = f[j];
    int t = e[j];             /* r[0].next指向一个非空子表中的第一个结点 */
    while (j < RADIX)
    {
        for (j = succ(j); j < RADIX - 1 && !f[j]; j = succ(j));
        if (f[j])
        {
            r[t].next = f[j];
            t = e[j];
        }
    }
    r[t].next = 0;
}

void RadixSort(SLList* L)
{
    /* L是采用静态链表表示的顺序表 */
    /* 对L做基数排序，使得L成为按关键字自小到大的有序静态链表,L.r[0]为头结点 */
    ArrType f, e; // 声明辅助数组
    for (int i = 0; i < L->recnum; ++i)
        L->r[i].next = i + 1;
    L->r[L->recnum].next = 0;                 /* 将L改造为静态链表 */
    for (int i = 0; i < L->keynum; ++i)           /* 按最低位优先依次对各关键字进行分配和收集 */
    {
        Distribute(L->r, i, f, e);            /* 第i趟分配 */
        Collect(L->r, i, f, e);              /* 第i趟收集 */
    }
}

4.性能分析

• 时间复杂度
  1. 对于n个记录(加色每个记录含d个关键字，每个关键字的取值范围为rd个值）进行链式基数排序时，每一趟分配的时间复杂度为O(n)，每一趟收集的时间复杂度为O(rd)，整个排序需进行d趟分配和收集，所以时间复杂度为O(d(n+rd))。
• 空间复杂度
  1. 所需辅助空间为2rd个队列指针，另外由于需用链表做存储结构，则相对于其他以顺序结构存储记录的排序方法而言，还增加了n个指针域的空间，所以空间复杂度为O(n+rd)。
• 算法特点
  1. 是稳定排序。
  2. 可用于链式结构，也可用于顺序结构。
  3. 时间复杂度可以突破基于关键字比较一类方法的下界(nlog2n)，达到O(n)。
  4. 基数排序可使用条件有严格的要求：需要知道各级关键字的主次关系和各级关键字的取值范围。

No.7排序性能分析总结

• 从表的时间复杂度的平均情况来看，直接插入排序、冒泡排序和简单选择排序的速度较慢，而其他排序方法的速度较快。从算法实现的角度来看，速度较慢的算法实现过程比较简单，称之为简单的排序方法；而速度较快的算法可以看做是对某一排序算法的改进(Shell是由直接插入改进、堆排序是由直接选择改进、快速排序是由冒泡排序改进)，称之为先进的排序方法，但这些算法实现比较复杂。总体来看，各种排序算法各有优缺点，没有哪一种是绝对最优的。在使用时需根据不用情况适当选用，甚至可将多种方法结合起来使用。一般综合考虑以下因素：
  1. 待排序的记录个数。
  2. 记录本身的大小。
  3. 关键字的结构及初始状态。
  4. 对排序稳定性的要求。
  5. 存储结构。
• 根据这些因素和上表所做的比较，可以得出以下几点结论。
  1. 当待排序的记录个数n较小时，n^2和nlog2n的差别不大，可以选用简单的排序方法。
  2. 而当关键字基本有序时，可选用直接插入排序或冒泡排序，排序速度很快，其中直接插入排序最为简单常用、性能最佳。
  3. 当n较大时，应该选用先进的排序方法。对于先进的排序方法，从平均时间性能而言，快速排序最佳，是目前基于比较的排序方法中最好的方法。但在最坏情况下，即当关键字基本有序时，快速排序的递归深度为n，时间复杂度为O(n^2)，空间复杂度为O(n)。堆排序和归并排序不会出现快速排序的最坏情况，但归并排序的辅助空间较大。这样，当n较大时，具体的选用原则是：
     1. 当关键字分布随机，稳点性不做要求时，可采用快速排序。
     2. 当关键字基本有序，稳点性不做要求时，可采用堆排序。
     3. 当关键字基本有序，内存允许且要求排序稳点时，可采用归并排序。
  4. 可以将简单的排序方法和先进的排序方法结合。例如，当n较大时，可以先将待排序序列划分成若干子序列，分别进行直接插入排序，然后再利用归并排序，将有序子序列合并成一个完整的有序序列。或者，在快速排序中，当划分区间的长度小于某值时，可以转而调用直接插入排序。
  5. 基数排序的时间复杂度也可以写成O(d*n)。因此，它适用于n值很大而关键字较小的序列。若关键字很大，而序列中的大多数记录的“最高位关键字”均不同，则亦可先按“最高位关键字”不同将序列分成若干个“小”的子序列，而后进行直接插入排序。但基数排列使用条件有严格的要求：需要知道各级关键字的主次关系和各级关键字的取值范围，即只适用于像整数和字符这类有明显结构特征的关键字，当关键字的取值范围为无穷集合时，则无法使用基数排序。
  6. 由于大多数情况下是按记录的主关键字进行的，则所用的排序方法是否稳定无关紧要。若排序按记录的次关键字进行，则必须采用稳定的排序方法。一般来说，如果排序的过程中的”比较”是在“相邻的两个记录关键字”间进行的，则排序方法是稳定的。值得提出的是，稳定性是由方法本身提出的，证明一种排序方法是否稳定的，要从算法本身的步骤中加以证明；而证明排序方法是不稳定的，只需要列出一个不稳定的实例来说明。
  7. 平时在讨论排序方法中，多数采用顺序表实现的。若记录本身信息量较大，为避免移动记录耗费大量时间，可以采用链式结构。比如直接插入排序、归并排序都易于在链表上实现。但像折半插入排序、希尔排序、快速排序和堆排序，却难于在链表上实现。

热门相关：总裁别再玩了   后福   大妆   豪门情变，渣总裁滚远点！   本法官萌萌哒