发布时间 : 星期二 文章大数据结构各种排序算法地时间性能.更新完毕开始阅读
实用文案
三、详细设计
（1）产生随机数：直接调用函数srand(),以时间作为随机种子进行选择，并把随机数装入数组中
unsigned long int *Sort::setRan(unsigned long int num){ unsigned long int *ra;
ra=(unsigned long int*)malloc(num*sizeof(unsigned long int)); srand(time(NULL));
for(unsigned long int m=0;m cout< （2）快速排序：要实现快速排序首先选择一个轴值，这里选取数组第一个为轴值。定义两个标识low,high。high标识最后一个元素的位置，从后向前，将关键字与轴值比较，直至遇到小于轴值的关键字，前移，low标识在第二个元素的位置，从前向后，将关键字与轴值比较，直至遇到大于轴值的关键字，后移。当low,high相遇后第一趟排序结束。调整数列，轴值左边的为比轴值小的，右边为比轴值大的。对轴值左边（即low到pivotkey-1的数）和右边的子列（pivotkey+1到high的数）分别进行上述递归快速排序，直到范围为1结束。 int partition(int a[],int low,int high){//快速排序中的一趟 int pivotkey; //作为枢轴来使用 pivotkey=a[low]; while(low while(low a[low]=a[high]; while(low a[high]=a[low]; } a[low]=pivotkey; return low; } void qsort(int a[],int low,int high){//快速排序的递归形式 int pivotloc; 标准文档 实用文案 if(low pivotloc=partition(a,low,high);//一趟排序结果的调用 qsort(a,low,pivotloc-1); qsort(a,pivotloc+1,high); } } （3）插入排序：插入排序的思想是将一组无序的元素分别插入一个已经有序的的数组里，并保证插入后的数组也是有序的。当所有无序组的元素都插入完毕时，一个有序数组构造完成。数组n[1…r]为初始的一个无序数组（为了直观起见，我们这里设定数组从1开始，而不是0），则n[1]默认为只有一个元素的有序数组，n[2]插入只有n[1]构成的有序数组中，则此时有序数组的元素数量变为2。以此类推，到第i个元素时，前i-1个元素已经是有序的，此时只需将第i个元素插入到有序数组中并使之保持有序。如此直至最后一个元素插入完毕，整个插入排序完成。 void Sort::insertSort(unsigned long int *s){ this->setNum(); LARGE_INTEGER Freg; LARGE_INTEGER Count1,Count2; QueryPerformanceFrequency(&Freg); QueryPerformanceCounter(&Count1);//获取时间Count1 double d; int temp,j; for (unsigned long int i=0;i j=i; temp=s[i]; while (j>=1 && temp this->SortNum++; } if(j>1) this->SortNum++; s[j]=temp; } QueryPerformanceCounter(&Count2);//获取时间Count2 d=(double)(Count2.QuadPart-Count1.QuadPart)/(double)Freg.QuadPart*1000.0;//计算时间差，d的单位为ms. cout<<\插入排序算法对\个随机数排序时间为为\ms.\ cout<<\插入排序算法对\个随机数交换次数为\次。\ 标准文档 实用文案 } (4) 冒泡排序（bubble sort）：将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上\飘浮\。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。从无序区底部向上依次比较相邻的两个气泡的重量，若发现轻者在下、重者在上，则交换二者的位置。即依次比较(R[n]，R[n-1])，(R[n-1]，R[n-2])，…，(R[2]，R[1])；对于每对气泡(R[j+1]，R[j])，若R[j+1].key void Sort::bubbleSort(unsigned long int *s){ this->setNum(); LARGE_INTEGER Freg; LARGE_INTEGER Count1,Count2; QueryPerformanceFrequency(&Freg); QueryPerformanceCounter(&Count1);//获取时间Count1 double d; unsigned long int temp; for(unsigned long int i=0;i<(this->RanNum);i++){ for(int j=i+1;j<(this->RanNum);j++){ if(s[i]>s[j]){ temp = s[i]; s[i]=s[j]; s[j]=temp; this->SortNum++; } } } QueryPerformanceCounter(&Count2);//获取时间Count2 d=(double)(Count2.QuadPart-Count1.QuadPart)/(double)Freg.QuadPart*1000.0;//计算时间差，d的单位为ms. cout<<\冒泡排序算法对\个随机数排序时间为\ms.\ cout<<\冒泡排序算法对\个随机数交换次数为\次。\ } (5) 堆排序：堆排序与其他排序算法最大的区别是它依靠一种特殊的数据结 标准文档 实用文案 构——堆来进行排序。堆是一种完全二叉树，并且根节点不大于左右子树中的所有节点，n[i]<=n[2*i]&&n[i]<=n[2*i+1]。因此堆排序算法首先要将给出的无序数组构造成一个堆，然后输出根节点（最小元素），将剩余元素重新恢复成堆，再次输出根节点。依次类推，直至最后一个节点输出，此时堆排序完成。 void Sort::heapRestor(unsigned long int *s,int i,int m) { int ma; if((i<=m/2)&&(s[i]>min(s[2*i],s[2*i+1]))) { if(s[2*i] ma=s[i]; s[i]=s[2*i]; s[2*i]=ma; this->heapRestor(s,2*i,m); } else { ma=s[i]; s[i]=s[2*i+1]; s[2*i+1]=ma; this->heapRestor(s,2*i+1,m); } this->SortNum=this->SortNum+2; } else if(i<=m/2) this->SortNum++; } void Sort::heapCreat(unsigned long int *s,int m) { int num; for(num=m/2;num>=1;num--) this->heapRestor(s,num,m); } void Sort::heapSort(unsigned long int *s1,unsigned long int *s2) { this->setNum(); int i,num; num=this->RanNum; LARGE_INTEGER Freg; LARGE_INTEGER Count1,Count2; QueryPerformanceFrequency(&Freg); QueryPerformanceCounter(&Count1);//获取时间Count1 标准文档