北工大数据结构上机实验报告

1、 上机题五报告 增加了计算时间的算法 可以比较各个排序的所用时间 姓名： 学号： 完成日期：2015年6月2日题目：堆排序、快排、基数排序1.1 需求分析1. 程序功能：对于给定的一串数据，可以从小到大排序并计算所用时间。2. 测试数据：1.2 概要设计开始1.2.1 主程序流程结束输出排序结果和时间进行排序输出原始数据 开始1.2.2 模块调用图 归并mergeSort堆排HeapSort快排QuickSort输出结果计算时间输出结果计算时间输出结果计算时间1.3 详细设计1、快速排序通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按这

2、种方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此使整个数据变成有序序列。void QuickSort(int a, int left, int right) 设置两个变量left、right，排序开始的时候left=1，right =N； if(left right) int pivotPos = Partition(a, left, right); QuickSort(a, left, pivotPos-1);/ 从left开始向后搜索，即由前开始向后搜索（left=left+1），找到第一个大于X的值，两者交换； QuickSort(a, pivotPos+1, rig

3、ht);/从left开始向后搜索，即由前开始向后搜索（left=left+1），找到第一个大于X的值，两者交换； /重复上述两步，直到left= right； int Partition(int a, int low, int high) int pivotValue = ahigh; int i = low-1; for(int j = low; j = high-1; j+) if(aj = pivotValue) i = i+1; swap(ai, aj); swap(ai+1, ahigh); return i+1; 2、堆排序：用最大堆排序(1)将原始未排序的数据建成一个堆。(2)建

4、成堆以后，最大值在堆顶，也就是第0个元素，这时候将第零个元素和最后一个元素交换。(3)这时候将从0到倒数第二个元素的所有数据当成一个新的序列，建一个新的堆，再次交换第一个和最后一个元素，依次类推，就可以将所有元素排序完毕。void insert_heap( int data, const int ¤t, int low, int high ) int large; /元素datalow左右儿子中，大者的位置 large = 2*low + 1; while( large = high ) if( large high & datalarge data large ) /待插入元素的

5、值比它的两个儿子都大 break; else data low = data large ; /将其左右儿子的大者上移 low = large; large = 2 * large + 1; data low = current; void build_heap( int data, int num ) /建立最大堆 int current; for( int low = num/2 - 1; low=0; low- ) current = data low ; insert_heap( data, current, low, num-1 ); void heap_sort( int data

6、, int num ) int current, last_sorted; build_heap( data, num ); /建立堆 for( last_sorted = num-1; last_sorted0; last_sorted- ) /逐个元素处理 current = data last_sorted ; /data0在整个数组排序结束前，存储的是待排序元素中最大的元素 datalast_sorted = data0; insert_heap( data, current, 0, last_sorted-1 ); 3、归并排序假设数组A有N个元素，那么可以看成数组A是由N个有序的子

7、序列组成，每个子序列的长度为1，然后再两两合并，得到了一个N/2个长度为2或1的有序子序列，再两两合并，如此重复，值得得到一个长度为N的有序数据序列为止void merge(int input, int p, int q, int r) /用二分检索查找的方法采用从低部分，高部分进行查找建立一个新的数组，将小的数放入新的数组中。 int n1 = q-p+1; int n2 = r-q; int i, j; for(i = 1; i =n1; i+) tempLi = inputp+i-1; for(j = 1; j =n2; j+) tempRj = inputq+j; tempLn1+1

8、= INF; tempRn2+1 = INF; i = 1; j = 1; for(int k = p; k = r; k+) if(tempLi = tempRj) inputk = tempLi+; else inputk = tempRj+; void mergeSort(int input, int p, int r) /利用递归进行排序，先查找中点位置，再对前部分查找，然后后部分，将小的数据放入新的数组 if(p r) int q = (p+r)/2; /查找中点位置 mergeSort(input,p,q); /前部分排序 mergeSort(input,q+1,r); /后部分排

9、序 merge(input, p, q, r); 1.4 调试分析1.5源代码#include using namespace std; const int N = 6; const int INF = 32767; int tempL(N+1)/2+2; int tempR(N+1)/2+2; int a1N = -3, 7, 5, 2, 9, 3; int a2N = -3, 7, 5, 2, 9, 3;int a3N = -3, 7, 5, 2, 9, 3; void swap(int& a, int& b) int temp =a; a = b; b = temp; int Parti

10、tion(int a, int low, int high) int pivotValue = ahigh; int i = low-1; for(int j = low; j = high-1; j+) if(aj = pivotValue) i = i+1; swap(ai, aj); swap(ai+1, ahigh); return i+1; void QuickSort(int a, int left, int right) if(left right) int pivotPos = Partition(a, left, right); QuickSort(a, left, pivo

11、tPos-1); QuickSort(a, pivotPos+1, right); void HeapAdjust(int *a,int i,int size) /调整堆 int lchild=2*i; /i的左孩子节点序号 int rchild=2*i+1; /i的右孩子节点序号 int max=i; if(i=size/2) /如果i不是叶节点就不调整 if(lchildamax) max=lchild; if(rchildamax) max=rchild; if(max!=i) swap(ai,amax); HeapAdjust(a,max,size); /避免调整之后以max为父节点的

12、子树不是堆 void BuildHeap(int *a,int size) /建立堆 int i; for(i=size/2;i=1;i-) /非叶节点最大序号值为size/2 HeapAdjust(a,i,size); void HeapSort(int *a,int size) /堆排序 int i; BuildHeap(a,size); for(i=size;i=1;i-) swap(a1,ai); /交换堆顶和最后一个元素，即每次将剩余元素中的最大者放到最后面 HeapAdjust(a,1,i-1); /重新调整堆顶节点成为大顶堆 void merge(int input, int p

13、, int q, int r) int n1 = q-p+1; int n2 = r-q; int i, j; for(i = 1; i =n1; i+) tempLi = inputp+i-1; for(j = 1; j =n2; j+) tempRj = inputq+j; tempLn1+1 = INF; tempRn2+1 = INF; i = 1; j = 1; for(int k = p; k = r; k+) if(tempLi = tempRj) inputk = tempLi+; else inputk = tempRj+; void mergeSort(int input,

14、 int p, int r) if(p r) int q = (p+r)/2; mergeSort(input,p,q); mergeSort(input,q+1,r); merge(input, p, q, r); void print(int array) for(int i = 0; i =N-1; i+) printf(%d ,arrayi); printf(n); inline unsigned _int64 GetCycleCount() _asm RDTSC int main() unsigned long b,e; cout原数组：-3 7 5 2 9 3endlendl;cout快速排序：;b=(unsigned long)GetCycleCount(); QuickSort(a1,0,N-1);e=(unsigned long)GetCycleCount(); print(a1);cout执行时间：e-bendl;cout-endl;cout堆排序：;b=(unsigned long)GetCycleCount(); HeapSor