数据结构实验(七种排序算法的实现)题目和源程序.doc

《数据结构实验(七种排序算法的实现)题目和源程序.doc》由会员分享，可在线阅读，更多相关《数据结构实验(七种排序算法的实现)题目和源程序.doc（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1、直接插入排序2、希尔排序3、2-路归并排序4、折半插入排序5、冒泡排序6、快速排序7、堆排序/*- * 07_排序.cpp - 排序的相关操作 * 对排序的每个基本操作都用单独的函数来实现 * 水上飘 2011年写 -*/ ds07.cpp : 定义控制台应用程序的入口点。/#include stdafx.h#include stdio.h#include #include using namespace std;#define MAXSIZE 20typedef int KeyType;typedef structKeyType key; /关键字项KeyType data; /数据项R

2、edType; /记录类型typedef structRedType arrMAXSIZE+1; /arr0闲置或用作哨兵单元int length; /顺序表长度SqList; /顺序表类型typedef SqList HeapType;/对顺序表L做一趟希尔插入排序/前后记录位置的增量是dk/r0只是暂存单元/当j=0时，插入位置已找到void shellInsert(SqList &L, int dk)int i, j;for (i = dk + 1; i = L.length; i+)if (L.arri.key 0 & L.arr0.key L.arrj.key; j -= dk)L.

3、arrj + dk = L.arrj;/记录后移，查找插入位置/end for jL.arrj + dk = L.arr0;/插入/end if/end for i/shellInsert/按增量序列dlta0.t-1对顺序表做希尔排序void shellSort(SqList &L, int dlta, int t)for (int k = 0;k t; k+)shellInsert(L, dltak);/一趟增量为dltak的插入序列/折半插入排序void bInsertSort(SqList &L)for (int i = 2; i = L.length; i+)L.arr0 = L.a

4、rri;/将其暂存到arr0int low = 1;int high = i - 1;while(low = high)/在arrlow.high中折半查找有序插入的位置int m = (low + high) / 2;/折半if(L.arr0.key = high + 1; j-)L.arrj + 1 = L.arrj;/记录后移L.arrhigh + 1 = L.arr0;/插入/for/BInsertSort/直接插入排序void insertSort(SqList &L)for(int i = 2; i = L.length; i+)if(L.arri.key L.arri-1.key

5、)/if,需将L.arri插入有序子表L.arr0 = L.arri;/复制为哨兵L.arri = L.arri-1;int j;for(j = i - 2; L.arr0.key L.arrj.key; j-)L.arrj+1 = L.arrj;/记录后移L.arrj+1 = L.arr0;/插入到正确位置/if/for/InsertSort/冒泡排序void bubbleSort(SqList &L)RedType* temp = NULL;for(int i = 1; i L.length; i+)/第i趟排序for(int j = 1; j L.arrj+1.key)/交换前后的位置L

6、.arr0 = L.arrj;L.arrj = L.arrj+1;L.arrj+1 = L.arr0;/if/for j/for i/bubbleSort/交换顺序表中子表L.arrlow.high的记录,/枢轴记录到位,并返回其所在位置int partition(SqList &L, int low, int high)L.arr0 = L.arrlow;/子表的第一个记录做枢轴记录KeyType pivotKey = L.arrlow.key;/枢轴记录关键字while(low high)/从表的两端交替向中间扫描while(low = pivotKey)high-;/whileL.arr

