南航数据结构课设——排序算法时间

排序算法比较 （必做）（排序）

[问题描述]

利用随机函数产生10个样本，每个样本有50000个随机整数（并使第一个样本是正序，第二个样本是逆序），利用直接插入排序、希尔排序，冒泡排序、快速排序、选择排序、堆排序，归并排序、基数排序8种排序方法进行排序（结果为由小到大的顺序），并统计每一种排序算法对不同样本所耗费的时间。

?[基本要求]

（1） 原始数据存在文件中，用相同样本对不同算法进行测试；

（2） 屏幕显示每种排序算法对不同样本所花的时间；

数据结构：数组

算法设计与分析

利用随机函数生成10个含有50000个数据的样本，记录排序前的时间和排序后的时间，两者之差就是排序所用时间。

源代码

#include<iostream>
#include<stdlib.h>
#include<fstream>
#define n 50000
#define len 50000
#include <stack>
using namespace std;
void swap(int *x,int *y)
{
    int temp=*x;
    *x=*y;
    *y=temp;
}
void BubbleSort(int arr[])
{
	for(int i=0;i<n-1;i++)
    {
        for(int j=0;j<n-1-i;j++)
        {
            if(arr[j+1]<arr[j])
            {
                int temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
    }
}
void SelectSort(int arr[])
{
	for(int i=0;i<n-1;i++)
    {
        int temp=i;
        for(int j=i+1;j<n;j++)
        {
            if(arr[j]<arr[temp])
            temp=j;
        }
        int ten=arr[i];
        arr[i]=arr[temp];
        arr[temp]=ten;
    }
}
void InsertSort(int arr[])
{
	for(int i=1;i<n;i++)
    {
        int temp=arr[i];
        for(int j=i-1;j>=0;j--)
        {
            if(temp<arr[j])
            {
                arr[j+1]=arr[j];
                arr[j]=temp;
            }
            
        }
    }
}
void ShellSort(int arr[]) {
	int grp = n / 2;	
	for (; grp > 0; grp = grp / 2) 
	{	
		for (int i = grp; i < n; i++) 
		{	
			int cur = arr[i];	
			int j = 0;
			for (j = i - grp; j >= 0 && arr[j] > cur; j = j - grp) 
			{
				arr[j + grp] = arr[j];	
			}
			arr[j + grp] = cur;	
		}
	}
	
}
int Partition( int a[], int low, int high )
{
	//假设每次都以第一个元素作为枢轴值，进行一趟划分：
	int pivot = a[low];
	 
	while( low<high )
	{
		while( low<high && a[high]>=pivot )
		--high;
		a[low] = a[high];  //停下来做交换 
		while( low<high && a[low]<=pivot )
		++low;
		a[high] = a[low];  //停下来做交换 
	}
	
	a[low] = pivot;  //pivot的最终落点 
	return low;
}
void QuickSort(int a[], int left, int right)
{
	//手动利用栈来存储每次分块快排的起始点
	//栈非空时循环获取中轴入栈
	stack<int> s;
	if( left<right )
	{
		int boundary = Partition(a,left,right);
		
		if( boundary-1>left ) //确保左分区存在 
		{
			//将左分区端点入栈 
			s.push(left);
			s.push(boundary-1);
		}
		if( boundary+1<right ) //确保右分区存在 
		{
			s.push(boundary+1);
			s.push(right);
		}
		
		while( !s.empty() )
		{
			//得到某分区的左右边界 
			int r = s.top();
			s.pop();  
			int l = s.top();
			s.pop();
			
			boundary = Partition(a,l,r);
			if( boundary-1>l ) //确保左分区存在 
		    { 
			    //将左分区端点入栈 
		    	s.push(l);
		    	s.push(boundary-1);
	    	}
		    if( boundary+1<r ) //确保右分区存在 
	     	{
	 	    	s.push(boundary+1);
	    		s.push(r);
	    	}
		}
	}
}
void adjustHeap(int arr[], int param1, int j)
{
    int t;
    if(j<param1)
	{
		int max=j;
		int s1=2*j+1;
		int s2=2*j+2;
		if(arr[s1]>arr[max]&&s1<param1)
			max=s1;
		if(arr[s2]>arr[max]&&s2<param1)
			max=s2;
		if(max!=j)
		{
            t = arr[max];
            arr[max] = arr[j];
            arr[j] = t; 
            adjustHeap(arr,param1,max);		
		}
	}
}
int* heap_sort(int arr[])
{
    int i,t;
    int l=n-1;				
	int p=(l-1)/2;	
	for(int i=p;i>=0;i--)	
	{
		adjustHeap(arr,n,i);	
	}
    for(int i=n-1;i>=0;i--)
	{
        t = arr[i];
        arr[i] = arr[0];
        arr[0] = t;
		adjustHeap(arr,i,0);		
	}
    return arr;
}
int temp[n];
int bucket[10];
 
int maxBit(int data[])
{
	//行这些代码在求n个元素的最大值 
	int maxData = data[0];
	for(int i=1;i<n;i++)
	{
		if(maxData<data[i])
			maxData=data[i];
	}
	
	//这些代码在求最大值的位数是多少 
	int d=1;    //d用来计数最大值的位数，因为既然是一个数，肯定至少有1位，所以d初始化为1 
	while(maxData>=10)  //将最大值不断/10，计算位数 
	{
		maxData/=10;
		d++;
	}
	return d;
} 
void RadixSort(int data[])  //基数排序 
{
	int d = maxBit(data);  //求出最大位数
	int i,j,k;
	int radix = 1;
	for(i=1;i<=d;i++)   //进行d次排序
	{
	    for(j=0;j<10;j++)   //每次分配前清空计数器
		{
			bucket[j]=0;
		}
		for(j=0;j<n;j++)    //统计每个桶的元素个数 
		{
			k=(data[j]/radix)%10;
			bucket[k]++;
		}
		
		//关键代码1 
	    for(j = 1; j < 10; j++)
            bucket[j] = bucket[j - 1] + bucket[j]; 
       
       //关键代码2 
		for(j = n-1; j>=0; j--) 
        {
            k = (data[j] / radix) % 10;
            temp[bucket[k] - 1] = data[j];
            bucket[k]--;
        }
        for(j = 0; j < n; j++) //将临时数组的内容复制到data中
            data[j] = temp[j];
            
        radix = radix * 10;  //个位  -》 十位  -》百位 -》…… 
	} 
}
void merge(int a[], int low, int mid, int hight)  //合并函数
{
	int* b = new int[hight - low + 1];  //用 new 申请一个辅助函数
	int i = low, j = mid + 1, k = 0;    // k为 b 数组的小标
	while (i <= mid && j <= hight)  
	{
		if (a[i] <= a[j])
		{
			b[k++] = a[i++];  //按从小到大存放在 b 数组里面
		}
		else
		{
			b[k++] = a[j++];
		}
	}
	while (i <= mid)  // j 序列结束，将剩余的 i 序列补充在 b 数组中 
	{
		b[k++] = a[i++];
	}
	while (j <= hight)// i 序列结束，将剩余的 j 序列补充在 b 数组中 
	{
		b[k++] = a[j++];
	}
	k = 0;  //从小标为 0 开始传送
	for (int i = low; i <= hight; i++)  //将 b 数组的值传递给数组 a
	{
		a[i] = b[k++];
	}
	delete[]b;     // 辅助数组用完后，将其的空间进行释放（销毁）
}
void MergeSort(int a[], int low, int hight) //归并排序
{
	if (low < hight)
	{
		int mid = (low + hight) / 2;
		MergeSort(a, low, mid);          //对 a[low,mid]进行排序
		MergeSort(a, mid + 1, hight);    //对 a[mid+1,hight]进行排序
		merge(a, low, mid, hight);       //进行合并操作
	}
}

int main()
{
	int i, j,arr[10][n];
	timeb startTime,endTime;
	
	fstream datafile1,datafile2,datafile3,datafile4,datafile5,datafile6,
	datafile7,datafile8,datafile9,datafile10;
	datafile1.open("text1.dat",ios::in|ios::binary);
	datafile1.read((char*)arr[0],sizeof(arr[0]));
	
	datafile2.open("text2.dat",ios::in|ios::binary);
	datafile2.read((char*)arr[1],sizeof(arr[1]));
	
	datafile3.open("text3.dat",ios::in|ios::binary);
	datafile3.read((char*)arr[2],sizeof(arr[2]));
	
	datafile4.open("text4.dat",ios::in|ios::binary);
	datafile4.read((char*)arr[3],sizeof(arr[3]));
	
	datafile5.open("text5.dat",ios::in|ios::binary);
	datafile5.read((char*)arr[4],sizeof(arr[4]));
	
	datafile6.open("text6.dat",ios::in|ios::binary);
	datafile6.read((char*)arr[5],sizeof(arr[5]));
	
	datafile7.open("text7.dat",ios::in|ios::binary);
	datafile7.read((char*)arr[6],sizeof(arr[6]));
	
	datafile8.open("text8.dat",ios::in|ios::binary);
	datafile8.read((char*)arr[7],sizeof(arr[7]));
	
	datafile9.open("text9.dat",ios::in|ios::binary);
	datafile9.read((char*)arr[8],sizeof(arr[8]));
	
	datafile10.open("text10.dat",ios::in|ios::binary);
	datafile10.read((char*)arr[9],sizeof(arr[9]));
	/*for(int i=0;i<n;i++)
	cout<<arr[2][i]<<" ";
	*/
	
	cout<<"1.冒泡排序"<<endl;
	for(i=0;i<=9;i++)
	{
		ftime(&startTime);
	    BubbleSort(arr[i]);
		ftime(&endTime);
		cout << "第" << i+1 << "组数据花费时间:" << (endTime.time - startTime.time) * 1000 + 
	(endTime.millitm - startTime.millitm) << "ms" << endl;
	}
	cout<<endl;
	cout<<"2.选择排序"<<endl;
	for(i=0;i<=9;i++)
	{
		ftime(&startTime);
	    SelectSort(arr[i]);                
		ftime(&endTime);
		cout << "第" << i+1 << "组数据花费时间:" << (endTime.time - startTime.time) * 1000 + 
	(endTime.millitm - startTime.millitm) << "ms" << endl;
	}
	cout<<endl;
	cout<<"3.插入排序"<<endl;
	for(i=0;i<=9;i++)
	{
		ftime(&startTime);
	    InsertSort(arr[i]);                
		ftime(&endTime);
		cout << "第" << i+1 << "组数据花费时间:" << (endTime.time - startTime.time) * 1000 + 
	(endTime.millitm - startTime.millitm) << "ms" << endl;
	}
	cout<<endl;
	cout<<"4.希尔排序"<<endl;
	for(i=0;i<=9;i++)
	{
		ftime(&startTime);
	    ShellSort(arr[i]);                
		ftime(&endTime);
		cout << "第" << i+1 << "组数据花费时间:" << (endTime.time - startTime.time) * 1000 + 
	(endTime.millitm - startTime.millitm) << "ms" << endl;
	}
	cout<<endl;
	cout<<"5.快速排序"<<endl;
	for(i=0;i<=9;i++)
	{
		ftime(&startTime);
	    QuickSort(arr[i],0,n-1);               
		ftime(&endTime);
		cout << "第" << i+1 << "组数据花费时间:" << (endTime.time - startTime.time) * 1000 + 
	(endTime.millitm - startTime.millitm) << "ms" << endl;
	}
	cout<<endl;
	cout<<"6.堆排序"<<endl;
	for(i=0;i<=9;i++)
	{
		ftime(&startTime);
	    heap_sort(arr[i]);               
		ftime(&endTime);
		cout << "第" << i+1 << "组数据花费时间:" << (endTime.time - startTime.time) * 1000 + 
	(endTime.millitm - startTime.millitm) << "ms" << endl;
	}
	cout<<endl;
	cout<<"7.基数排序"<<endl;
	for(i=0;i<=9;i++)
	{
		ftime(&startTime);
	    RadixSort(arr[i]);               
		ftime(&endTime);
		cout << "第" << i+1 << "组数据花费时间:" << (endTime.time - startTime.time) * 1000 + 
	(endTime.millitm - startTime.millitm) << "ms" << endl;
	}
	cout<<endl;
	cout<<"8.归并排序"<<endl;
	for(i=0;i<=9;i++)
	{
		ftime(&startTime);
	    MergeSort(arr[i],0,n-1);              
		ftime(&endTime);
		cout << "第" << i+1 << "组数据花费时间:" << (endTime.time - startTime.time) * 1000 + 
	(endTime.millitm - startTime.millitm) << "ms" << endl;
	}
	cout<<endl;
	datafile1.close();
	datafile2.close();
	datafile3.close();
	datafile4.close();
	datafile5.close();
	datafile6.close();
	datafile7.close();
	datafile8.close();
	datafile9.close();
	datafile10.close();
} 

测试结果?

时间复杂度

排序算法时间复杂度

插入排序：O(n^2) ??希尔排序：O(n^2) ??选择排序: O(n^2)

堆排序：O(nlog2n) ?冒泡排序：O(n^2) ??归并排序：O(nlog2n)

基数排序：O(nlog2n)? ? 快速排序：O(nlog2n)

?