2022年数据结构排序问题C语言 .pdf

《2022年数据结构排序问题C语言 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构排序问题C语言 .pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构排序算法（C描述） (1)冒泡排序； (2)选择排序； (3)插入排序； (4)快速排序； (5)堆排序； (6)归并排序；#include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR #define OVERFLOW -2 #define MAXSIZE 20 /一个用作示例的小顺序表的最大长度#define LT(a,b) (a)(b) #define LQ(a,b) (a)=(b) typedef int KeyType;/定义关键字类型为整数类型typedef int InfoType;

2、typedef struct KeyType key;/关键字项InfoType otherinfo;/其他数据项RedType;/ 记录类型typedef struct 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 9 页 - - - - - - - - - RedType rMAXSIZE+1;/r0闲置或用作哨兵单元int length;/顺序表长度SqList;/顺序表类型int InitList_Sq(SqList &L) / 构造一个空的顺序表L。int i

3、; printf(请输入待排序的记录的个数：); scanf(%d,&L.length); printf(请输入待排序的记录的关键字（整型数）：); for(i=1;i=L.length;i+) scanf(%d,&L.ri); return OK; void Print_Sq(SqList &L) /输出 int i; for(i=1;i=L.length;i+) printf(%4d,L.ri); printf(n); /-插入排序 - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - -

4、 第 2 页，共 9 页 - - - - - - - - - void InsertSort(SqList &L) / 对顺序表 L 作直接插入排序。int i,j; for(i=2;i=L.length;+i) if(LT(L.ri.key,L.ri-1.key)/“”，需将 L.ri插入有序子表 L.r0=L.ri;/复制为哨兵L.ri=L.ri-1; for(j=i-2;LT(L.r0.key,L.rj.key);-j) L.rj+1=L.rj;/记录后移L.rj+1=L.r0;/插入到正确位置 /-冒泡排序 - void BubbleSort(SqList &L) /L.r是待排序的文

5、件，采用自下向上扫描，对L.r 做冒泡排序int i,j; int exchange; / 交换标志for(i=1;i=i;j-) / 对当前无序区 Ri.n 自下向上扫描if(LT(L.rj+1.key,L.rj.key) / 交换记录名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 9 页 - - - - - - - - - L.r0=L.rj+1; /L.r0不是哨兵，仅做暂存单元L.rj+1=L.rj; L.rj=L.r0; exchange=TRUE; / 发生了

6、交换，故将交换标志置为真 if(!exchange) / 本趟排序未发生交换，提前终止算法return; /-快速排序 - int Partition(SqList &L,int low,int high) / 交换顺序表 L 中子表 rlow.high的记录，枢轴记录到位，并返回其所在位置，此时/ 在它之前（后）的记录均不大（小）于它。KeyType pivotkey; L.r0=L.rlow;/用子表的第一个记录作枢轴记录pivotkey=L.rlow.key;/枢轴记录关键字while(lowhigh) / 从表的两端交替地向中间扫描while (low=pivotkey) -high;

7、 L.rlow=L.rhigh;/将比枢轴记录小的记录移到低端while (lowhigh&L.rlow.key=pivotkey) +low; L.rhigh=L.rlow;/将比枢轴记录大的记录移到高端 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 9 页 - - - - - - - - - L.rlow=L.r0;/枢轴记录到位return low;/返回枢轴位置 void QSort(SqList &L,int low,int high) / 对顺序表 L 中的

8、子序列 L.rlow.high进行快速排序int pivotloc; if(lowhigh) / 长度大于 1 pivotloc=Partition(L,low,high);/将 L.rlow.high一分为二QSort(L,low,pivotloc-1);/对低子表递归排序pivotloc是枢轴位置QSort(L,pivotloc+1,high);/对高子表递归排序 void QuickSort(SqList &L) / 对顺序表 L 作快速排序。QSort(L,1,L.length); /-归并排序 - void Merge(RedType SR,RedType TR,int i,int

9、m,int n) / 将有序的 SRi.m 和 SRm+1.n 归并为有序的 TRi.n int j,k; for(j=m+1,k=i;i=m&j=n;+k) / 将 SR中记录由小到大地并入TR if LQ(SRi.key,SRj.key) TRk=SRi+; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 9 页 - - - - - - - - - else TRk=SRj+; if(i=m)/TRk.n=SRi.m;将剩余的 SRi.m 复制到 TR while(k

10、=n&i=m) TRk+=SRi+; if(j=n)/将剩余的 SRj.n复制到 TR while(k=n&j=n) TRk+=SRj+; void MSort(RedType SR,RedType TR1,int s,int t) / 将 SRs.t归并排序为 TR1s.t。int m; RedType TR220; if(s=t) TR1t = SRs; else m=(s+t)/2;/将 SRs.t平分为 SRs.m 和 SRm+1.t MSort(SR,TR2,s,m);/递归地将 SRs.m 归并为有序的 TR2s.m MSort(SR,TR2,m+1,t);/将 SRm+1.t 归

11、并为有序的 TR2m+1.t Merge(TR2,TR1,s,m,t);/将 TR2s.m 和 TR2m+1.t 归并到 TR1s.t void MergeSort(SqList &L) / 对顺序表 L 作归并排序。MSort(L.r, L.r, 1, L.length); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 9 页 - - - - - - - - - /-堆排序 - void HeapAdjust(SqList &H,int s,int m) / 已知 H

12、.rs.m中记录的关键字除H.rs.key之外均满足堆的定义，/ 本函数调整 H.rs的关键字，使 H.rs.m成为一个大顶堆/ （对其中记录的关键字而言）int j; RedType rc; rc=H.rs; for(j=2*s;j=m;j*=2) / 沿 key 较大的孩子结点向下筛选if(jm&H.rj.key=H.rj.key) break;/rc应插入在位置 s 上H.rs=H.rj; s=j; H.rs=rc;/插入 void HeapSort(SqList &H) / 对顺序表 H进行堆排序。int i; RedType temp; for(i=H.length/2;i0;-i)

13、/把 H.r1.H.length建成大顶堆HeapAdjust(H,i,H.length); for(i=H.length;i1;-i) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 9 页 - - - - - - - - - temp=H.ri; H.ri=H.r1; H.r1=temp;/将堆顶记录和当前未经排序子序列Hr1.i中/ 最后一个记录相互交换HeapAdjust(H,1,i-1);/将 H.r1.i-1重新调整为大顶堆 void main() SqLis

14、t S; printf(- 五种排序算法 -n); InitList_Sq(S); printf( 1.简单插入排序 n); InsertSort(S); Print_Sq(S); printf( 2.冒泡排序 n); BubbleSort(S); Print_Sq(S); printf( 3.快速排序 n); QuickSort(S); Print_Sq(S); printf( 4.归并排序 n); MergeSort(S); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 9 页 - - - - - - - - - Print_Sq(S); printf( 5.堆排序n); HeapSort(S); Print_Sq(S); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 9 页 - - - - - - - - -