C/C++源代码实现对随机生成的数据进行排序（直接插入排序、折半插入排序）

素颜马尾好姑娘i 2022-04-08 10:40 139阅读 0赞

## **代码实现功能如下：** ##

**1.产生1E4个随机数并对随机数进行排序；**

**2.计算排序所用时间；**

**3.排序方法为直接插入排序和折半插入排序。**

## **源代码如下：** ##

#include<stdio.h> 
    #include<stdlib.h>
    #include<time.h>		//用到 time 函数 
    #include<iostream>
    using namespace std;
    #define MAX 10000		//顺序表的最大长度
    int a[MAX+5];
    int b[MAX+5];
    		//顺序表类型
    
    void InsertSort(){
       //对顺序表L做			直接插入排序
    	int i,j,k;
    	for(i=2;i<=10000;i++)
    	{
    		int temp=a[i];
    		for(j=i;j>1 && a[j-1]>temp;j--)
    		{
    			a[j]=a[j-1];
    		}
    		a[j]=temp;
    	}
    }
    
    void BInsertSort(){
    	int left,right;
    	int i,j,k;
    	int mid;
    	for(i=2;i<=10000;i++)
    	{
    		int temp=a[i];
    		left=1;
    		right=i-1;
    		while(left<=right)
    		{
    			mid=(left+right)/2;
    			if(temp>a[mid])
    			{
    				left=mid+1;
    			}
    			else
    			{
    				right=mid-1;
    			}
    		}
    		for(j=i;j>left ;j--)
    		a[j]=a[j-1];
    		a[left]=temp;
    	}
    }
    
    void menu()
    {
    	cout<<"************    排序程序    ************"<<'\n' ;
    	cout<<endl;
    	cout<<"********   请选择：		********"<<'\n' ;
    	cout<<"********   1.直接插入排序实现； ********"<<'\n';
    	cout<<"********   2.折半插入排序实现； ********"<<'\n';
    	cout<<"********   3.退出程序；         ********"<<'\n';
    	cout<<endl;
    	cout<<"****************************************"<<'\n' ;
    }
    
    int main()
    {
    	int i;
    	clock_t start,end; 
    	menu();
    	srand((unsigned int)time(NULL));	 //用时间做种，每次产生随机数不一样
    	for(i=1;i<=10000;i++)
    	{
    		a[i]=rand()%50000+1;
    		b[i]=a[i];
    	}
    
    	int x;
    	cout<<"请输入你所需要的选项："<<endl;
    	while(cin>>x)
    	{
    		switch(x){
    		case 1: 
    		{
    			cout<<"直接插入排序的结果为："<<endl;
    			start=clock();
    			InsertSort();
    			end=clock();
    			for(i=1;i<=10000;i++)
    				cout<<a[i]<<'\t';
    			double count=(double)(end-start)/1000;
    			cout<<endl;
    			cout<<"排序所用时间为："<<count<<"s"<<endl;
    		} break;
    		case 2:
    			{
    			for(i=0;i<10000;i++)
    				a[i]=b[i];
    			cout<<"折半插入排序的结果为："<<endl;
    			start=clock();
    			BInsertSort();
    			end=clock();
    			for(i=0;i<10000;i++)
    				cout<<a[i]<<'\t';
    			double count=(double)(end-start)/1000;
    			cout<<endl; 
    			cout<<"排序所用时间为："<<count<<"s"<<endl;	
    			}break;
    		
    		}
    		if(x==3)
    		break;
    	}
    	
    		
    	return 0;
    }

## **运行结果：** ##

10000个随机数进行直接插入排序运行时间为0.061s，进行折半插入排序运行时间为0.047s。