数据结构实验9各种排序算法.docx

1、数据结构实验9各种排序算法9.1 实现希尔排序算法一， 实验目的 1.熟悉掌握各种排序算法，深刻理解各种排序算法及其执行的过程；2.学会分析各种排序算法的过程和性能。二， 实验内容9.1 实现希尔排序算法编写一个程序实现希尔排序，dk=5,3,1，并输出6,9,7,8,0,1,3,2,4,5的排序过程。9.2 实现快速排序算法编写一个程序实现快速排序，并输出49,38,65,97,76,13,27,49的排序过程（要求输出每次枢轴记录到位后的关键字序列）。9.3 实现堆排序算法编写一个程序实现堆排序，并输出49,38,65,97,76,13,27,49的排序过程（要求输出初始堆、第一个记录与堆

2、尾交换后、重新调整成堆，直至排好序后的关键字序列）。三， 源代码及结果截图9.1/9.1 实现希尔排序算法#includeusing namespace std;#define MAX 10void ShellSorts(int sorts,int dk) /一次希尔排序 int temp,j,i; cout希尔排序过程：endl; for(i=dk;isortsi) temp=sortsi; sortsi=sortsi-dk; for(j=i-dk;j=0&sortsjtemp;j-=dk) sortsj+dk=sortsj; sortsj+dk=temp; for(i=0;iMAX;i+)

3、 coutsortsi ; coutendl;int dlta=5,3,1; /希尔排序的DKvoid SHELL(int sorts,int dk) /希尔排序 for(int k=0;k3;k+) ShellSorts(sorts,dltak);void ShowSorts(int a) /显示排序后的结果 int i=0; for(i;iMAX;i+) coutai ; coutendl;void main() int SMAX=6,9,7,8,0,1,3,2,4,5; /待排序数组 /int JGMAX=0,1,2,3,4,5,6,7,8,9; /正确排序结果，方便自己看的 int j

4、=0; cout待排序数组: endl; for(j;jMAX;j+) coutSj ; coutendl; SHELL(S,dlta); /希尔排序 cout希尔排序后的结果: endl; ShowSorts(S); /显示拍完序后的数组9.2/9.2 实现快速排序算法#include #define MAXE 20 /线性表中最多元素个数 typedef int KeyType;typedef char InfoType8;typedef struct /记录类型 KeyType key; /关键字项 InfoType data; /其他数据项,类型为InfoType RedType;vo

5、id QuickSort(RedType R,int l,int h) /对Rs至Rt的元素进行快速排序 int i=l,j=h,k; RedType temp; if (li & Rj.keytemp.key) j-; /从右向左扫描,找第个关键字小于temp.key的Rj if (ij) /*表示找到这样的Rj,Ri、Rj交换*/ Ri=Rj; i+; while (ij & Ri.keytemp.key) i+; /从左向右扫描,找第个关键字大于temp.key的记录Ri if (ij) /表示找到这样的Ri,Ri、Rj交换/ Rj=Ri; j-; Ri=temp; printf( );

6、 /输出每一趟的排序结果 for (k=0;k8;k+) if (k=i) printf( %d,Rk.key); else printf(%4d,Rk.key); printf(n); QuickSort(R,l,i-1); /对左区间递归排序 QuickSort(R,i+1,h); /对右区间递归排序 void main() int i,k,n=8; KeyType a=49,38,65,97,76,13,27,49; RedType RMAXE; for (i=0;in;i+) Ri.key=ai; printf(n); printf( 初始关键字:); /输出初始关键字序列 for (

7、k=0;kn;k+) printf(%4d,Rk.key); printf(n); QuickSort(R,0,n-1); printf( 快速排序结果： ); /输出初始关键字序列 for (k=0;kn;k+) printf(%4d,Rk.key); printf(nn);9.3/9.3实现堆排序算法#includevoid HeapAdjust(int data,int s,int m) /* 排列成堆的形式 */ int j,rc; rc=datas; /* 保存处理元素 */ for(j=2*s;j=m;j*=2) /* 处理父亲元素 */ if(jm & datajdataj) b

8、reak; datas=dataj; /* 父节点比较大的孩子节点大则互换 ,保证父节点比所有子节点都大（父节点存储在前面）*/ s=j; datas=rc; /* 相当于dataj=rc */void DispHeap(int R,int i,int n) /*以括号表示法输出建立的堆*/ if (i=n) coutRi; /*输出根结点*/ if (2*i=n | 2*i+1n) cout(; if (2*i=n) DispHeap(R,2*i,n); /*递归调用输出左子树*/ cout,; if (2*i+1=n) DispHeap(R,2*i+1,n); /*递归调用输出右子树*/

9、cout0;-i) HeapAdjust(data,i,long_n); /* 处理后，datai是这个数组后半部分的最大值 */ cout 初始堆:; DispHeap(data,1,long_n);cout0;-i) /*进行n-1次循环,完成推排序*/ cout 交换 datai与data1 输出 data1endl; temp=data1; /* 把根元素（剩下元素中最大的那个）放到结尾 ,下一次只要排剩下的数就可以啦*/ data1=datai; datai=temp; HeapAdjust(data,1,i-1); cout 筛选调整得到堆:; DispHeap(data,1,i-

10、1);coutendl; /*输出每一趟的排序结果*/ void main() int i,k,n=8; int a=49,38,65,97,76,13,27,49; int R20; for (i=1;i=n;i+) Ri=ai-1; coutendl; cout 初始关键字: ; for (k=1;k=n;k+) coutRk ; cout=1;i-) /循环建立初始堆 HeapAdjust(R,i,n); Heap_sort(R,n); cout 最终结果: ; /输出最终结果 for (k=1;k=n;k+) coutRk ; coutendl; 四，实验小结1、 通过本次实验，加深了我各种排序算法的认识。2、 将待排序列建成堆（初始堆生成）后，序列的第一个元素（堆顶元素）就一定是序列中的最大元素； 将其与序列的最后一个元素交换，将序列长度减一；再将序列建成堆（堆调整）后，堆顶元素仍是序列中的最大元素，再次将其与序列最后一个元素交换并缩短序列长度；反复此过程，直至序列长度为一，所得序列即为排序后结果。