第九章 排序【数据结构】【精致版】

前言

2023-11-7 16:23:34
以下内容源自《【数据结构】【精致版】》
仅供学习交流使用

版权

禁止其他平台发布时删除以下此话
本文首次发布于CSDN平台
作者是CSDN@日星月云
博客主页是https://jsss-1.blog.csdn.net
禁止其他平台发布时删除以上此话

第九章 排序

9.1 概述

记录序列的数据类型描述如下

#define MAXSIZE 1000  //假设的文件长度,即待排序的记录数目  
typedef int KeyType;  //假设的关键字类型
typedef int OtherType;
typedef struct{KeyType key;//关键字项OtherType other_data;//其他数据项,类型OtherType依赖于具体应用而定义  
}RecordType; //记录类型
typedef struct{RecordType r[ MAXSIZE+1];int length;//序列长度,即记录个数
}RecordList; //记录序列类型,即顺序表类型RecordList create(int nums[],int n){RecordList L;L.length=n;for(int i=1;i<=n;i++){RecordType t={nums[i],0};L.r[i]=t;}return L;
}void print(RecordList L){int n=L.length;for(int i=1;i<=n;i++){printf("%d ",L.r[i].key);}printf("\n");
}

9.2 插入类排序

9.2.1 直接插入排序

1-直接插入排序.c

