当前位置： 首页 > news >正文

《数据结构（C语言版）第二版》第八章-排序（8.5-归并排序、8.6基数排序、8.7 外部排序）

news 来源：原创 2024/9/20 4:43:59

8.5 归并排序 (Merging Sort)

【基本思想】
将两个或两个以上的有序表合并成一个有序表的过程。

将两个有序表合并成一个有序表的过程称为2-路归并，2-路归并最为简单和常用。

假设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到⌈n/2⌉（n/2向上取整）个长度为2 或1 的有序子序列；再两两归并，……， 如此重复，直至得到一 个长度为n 的有序序列为止。

【算法特点】
(1)是稳定排序。
(2)可用于链式结构， 且不需要附加存储空间，但递归实现时仍需要开辟相应的递归工作栈。

#include <stdio.h>
#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;
typedef char InfoType;typedef struct
{KeyType key;InfoType otherinfo;
}RedType;typedef struct
{RedType r[MAXSIZE + 1];  //r[O]闲置或用做哨兵单元int length;
}SqList;void CreateSqList(SqList& L);
void Merge(RedType R[], RedType T[], int low, int mid, int high);
void MSort(RedType R[], RedType T[], int low, int high);
void MergeSort(SqList& L);
void printSqList(SqList L);int main()
{SqList L = { {0},0 };CreateSqList(L);MergeSort(L);printSqList(L);return 0;
}void CreateSqList(SqList& L)
{int i = 0;printf("请输入顺序表的元素个数：");scanf_s(" %d", &L.length);for (i = 1; i <= L.length; i++){printf("请输入第%d个关键字：", i);scanf_s(" %d", &L.r[i].key);}
}//算法8.10 相邻两个有序子序列的归并
//将有序表 R[low...mid]和R[mid+l...high]归并为有序表 T[low...high]
void Merge(RedType R[], RedType T[], int low, int mid, int high)
{int i = low;int j = mid + 1;int k = low;while (i <= mid && j <= high){if (R[i].key <= R[j].key){T[k++] = R[i++];}else{T[k++] = R[j++];}}while (i <= mid){T[k++] = R[i++];}while (j <= high){T[k++] = R[j++];}
}//算法8.11 归并排序
// R[low ... high]归并排序后放人 T[low ... high]中
void MSort(RedType R[], RedType T[], int low, int high)
{if (low == high){T[low] = R[low];}else{int mid = (low + high) / 2;  //将当前序列一分为二， 求出分裂点 mid RedType S[MAXSIZE];      //辅助存储空间SMSort(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]}
}//对顺序表 L 做归并排序
void MergeSort(SqList& L)
{MSort(L.r, L.r, 1, L.length);
}void printSqList(SqList L)
{int i = 0;printf("\n\n排序后的序列为：");for (i = 1; i <= L.length; i++){printf("\nr[%d].key = %d", i, L.r[i].key);}
}

在这里插入图片描述
在这里插入图片描述

8.6 基数排序（分配类）

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

8.6.1 多关键字的排序

在这里插入图片描述

8.6.2 链式基数排序

【基本思想】
(1) 以静态链表存储待排记录，并令表头指针指向第一个记录；
从最低位关键字（对整个值影响最小的关键字）起：
(2) “分配” 时，按当前“关键字位”所取值，将记录分配到不同的 “链队列” 中，每个队列中记录的 “关键字位” 相同；
(3) “收集”时，按当前关键字位取值从小到大将各队列首尾相链成一个链表；
(4) 从低位到高位，对每个关键字位均重复 2 和 3 两步。

【算法特点】
(1)是稳定排序。
(2)可用于链式结构， 也可用于顺序结构。
(3)时间复杂度可以突破基于关键字比较一类方法的下界 O(nlog2n), 达到 O(n)。
(4)基数排序使用条件有严格的要求：需要知道各级关键字的主次关系和各级关键字的取值范围。

8.6.2.1 当逻辑关键字由数字复合而成时

将代码scanf_s 和 printf中的” %c“ 占位符，都改为” %d“
宏定义中#define RADIX 26  改为 10创建静态链表的函数CreateSLList 中//初始化rd数组for (i = 0; i < RADIX; i++){rd[i] = 0;}打印函数中必须加引用符
void printSLList(SLList &L);

个位（优先级最低）：影响最小，即使个位数很大，也不会显著改变元素在整个数组中的位置。
十位（优先级中等）：影响较大，十位数的变化会开始影响元素的位置。
百位（优先级最高）：影响最大，百位数决定了元素的最终位置。
如当关键字是数字，且每个逻辑关键字由三个关键字复合而成时，百位数的地位高于十位数，十位数的地位又高于个位数。
那么最左边的百位数就是最高位数（优先级最高的）关键字，最右边的个位数就是最低位数（优先级最低的）关键字。

#include <stdio.h>
#include <stdlib.h>#define MAXNUM_KEY 8
#define RADIX 10
#define MAX_SPACE 10000typedef int KeysType;
typedef char InfoType;typedef struct
{KeysType keys[MAXNUM_KEY];   //关键字InfoType otheritems;int next;
}SLCell;   //静态链表的结点类型typedef struct
{SLCell r[MAX_SPACE];  //静态链表的可利用空间，r[O]为头结点int keynum;int recnum;
}SLList;    //静态链表类型KeysType rd[RADIX];  //每个关键字的所有可能取值，数组rd的大小即为此基数排序的基为RADIXtypedef int ArrType[RADIX];  //指针数组类型void CreateSLList(SLList& L);
void Distribute(SLCell r[], int i, int f[], int e[]);
int ord(SLCell r[], int i, int p);
void Collect(SLCell r[], int i, int f[], int e[]);
void RadixSort(SLList& L);
void printSLList(SLList &L);int main()
{SLList L = { {0},0,0 };CreateSLList(L);RadixSort(L);printf("\n\n排序后的序列为：");printSLList(L);return 0;
}void CreateSLList(SLList& L)
{int i = 0;int j = 0;printf("请输入静态链表中，逻辑关键字的记录个数：");scanf_s(" %d", &L.recnum);printf("请输入每个逻辑关键字的关键字项数：");scanf_s(" %d", &L.keynum);//初始化rd数组for (i = 0; i < RADIX; i++){rd[i] = 0;}/*	当关键字是数字时，基数RADIX=10，每个关键字可能取的数字为：0，1，...，9，指针数组rd中每个元素的类型为int当关键字是字母时，基数RADIX=26，每个关键字可能取的字母为：A，B，...，Z，指针数组rd中每个元素的类型为char每个 关键字可能取的值 就是一个子表。  */printf("基数（即每个关键字的最大取值范围）：%d", RADIX);printf("\n\n请按从小到大的顺序,依次输入关键字可取的值： \n");for (i = 0; i < RADIX; i++){printf("请输入关键字可能取的第%d个值：", i + 1);scanf_s(" %d", &rd[i]);}/*基数排序的思想是低位优先，而在下面代码实现过程中，RadixSort函数是下标从0开始依次往后，正序依次读取keys数组中的数据的。因此这里存储的时候，必须将按关键字位数从高到低倒着存储，使得最低位关键字在最前面。*/for (i = 1; i <= L.recnum; i++)    //r[O]为头结点，不保存数据{printf("\n请输入第%d个逻辑关键字：\n", i);for (j = L.keynum - 1; j >= 0; j--){printf("请输入第%d个逻辑关键字的第%d个关键字：", i, L.keynum - j);scanf_s(" %d", &L.r[i].keys[j]);}}
}//算法8.12 基数排序
/*  前提：静态链表 L 的 r域中记录已按 (keys[O], …， keys[i-1]) 有序【 keys[i]前面的关键字(keys[O], …， keys[i-1]) 位数都比它低，但已经都经过分配和收集，变得有序了。每个关键字记录中的keys[i]，是待分配的最低位关键字。 】本算法按第i个关键字keys[i]建立 RADIX 个子表，使同一子表中记录的keys[i]相同。  */
void Distribute(SLCell r[], int i, int f[], int e[])
{//f[O ...RADIX - 1]和 e[O ... RADIX - 1]分别指向各子表中第一个和最后一个记录int j = 0;int p = 0;for (j = 0; j < RADIX; ++j){f[j] = 0;   //各子表初始化为空表e[j] = 0;}//p初始值指向静态链表L中第一个结点r[1]（序列中的第一个逻辑关键字）//静态链表L中最后一个结点的后继为0，即指向头结点r[0]（头结点中不保存数据）for (p = r[0].next; p; p = r[p].next){j = ord(r, i, p);//ord将记录r[p]中第i个关键字映射到[0 .. RADIX-1]//f[j]指向 数组rd中下标为j的关键字 子表中的第一个记录if (!f[j]){f[j] = p;//【*】例如keys[i]为8，当在关键字8（在rd数组中的下标也为8）的子表中还没有记录时，使得f[8]指向 该第一个 keys[i]为8记录p}else{//【*】否则的话，就使得该记录p 成为  指针e[8]的后继结点（指针e[8]指向该子表的最后一个记录）r[e[j]].next = p;//如此，就将所有记录中第i个关键字keys[i]相同的记录，都放在该子表keys[i]中//直接在静态链表L 的r域中进行修改，使得 第i个关键字keys[i]相同的记录 可以通过静态链表L结点的next域被连续获取到}//令e[j]重新指向子表keys[i]中的最后一个记录pe[j] = p;}
}//将记录r[p]中第i个关键字映射到[0 .. RADIX-1]
int ord(SLCell r[], int i, int p)
{KeysType k = r[p].keys[i];int j = 0;//寻找k在rd数组中的下标for (j = 0; j < RADIX; j++){if (rd[j] == k){return j;}}return -1;}//本算法按 keys[i]自小至大地将f[O.. RADIX-1]所指各子表依次链接成一个链表
void Collect(SLCell r[], int i, int f[], int e[])
{//e[O .. RADIX-1]为各子表的尾指针int j = 0;int t = 0;//找第一个非空子表for (j = 0; j < RADIX && !f[j]; j++){;}//使r[O].next指向第一个非空子表中第一个结点r[0].next = f[j];t = e[j];while (j < RADIX){//找下一个非空子表for (j = j + 1; j <= RADIX - 1 && !f[j]; j++)  //注意是两个条件，及其准确性{;}//链接两个非空子表if (f[j] && j <= RADIX - 1)   //注意是两个条件，及其准确性{r[t].next = f[j];t = e[j];}else if (j >= RADIX)  //一定要增加推出while循环的语句{break;}}//t指向最后一个非空子表中的最后一个结点r[t].next = 0;
}//L是采用静态链表表示的顺序表
//对 L 做基数排序，使得 L 成为按关键字自小到大的有序静态链表， L.r[O]为头结点，不存储记录
void RadixSort(SLList& L)
{int i = 0;int f[RADIX] = { 0 };int e[RADIX] = { 0 };for (i = 0; i < L.recnum; ++i){L.r[i].next = i + 1;  //将 L 改造为静态链表}L.r[L.recnum].next = 0;//最后一个记录关键字的后继置为0【静态链表中第一个结点r[0]为头结点，不保存任何数据，因此这里相当于最后一个结点的后继为空】for (i = 0; i < L.keynum; ++i)  //按最低位优先依次对各关键字进行分配和收集{Distribute(L.r, i, f, e);  //这里的第一个i = 0,而不是L.keynum-1，说明最低为关键字在keys数组中的第一位Collect(L.r, i, f, e);  //没有用到i,仅仅是一个标志，说明讨论的是第i个关键字/进行的是第i趟收集printf("\n第%d趟分配和收集之后，序列的顺序为：", i + 1);printSLList(L);}
}void printSLList(SLList &L)
{int i = 1;int j = 0;int p = 0;for (p = L.r[0].next; p ; p = L.r[p].next)    //r[O]为头结点，不保存数据{printf("\n第%d个逻辑关键字：", i);for (j = L.keynum - 1; j >= 0; j--){printf("%d", L.r[p].keys[j]);}i++;}
}

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

8.6.2.2 当逻辑关键字由字母复合而成时

#include <stdio.h>
#include <stdlib.h>#define MAXNUM_KEY 8
#define RADIX 26
#define MAX_SPACE 10000typedef char KeysType;
typedef char InfoType;typedef struct
{KeysType keys[MAXNUM_KEY];   //关键字InfoType otheritems;int next;
}SLCell;   //静态链表的结点类型typedef struct
{SLCell r[MAX_SPACE];  //静态链表的可利用空间，r[O]为头结点int keynum;int recnum;
}SLList;    //静态链表类型KeysType rd[RADIX];  //每个关键字的所有可能取值，数组rd的大小即为此基数排序的基为RADIXtypedef int ArrType[RADIX];  //指针数组类型void CreateSLList(SLList& L);
void Distribute(SLCell r[], int i, int f[], int e[]);
int ord(SLCell r[], int i, int p);
void Collect(SLCell r[], int i, int f[], int e[]);
void RadixSort(SLList& L);
void printSLList(SLList L);int main()
{SLList L = { {0},0,0 };CreateSLList(L);RadixSort(L);printf("\n\n排序后的序列为：");printSLList(L);return 0;
}void CreateSLList(SLList& L)
{int i = 0;int j = 0;printf("请输入静态链表中，逻辑关键字的记录个数：");scanf_s(" %d", &L.recnum);printf("请输入每个逻辑关键字的关键字项数：");scanf_s(" %d", &L.keynum);//初始化rd数组for (i = 0; i < RADIX; i++){rd[i] = '\0';}/*	当关键字是数字时，基数RADIX=10，每个关键字可能取的数字为：0，1，...，9，指针数组rd中每个元素的类型为int当关键字是字母时，基数RADIX=26，每个关键字可能取的字母为：A，B，...，Z，指针数组rd中每个元素的类型为char每个 关键字可能取的值 就是一个子表。  */printf("基数（即每个关键字的最大取值范围）：%d", RADIX);printf("\n\n请按从小到大的顺序,依次输入关键字可取的值： \n");for (i = 0; i < RADIX; i++){printf("请输入关键字可能取的第%d个值：", i + 1);scanf_s(" %c", &rd[i]);}/*	基数排序的思想是低位优先，而在下面代码实现过程中，RadixSort函数是下标从0开始依次往后，正序依次读取keys数组中的数据的。因此这里存储的时候，必须将按关键字位数从高到低倒着存储，使得最低位关键字在最前面。   	*/for (i = 1; i <= L.recnum; i++)    //r[O]为头结点，不保存数据{printf("\n请输入第%d个逻辑关键字：\n", i);for (j = L.keynum - 1; j >= 0; j--){printf("请输入第%d个逻辑关键字的第%d个关键字：", i, L.keynum - j);scanf_s(" %c", &L.r[i].keys[j]);}}
}//算法8.12 基数排序
/*  前提：静态链表 L 的 r域中记录已按 (keys[O], …， keys[i-1]) 有序【 keys[i]前面的关键字(keys[O], …， keys[i-1]) 位数都比它低，但已经都经过分配和收集，变得有序了。每个关键字记录中的keys[i]，是待分配的最低位关键字。 】本算法按第i个关键字keys[i]建立 RADIX 个子表，使同一子表中记录的keys[i]相同。  */
void Distribute(SLCell r[], int i, int f[], int e[])
{//f[O ...RADIX - 1]和 e[O ... RADIX - 1]分别指向各子表中第一个和最后一个记录int j = 0;int p = 0;for (j = 0; j < RADIX; ++j){f[j] = 0;   //各子表初始化为空表e[j] = 0;}//p初始值指向静态链表L中第一个结点r[1]（序列中的第一个逻辑关键字）//静态链表L中最后一个结点的后继为0，即指向头结点r[0]（头结点中不保存数据）for (p = r[0].next; p; p = r[p].next){j = ord(r, i, p);//ord将记录r[p]中第i个关键字映射到[0 .. RADIX-1]//f[j]指向 数组rd中下标为j的关键字 子表中的第一个记录if (!f[j]){f[j] = p;//【*】例如keys[i]为8，当在关键字8（在rd数组中的下标也为8）的子表中还没有记录时，使得f[8]指向 该第一个 keys[i]为8记录p}else{//【*】否则的话，就使得该记录p 成为  指针e[8]的后继结点（指针e[8]指向该子表的最后一个记录）r[e[j]].next = p;//如此，就将所有记录中第i个关键字keys[i]相同的记录，都放在该子表keys[i]中//直接在静态链表L 的r域中进行修改，使得 第i个关键字keys[i]相同的记录 可以通过静态链表L结点的next域被连续获取到}//令e[j]重新指向子表keys[i]中的最后一个记录pe[j] = p;}
}//将记录r[p]中第i个关键字映射到[0 .. RADIX-1]
int ord(SLCell r[], int i, int p)
{KeysType k = r[p].keys[i];int j = 0;//寻找k在rd数组中的下标for (j = 0; j < RADIX; j++){if (rd[j] == k){return j;}}return -1;}//本算法按 keys[i]自小至大地将f[O.. RADIX-1]所指各子表依次链接成一个链表
void Collect(SLCell r[], int i, int f[], int e[])
{//e[O .. RADIX-1]为各子表的尾指针int j = 0;int t = 0;//找第一个非空子表for (j = 0; j < RADIX && !f[j]; j++){;}//使r[O].next指向第一个非空子表中第一个结点r[0].next = f[j];t = e[j];while (j < RADIX){//找下一个非空子表for (j = j + 1; j <= RADIX - 1 && !f[j]; j++)  //注意是两个条件，及其准确性{;}//链接两个非空子表if (f[j] && j <= RADIX - 1)   //注意是两个条件，及其准确性{r[t].next = f[j];t = e[j];}else if (j >= RADIX)  //一定要增加推出while循环的语句{break;}}//t指向最后一个非空子表中的最后一个结点r[t].next = 0;
}//L是采用静态链表表示的顺序表
//对 L 做基数排序，使得 L 成为按关键字自小到大的有序静态链表， L.r[O]为头结点，不存储记录
void RadixSort(SLList& L)
{int i = 0;int f[RADIX] = { 0 };int e[RADIX] = { 0 };for (i = 0; i < L.recnum; ++i){L.r[i].next = i + 1;  //将 L 改造为静态链表}L.r[L.recnum].next = 0;//最后一个记录关键字的后继置为0【静态链表中第一个结点r[0]为头结点，不保存任何数据，因此这里相当于最后一个结点的后继为空】for (i = 0; i < L.keynum; ++i)  //按最低位优先依次对各关键字进行分配和收集{Distribute(L.r, i, f, e);  //这里的第一个i = 0,而不是L.keynum-1，说明最低为关键字在keys数组中的第一位Collect(L.r, i, f, e);  //没有用到i,仅仅是一个标志，说明讨论的是第i个关键字/进行的是第i趟收集printf("\n第%d趟分配和收集之后，序列的顺序为：",i+1);printSLList(L);}
}void printSLList(SLList L)
{int i = 1;int j = 0;int p = 0;for (p = L.r[0].next; p; p = L.r[p].next)    //r[O]为头结点，不保存数据{printf("\n第%d个逻辑关键字：", i);for (j = L.keynum - 1; j >= 0; j--){printf("%c ", L.r[p].keys[j]);}i++;}
}

在这里插入图片描述

在这里插入图片描述

8.7 外部排序

基本思想：
外部排序基本上由两个相对独立的阶段组成。
（1）首先， 按可用内存大小， 将外存上含n个记录 的文件分成若干长度为 l 的子文件或段 (segment), 依次读入内存并利用有效的内部排序方法对它们进行排序， 并将排序后得到的有序子文件重新写入外存， 通常称这些有序子文件为归并段或 顺串(run);
（2）然后， 对这些归并段进行逐趟归并， 使归并段（有序的子文件）逐渐由小至大， 直至得到整个有序文件为止。

为减少归并中外存读写的次数，提高外排序的效率，一般通过增大归并路数和减少初始归并段个数两种方案对归并算法进行改进，

8.7.2 多路平衡归并排序的实现—增大归并路数

归并段的个数/路数，即k值的选择并非越大越好， 如何选择合适的k是一个需要综合考虑的问题。
主要是要用 败者树 这种方法，从k个记录中选出最小的，来实现k-路归并。

多路平衡归并排序 —— C语言中文网

8.7.3 置换－选择排序—减少初始归并段个数

置换选择排序算法详解 —— C语言中文网

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • Baumer工业相机堡盟工业相机如何通过BGAPI SDK设置相机的图像剪切（ROI）功能（C语言）
  • thrift与dubbo对比
  • 《OpenCV计算机视觉》—— 图像轮廓检测与绘制
  • 在Deepin上安装Cursor
  • Rust运算符
  • Nacos1.X中对NacosNamingService的实现
  • Google大数据架构技术栈
  • HOT 100（七）栈、堆、贪心算法
  • 定时任务和延时任务
  • 前端页面中使用 ppt 功能，并且可以随意插入关键帧
  • uniapp的苹果全屏播放再退出会导致页面字体变大解决方法
  • C语言代码练习（第二十三天）
  • 【Hot100】LeetCode—169. 多数元素
  • Python 课程6-Pandas 和 Matplotlib库
  • 102.WEB渗透测试-信息收集-FOFA语法（2）
  • 【跃迁之路】【477天】刻意练习系列236（2018.05.28）
  • FastReport在线报表设计器工作原理
  • gitlab-ci配置详解(一)
  • gops —— Go 程序诊断分析工具
  • jquery cookie
  • js递归,无限分级树形折叠菜单
  • node-sass 安装卡在 node scripts/install.js 解决办法
  • webpack项目中使用grunt监听文件变动自动打包编译
  • 给github项目添加CI badge
  • 记一次用 NodeJs 实现模拟登录的思路
  • 紧急通知：《观止-微软》请在经管柜购买！
  • 如何邀请好友注册您的网站(模拟百度网盘)
  • 新版博客前端前瞻
  • 学习笔记DL002:AI、机器学习、表示学习、深度学习，第一次大衰退
  • 走向全栈之MongoDB的使用
  • elasticsearch-head插件安装
  • 测评：对于写作的人来说，Markdown是你最好的朋友 ...
  • 如何在 Intellij IDEA 更高效地将应用部署到容器服务 Kubernetes ...
  • ​ 全球云科技基础设施：亚马逊云科技的海外服务器网络如何演进
  • ​LeetCode解法汇总2182. 构造限制重复的字符串
  • ​MySQL主从复制一致性检测
  • ​软考-高级-系统架构设计师教程（清华第2版）【第9章 软件可靠性基础知识（P320~344）-思维导图】​
  • # Panda3d 碰撞检测系统介绍
  • # Redis 入门到精通（七）-- redis 删除策略
  • （1）STL算法之遍历容器
  • (31)对象的克隆
  • (70min)字节暑假实习二面（已挂）
  • （9）目标检测_SSD的原理
  • （C语言）共用体union的用法举例
  • （利用IDEA+Maven）定制属于自己的jar包
  • （一）Kafka 安全之使用 SASL 进行身份验证 —— JAAS 配置、SASL 配置
  • （转）创业家杂志：UCWEB天使第一步
  • .java 9 找不到符号_java找不到符号
  • .mat 文件的加载与创建 矩阵变图像？ ∈ Matlab 使用笔记
  • .NET 6 在已知拓扑路径的情况下使用 Dijkstra，A*算法搜索最短路径
  • .Net Winform开发笔记（一）
  • .NET/C# 使用 ConditionalWeakTable 附加字段（CLR 版本的附加属性，也可用用来当作弱引用字典 WeakDictionary）
  • .NET6使用MiniExcel根据数据源横向导出头部标题及数据
  • .Net6支持的操作系统版本(.net8已来，你还在用.netframework4.5吗)
  • .NET框架设计—常被忽视的C#设计技巧