7、low = L.arrhigh;/将比枢轴小的记录移到低端while(low high & L.arrlow.key = pivotKey)low+;/whileL.arrhigh = L.arrlow;/将比枢轴大的记录移到高端/whileL.arrlow = L.arr0;/枢轴记录到位return low;/返回枢轴位置/paitition/对顺序表L中的子序列L.arrlow.high做快速排序void qSort(SqList &L, int low, int high)if(low high)/长度大于1KeyType pivotLoc = partition(L, low, hi

8、gh);/将L.arrlow.high一分为二qSort(L, low, pivotLoc-1);/对低子表递归排序，pivotLoc是枢轴位置qSort(L, pivotLoc+1, high);/对高子表递归排序/if/qSort/对顺序表L做快速排序void quickSort(SqList &L)qSort(L, 1, L.length);/quickSort/调整H.arrs的关键字，使H.arrs.m成为一个大顶堆/（对其中记录的关键字而言）void heapAdjust(HeapType &H, int s, int m)RedType rc = H.arrs;for(int j

9、 = 2 * s; j = m; j = j * 2)/沿key较大的孩子结点向下筛选if(j m & H.arrj.key H.arrj+1.key)j+;/j为key叫大记录的下标/ifif(!(rc.key 0; i-)/把H.arr1.H.length建成大顶堆heapAdjust(H, i, H.length);/forfor(int i = H.length; i 1; i-)/将堆记录当前未经排序的子序列H.arr1.i中的最后一个记录交换H.arr0 = H.arr1;H.arr1 = H.arri;H.arri = H.arr0;heapAdjust(H, 1, i-1);/

10、将H.arr1.i-1重新调整为大顶堆/for/heapSort/将有序的SRi.m和SRm+1.n归并为有序的TRi.nvoid Merge(RedType SR, RedType *TR, int i, int m, int n)int j, k;for (j = m + 1, k = i; i = m & j = n; k+)/将SR中记录由小到大地并入TRif (SRi.key = SRj.key)TRk = SRi+;elseTRk = SRj+;/end for j,kif (i = m)/将剩余的SRi.m复制到TRfor (; k = n & i = m; k+, i+)TRk

11、 = SRi;/end if iif (j = n)/将剩余的SRj.n复制到TRfor (; k = n & j = n; k+, j+)TRk = SRj;/end if j/Merge/将SRs.t归并排序为TR1s.tvoid MSort(RedType SR, RedType TR1, int s, int t)int m;RedType TR2MAXSIZE;if (s = t)TR1s = SRs; elsem = (s + t) /2;/将SRs.t平分为SRs.m和SRm+1.tMSort(SR, TR2, s, m);/递归地将SRs.m归并为有序的TR2s.mMSort(

12、SR, TR2, m+1, t);/递归地将SRm+1.t归并为有序的TR2m+1.tMerge(TR2, TR1, s, m, t);/将TR2s.m和TR2m+1.t归并到TR1s.t/MSort/对顺序表L做归并排序void mergeSort(SqList &L)MSort(L.arr, L.arr, 1, L.length);/mergeSort/初始化顺序表，给其赋值void setValue(SqList &L)KeyType data8 = 49,38,65,97,76,13,27,49;int n = 8;L.arr0.data = 0;L.length = n;for(in

13、t i = 1; i = L.length; i+)L.arri.data = datai-1;L.arri.key = L.arri.data;/end for i/setValue/输出顺序表void show(SqList &L)for(int i = 1; i = L.length; i+)if(i % 5 = 0)cout endl;cout setw(5) L.arri.data;cout endl;/show/调用排序函数进行排序void performance(SqList &L)cout 原始序列： endl;show(L);SqList LI = L;insertSort(

14、LI);cout 直接插入排序结果： endl;show(LI);SqList LS = L;int dlta3 = 4,3,1;int t = 3;shellSort(LS, dlta, t);cout 希尔排序结果： endl;show(LS);SqList LM = L;mergeSort(LM);cout 2-路归并排序结果： endl;show(LM);SqList LB = L;bInsertSort(LB);cout 折半插入排序结果： endl;show(LB);SqList LBB = L;bubbleSort(LBB);cout 冒泡排序结果： endl;show(LBB);SqList LQ = L;cout 快速排序结果： endl;quickSort(LQ);show(LQ);HeapType H = L;cout 堆排序结果： endl;heapSort(H);show(H);/performanceint _tmain(int argc, _TCHAR* argv)SqList L;setValue(L);performance(L);system(pause);return 0;