#include <stdio.h>
#include "0-RecordList.h"// 【算法9-1】直接插入排序
RecordList insertSort(RecordList L){for (int i = 2; i <= L.length; i++){L.r[0] = L.r[i]; // 监视哨备份待查记录int j;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]; // 插入正确位置}return L;
}// 待插记录已是当前有序的最大记录，不需要后移排序
// 【算法9-2】改进的直接插入排序
RecordList insertSortPlus(RecordList L){for (int i = 2; i <= L.length; i++){if (L.r[i].key < L.r[i - 1].key){      // 如果不小于，就是待插记录已是当前有序的最大记录L.r[0] = L.r[i]; // 监视哨备份待查记录int j;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]; // 插入正确位置}}return L;
}

int main(){int n=8;int nums[9]={-1,33,12,25,46,33,68,19,80};//0号不存储元素 RecordList L=create(nums,n);print(L);//33 12 25 46 33 68 19 80print(insertSort(L)); //12 19 25 33 33 46 68 80  print(insertSortPlus(L)); //12 19 25 33 33 46 68 80}

9.2.2 折半插入排序

2-折半插入排序.c

#include <stdio.h>
#include "0-RecordList.h"//【算法9-3】折半插入排序
//因为插入到有序列中，有折半快速找到位置
RecordList biInsertSort(RecordList L){for (int i = 2; i <=L.length ; i++) {if(L.r[i].key<L.r[i-1].key){//如果不小于，就是待插记录已是当前有序的最大记录L.r[0]=L.r[i];//监视哨备份待查记录//折半查找nums[i]插入位置int low=1;int high=i-1;while (low<high){int mid=(low+high)/2;if(L.r[0].key<L.r[mid].key){high=mid-1;}else{low=mid+1;}}for (int j = i-1; j>=low; j--) {L.r[j+1]=L.r[j];//记录后移}L.r[low]=L.r[0];//插入正确位置}}return L; 
}

int main(){int n=8;int nums[9]={-1,33,12,25,46,33,68,19,80};//0号不存储元素 RecordList L=create(nums,n);print(L);//33 12 25 46 33 68 19 80print(biInsertSort(L)); //12 19 25 33 33 46 68 80   }

9.2.3 希尔排序

#include <stdio.h>
#include "0-RecordList.h"#include <stdio.h>
#include "0-RecordList.h"//【算法9-4】希尔排序
//最小增量排序
void shellInsert(RecordList* L,int dk){for (int i = dk+1; i<=L->length ; i++) {if(L->r[i].key<L->r[i-1].key){//如果不小于，就是待插记录已是当前有序的最大记录L->r[0]=L->r[i];//监视哨备份待查记录int j;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];//插入正确位置}}
}
//dlta 增量序列
void shellSort(RecordList* L,int dlta[],int t){//t为增量序列的长度for (int k=0;k<t;k++){shellInsert(L,dlta[k]);}
}

int main(){int n=8;int nums[9]={-1,46,25,68,33,33,19,12,80};//0号不存储元素 RecordList L=create(nums,n);print(L);//46 25 68 33 33 19 12 80//    int dlta[3]={4,2,1};int dlta[3]={7,3,1};int t=3;shellSort(&L,dlta,t); print(L);//12 19 25 33 33 46 68 80 
}

9.3 交换类排序

9.3.1冒泡排序

4-冒泡排序.c

#include <stdio.h>
#include "0-RecordList.h"//【算法9-5】冒泡排序
RecordList bubbleSort(RecordList L){for (int i = 1; i <= L.length; i++) {for (int j = 1; j <=L.length-i ; j++) {if(L.r[j].key>L.r[j+1].key){RecordType temp=L.r[j];L.r[j]=L.r[j+1];L.r[j+1]=temp;}}}return L; 
}//【算法9-6】改进冒泡排序
//如已排好序，直接跳出
RecordList bubbleSortPlus(RecordList L){int flag=1;for (int i = 1; i <= L.length&&flag; i++) {flag=0;for (int j = 1; j <=L.length-i ; j++) {if(L.r[j].key>L.r[j+1].key){RecordType temp=L.r[j];L.r[j]=L.r[j+1];L.r[j+1]=temp;flag=1;}}}return L;
}

int main(){int n=8;int nums[9]={-1,46,25,68,33,33,19,12,80};//0号不存储元素 RecordList L=create(nums,n);print(L);//46 25 68 33 33 19 12 80print(bubbleSort(L)); 		//12 19 25 33 33 46 68 80      print(bubbleSortPlus(L)); 	//12 19 25 33 33 46 68 80   }

9.3.2 快速排序

5-快速排序.c

#include <stdio.h>
#include "0-RecordList.h"
//【算法9-7】一趟快速排序 
int QKPass(RecordList* L,int low,int high){L->r[0]=L->r[low];//枢轴while(low<high){while (low<high&&L->r[high].key>=L->r[0].key) --high;L->r[low]=L->r[high];while (low<high&&L->r[low].key<L->r[0].key) ++low;L->r[high]=L->r[low];}L->r[low]=L->r[0];return low;
}//【算法9-8】快速排序 
void QKSort(RecordList* L,int low,int high){int pos;if (low<high){pos=QKPass(L, low,high);QKSort(L, low,pos-1);QKSort(L, pos+1,high);}
}

int main(){int n=8;int nums[9]={-1,46,68,12,25,33,80,19,33};//0号不存储元素 RecordList L=create(nums,n);print(L);//46 68 12 25 33 80 19 33   QKSort(&L,1,L.length); 		    print(L);//12 19 25 33 33 46 68 80}

9.4 选择类排序

9.4.1 简单选择排序

6-简单选择排序.c

#include <stdio.h>
#include "0-RecordList.h"//【算法9-9】简单选择排序
RecordList selectSort(RecordList L){for (int i = 1; i <= L.length; i++) {int k=i;for (int j = i+1; j <=L.length ; j++) {if (L.r[j].key<L.r[k].key){//k是擂台k=j;}}if (k!=i){RecordType temp=L.r[i];L.r[i]=L.r[k];L.r[k]=temp;}}return L;}

int main(){int n=8;int nums[9]={-1,33,68,46,33,25,80,19,12};//0号不存储元素 RecordList L=create(nums,n);print(L);//33 68 46 33 25 80 19 12print(selectSort(L)); 		//12 19 25 33 33 46 68 80   }

9.4.2 树形选择排序

9.4.3 堆排序

7-堆排序.c

#include <stdio.h>
#include "0-RecordList.h"//【算法9-10】堆的筛选
void HeapAdjust(RecordList* L,int s,int m){//已知L[s..m]中记录的关键字除L[s]之外均满足堆的定义//本函数调整L[s]的关键字，使L[s..m]成为小顶堆RecordType t=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(t.key<=L->r[j].key){break;}//t应该插入位置sL->r[s]=L->r[j];s=j;}L->r[s]=t;
}
//【算法9-11】建立初始堆
void CreatHeap(RecordList* L){int len=L->length;for (int i=len/2;i>=1;i--){HeapAdjust(L,i, len);}
}
//【算法9-12】堆排序
void HeapSort(RecordList* L){CreatHeap(L);int len= L->length;for (int i = len; i >=2 ; i--) {L->r[0]=L->r[1];L->r[1]=L->r[i];L->r[i]=L->r[0];HeapAdjust(L,1,i-1);}
}

int main(){int n=8;int nums[9]={-1,46,12,33,72,68,19,80,33};//0号不存储元素 RecordList L=create(nums,n);print(L);//46 12 33 72 68 19 80 33   HeapSort(&L); 		   print(L);//80 72 68 46 33 33 19 12
}

9.5 归并类排序

9.5.1 二路归并排序

8- 二路归并排序.c

#include <stdio.h>
#include "0-RecordList.h"void Merge(RecordList* ,RecordList* ,int ,int ,int );//【算法9-13】二路归并排序
void MergeSort(RecordList* L,RecordList* CopyL,int left,int right){//对上下限值分别为left和right的记录序列L进行归并排序//其中copyL为同类型的记录，由于复制保存原记录序列int middle;if(left<right){middle=(left+right)/2;//找中间位置进行划分MergeSort(L,CopyL,left,middle);//对左半部分进行递归归并排序MergeSort(L,CopyL,middle+1,right);//对右半部分进行递归 归并排序Merge(L,CopyL,left,right,middle);//进行归并}
}//【算法9-14】二路归并排序
void Merge(RecordList* L,RecordList* CopyL,int left,int right,int middle){int i,p1,p2;for (i=left;i<=right;i++){//用copyL记录临时保存待排序记录序列CopyL->r[i]=L->r[i];}p1=left;//左半部分有序记录的起始位置p2=middle+1;//右半部分有序记录的起始位置i=left;//左半部分开始进行归并while(p1<=middle&&p2<=right){//取两个有序半区中关键字较小的记录if (CopyL->r[p1].key<=CopyL->r[p2].key){L->r[i]=CopyL->r[p1];//去较小的记录放到合并后的记录序列中p1++;} else{L->r[i]=CopyL->r[p2];p2++;}i++;}//剩下的序列无论是左半部分还是右半部分都直接复制到合并后的记录序列中while (p1<=middle){L->r[i]=CopyL->r[p1];i++;p1++;}while (p2<=middle){L->r[i]=CopyL->r[p2];i++;p2++;}}int main(){int n=8;int nums[9]={-1,46,12,33,72,68,19,80,33};//0号不存储元素 RecordList L=create(nums,n);print(L);//46 12 33 72 68 19 80 33RecordList CopyL=create(nums,n);MergeSort(&L,&CopyL,0,n); 		   print(L);//12 19 33 33 46 68 72 80
}

9.5.2自然归并排序

9-自然归并排序.c

#include <stdio.h>
#include <stdlib.h> 
#include "0-RecordList.h"//【算法9-15】自然归并排序
//将两个有序的子序列R[low..m]和R[m+1..high]归并成一个有序的子序列R[low..high]
void Merge(RecordType* R,int l,int m,int r){int i=l,j=m+1,p=0,q;RecordType *R1;R1=(RecordType*) malloc((r-l+1)*sizeof(RecordType));if(!R1) return;//申请空间失败 while (i<=m&&j<=r){//取两个有序半区中关键字较小的记录if(R[i].key<=R[j].key){R1[p++]=R[i++];}else {R1[p++]=R[j++];}}//剩下的序列无论是左半部分还是右半部分都直接复制到合并后的记录序列中if (i>m){for (q = j; q <=r ; q++) {R1[p++]=R[q];}}else {for (q=i;q<=m;q++){R1[p++]=R[q];}}for (p=0,i=l;i<=r;p++,i++){R[i]=R1[p];//归并完成后将结果复制回R[low..high]}
}
void NatureMergeSort(RecordType R[],int n){int i,sum,low,mid,high;while (1){i=0;sum=1;while (i<n-1){low=i;while (i<n-1&&R[i].key<R[i+1].key){ i++; }mid=i++;while (i<n-1&&R[i].key<R[i+1].key){ i++; }high=i++;if (i<=n){Merge(R,low,mid,high);sum++;}}if (sum==1) break;}}

int main(){int n=8;int nums[9]={-1,12,24,5,8,3,9,11,7};//0号不存储元素 RecordList L=create(nums,n);print(L);//12 24 5 8 3 9 11 7RecordList CopyL=create(nums,n);NatureMergeSort(L.r,9); 		   print(L);//3 5 7 8 9 11 12 24
}

9.6 分配类排序

9.6.1 多关键字排序

10-多关键字排序.c

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <time.h>
/*
Heart 红桃 
Spade 黑桃 
club  梅花 
diamond 方块 
*/
//花色的枚举类 
typedef enum color{D=1,C,S,H
}Color; 
//扑克的定义 
typedef struct card{Color color;int num;
}Card;
//输出花色 
void printColor(Color c){switch(c){case H: printf("红桃");break;case S: printf("黑桃");break;case C: printf("梅花");break;case D: printf("方块");break;}
}
//输出扑克 
void printCard(Card card){printColor(card.color);printf("%-2d",card.num);
} //创建一幅扑克 
void creatCards(Card cards[52]){	int colors[4]={D,C,S,H};int nums[13]={1,2,3,4,5,6,7,8,9,10,11,12,13};int n=0;for(int i=0;i<4;i++){for(int j=0;j<13;j++){Card card;card.color=colors[i];card.num=nums[j];cards[n]=card;   n++;  }}
//    printCards(cards);
}
//洗牌 
void shuffleCards(Card cards[52]){	srand((unsigned)time(NULL));//用srand()函数来重新播种，用time来充当随机数种子 creatCards(cards);	//交换52次 for (int i=0;i<52;i++){int r1=rand()%52;//rand()函数产生的随机数是伪随机数 ，和种子有关 int r2=rand()%52;//交换两张牌 Card temp=cards[r1];cards[r1]=cards[r2];cards[r2]=temp;}} 
//打印扑克牌 
void printCards(Card cards[52]){for(int i=0;i<52;i++){printCard(cards[i]);printf(" ");if(i%13==12){printf("\n");}}
}
//按最高位优先法MSD排序  花色从小到大  数值从小到大 
void sortCardsWithMSD(Card cards[52]){printf("按最高位优先法LSD排序 \n"); //首先按照花色将整副牌分为4组（每组13张牌）Card cardsByColor[4][13];int cardColorCount[4]={0}; //一个计数器数组，用来记录每组花色加入了多少 for (int i=0;i<52;i++){int index=cards[i].color-1; //面值从1开始，索引是从0开始的 cardsByColor[index][cardColorCount[index]]=cards[i];cardColorCount[index]++;		} 
//	printf("测试1\n");
//	for(int i=0;i<4;i++){
//		for(int j=0;j<13;j++){
//			printCard(cardsByColor[i][j]); 
//		}		
//		printf("\n");
//	}//然后每组在按照面值从小到大进行排序 (选择排序） for(int i=0;i<4;i++){		for(int j=0;j<13;j++){int m=j; for(int k=j+1;k<13;k++){if(cardsByColor[i][k].num<cardsByColor[i][m].num){m=k;}}if(m!=j){				Card temp=cardsByColor[i][j];cardsByColor[i][j]=cardsByColor[i][m];cardsByColor[i][m]=temp;}}				}
//	printf("测试2\n");
//	for(int i=0;i<4;i++){
//		for(int j=0;j<13;j++){
//			printCard(cardsByColor[i][j]); 
//		}		
//		printf("\n");
//	}int n=0;//最后将这4组牌收集到一起就是按照花色和面值排好序的有序序列 for(int i=0;i<4;i++){for(int j=0;j<13;j++){cards[n]=cardsByColor[i][j];n++;}		}
}
//按最低位优先法LSD排序  花色从小到大  数值从小到大 
void sortCardsWithLSD(Card cards[52]){printf("按最低位优先法LSD排序 \n"); //第一步 先按照面值大小从小到大将整副牌分为13组（每组4张牌）	Card cardsByNum[13][4];	int cardNumCount[13]={0};//一个计数器数组，用来记录每组面值加入了多少 for (int i=0;i<52;i++){int index=cards[i].num-1;	//面值从1开始，索引是从0开始的 cardsByNum[index][cardNumCount[index]]=cards[i];		cardNumCount[index]++;		} //	printf("测试1\n");
//	for(int i=0;i<13;i++){
//		for(int j=0;j<4;j++){
//			printCard(cardsByNum[i][j]); 
//		}		
//		printf("\n");
//	}//第二步 然后将每组牌按照面值的大小收集到一起   从小到大 Card CollectByNum[52];	int n=0;for(int i=0;i<13;i++){for(int j=0;j<4;j++){CollectByNum[n]=cardsByNum[i][j];n++;}		}
//	printf("测试2\n");
//	printCards(CollectByNum);//第三步 再对这些牌按照花色摆成4组，每组13张牌 		Card cardsByColor[4][13];int cardColorCount[4]={0}; //一个计数器数组，用来记录每组花色加入了多少 for (int i=0;i<52;i++){int index=CollectByNum[i].color-1;cardsByColor[index][cardColorCount[index]]=CollectByNum[i];cardColorCount[index]++;		} 
//	printf("测试3\n");
//	for(int i=0;i<4;i++){
//		for(int j=0;j<13;j++){
//			printCard(cardsByColor[i][j]); 
//		}		
//		printf("\n");
//	}n=0;//第四步 最后再把4组牌按花色的次序收集到一起就是按照花色和面值排好序的有序序列 for(int i=0;i<4;i++){for(int j=0;j<13;j++){cards[n]=cardsByColor[i][j];n++;}		}
//	printf("4");}void sortCardsWithBinSort(Card cards[52]){printf("按桶排序 \n"); //首先按照花色将整副牌分为4组（每组13张牌）	Card cardsByBin[4][13];//然后每组在按照面值从小到大进行排序 (桶排序）for (int n=0;n<52;n++){int i=cards[n].color-1;int j=cards[n].num-1;cardsByBin[i][j]=cards[n];				} int n=0;//最后将这4组牌收集到一起就是按照花色和面值排好序的有序序列 for(int i=0;i<4;i++){for(int j=0;j<13;j++){cards[n]=cardsByBin[i][j];n++;}		}
}void main(){printf("排序 按照花色从小到大  数值从小到大 \n");Card cards[52] ;   printf("洗牌ing.....\n");shuffleCards(cards);	//洗牌 printf("排序前的牌\n");printCards(cards);		//打印扑克牌 printf("排序ing.....\n"); 
//	sortCardsWithLSD(cards);//排序 
//	sortCardsWithMSD(cards);//排序 sortCardsWithBinSort(cards);printf("排序后的牌\n");printCards(cards);		//打印扑克牌 }

9.6.2 链式基数排序

11-链式基数排序.c

#include <stdio.h>
#include <stdlib.h> 
#include "0-RecordList.h"typedef RecordType DataType; 
#include "链队列.c"int digit(KeyType key, int m, int r);//【算法9-16】基于链队列的基数排序
void RadixSort(RecordType L[] ,int n,int m,int r){//L中的关键字为m为r进制数，L的长度为nLQueue** Queue;int i,j,k;Queue=(LQueue**)malloc(r*sizeof(LQueue*));for(i=0;i<r;i++){               //初始化r个链队列Queue[i]=Init_LQueue();}for (i = 0;  i<m ; i++) {       //进行m次分配与收集for (j=0;j<=n;j++){          //分配k=digit(L[j].key,i,r);   //提取当前关键字中第m位的数字值InLQueue(Queue[k],L[j]);}k=0;for (j = 0; j < r; j++) {   //收集for ( ; !Empty_LQueue(Queue[j]); k++) {Out_LQueue(Queue[j],&(L[k]));}}}}
//【算法9-17】提取关键字中第m位的数字值
int digit(KeyType key, int m, int r){int i,d;if(m==0){return key %r;}d=r;for (i = 1;  i<m ; i++) {d*=r;}return ((int)(key/d)%r);
}

int main(){int n=9;int nums[10]={-1,921,435,628,285,862,225,448,193,430};//0号不存储元素 RecordList L=create(nums,n);print(L);//921 435 628 285 862 225 448 193 430RadixSort(L.r,9,3,10); 		   print(L);//193 225 285 430 435 448 628 862 921
}

9.7 外部排序

9.7.1置换选择排序

9.7.2多路归并外排序

9.8 算法总结

最后

2023-11-7 19:26:28

我们都有光明的未来
不必感谢我，也不必记得我

祝大家考研上岸
祝大家工作顺利
祝大家得偿所愿
祝大家如愿以偿
点赞收藏关注哦