sort01.cpp

随机产生个整数n=100

#include <iostream>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <string.h>
#include <ctype.h>
#include <conio.h>
#include <windows.h>
#include "InsertSort.h"
#include "BinaryInsertSort.h"
#include "ShellSort.h"
#include "BubbleSort.h"
#include "QuickSort.h"
#include "SelectSort.h"
#include "HeapSort.h"

using namespace std ;

#define random(num) (rand() % (num))
#define randomize() srand((unsigned)time(NULL))
typedef int RedType ;
#define N 10000

typedef struct SqList 
{
    RedType INT[N+1];
    int length ;
}SqList ;
SqList L ;

//单位ms
class timer 
{
    public :
    void start()
    {
        start_t=clock();
    }
    clock_t time()
    {
        return(clock()-start_t);
    }
    //获得系统时间
    static void curtime()
    {
        static char*week[]=
        {
            "一","二","三","四","五","六","日" 
        }
        ;
        time_t t ;
        struct tm*tp ;
        t=:: time(NULL);
        tp=localtime(&t);
        cout<<"\t　       ─────────────────────\n" ;
        cout<<"\t\t    现在是:"<<tp->tm_year+1900<<"年"<<tp->tm_mon+1<<"月"<<tp->tm_mday<<"日" ;
        cout<<tp->tm_hour<<":"<<tp->tm_min<<":"<<tp->tm_sec ;
        cout<<"星期"<<week[(tp->tm_wday)-1]<<endl ;
    }
    private :
    clock_t start_t ;
}
;
int KCN,RMN ;
timer TIMER ;
void testInsertSort(int a[],int num)
{
    cout<<"排序前:"<<endl ;
    for(int i=0;i<num;i++)
    {
        cout<<a[i]<<"\t" ;
    }
    TIMER.start();
    InsertSort<int>(a,num,KCN,RMN);
    cout<<"TimeSpared: "<<TIMER.time()<<"ms"<<endl ;
    cout<<"排序后:"<<endl ;
    for(int i=0;i<num;i++)
    {
        cout<<a[i]<<"\t" ;
    }
    cout<<"The result is:"<<endl ;
    cout<<"KCN="<<left<<setw(11)<<KCN ;
    cout<<"KCN/N="<<left<<setw(11)<<(double)KCN/N ;
    cout<<"KCN/N^2="<<left<<setw(11)<<(double)KCN/N/N ;
    cout<<"KCN/NlogN="<<left<<setw(11)<<(double)KCN/N/log((double)N)*log(2.0)<<endl ;
    cout<<"RMN="<<left<<setw(11)<<RMN ;
    cout<<"RMN/N="<<left<<setw(11)<<(double)RMN/N ;
    cout<<"RMN/N^2="<<left<<setw(11)<<(double)RMN/N/N ;
    cout<<"RMN/NlogN="<<left<<setw(11)<<(double)RMN/N/log((double)N)*log(2.0)<<endl ;
}

void testBinaryInsertSort(int a[],int num)
{
    cout<<"排序前:"<<endl ;
    for(int i=0;i<num;i++)
    {
        cout<<a[i]<<"\t" ;
    }
    TIMER.start();
    BinaryInsertSort<int>(a,num,KCN,RMN);
    cout<<"\tTimeSpared: "<<TIMER.time()<<"ms"<<endl ;
    cout<<"排序后:"<<endl ;
    for(int i=0;i<num;i++)
    {
        cout<<a[i]<<"\t" ;
    }
    cout<<"The result is:"<<endl ;
    cout<<"KCN="<<left<<setw(11)<<KCN ;
    cout<<"KCN/N="<<left<<setw(11)<<(double)KCN/N ;
    cout<<"KCN/N^2="<<left<<setw(11)<<(double)KCN/N/N ;
    cout<<"KCN/NlogN="<<left<<setw(11)<<(double)KCN/N/log((double)N)*log(2.0)<<endl ;
    cout<<"RMN="<<left<<setw(11)<<RMN ;
    cout<<"RMN/N="<<left<<setw(11)<<(double)RMN/N ;
    cout<<"RMN/N^2="<<left<<setw(11)<<(double)RMN/N/N ;
    cout<<"RMN/NlogN="<<left<<setw(11)<<(double)RMN/N/log((double)N)*log(2.0)<<endl ;
}

void testShellSort(int a[],int num)
{
    cout<<"排序前:"<<endl ;
    for(int i=0;i<num;i++)
    {
        cout<<a[i]<<"\t" ;
    }
    TIMER.start();
    ShellSort<int>(a,num,KCN,RMN);
    cout<<"\tTimeSpared: "<<TIMER.time()<<"ms"<<endl ;
    cout<<"排序后:"<<endl ;
    for(int i=0;i<num;i++)
    {
        cout<<a[i]<<"\t" ;
    }
    cout<<"The result is:"<<endl ;
    cout<<"KCN="<<left<<setw(11)<<KCN ;
    cout<<"KCN/N="<<left<<setw(11)<<(double)KCN/N ;
    cout<<"KCN/N^2="<<left<<setw(11)<<(double)KCN/N/N ;
    cout<<"KCN/NlogN="<<left<<setw(11)<<(double)KCN/N/log((double)N)*log(2.0)<<endl ;
    cout<<"RMN="<<left<<setw(11)<<RMN ;
    cout<<"RMN/N="<<left<<setw(11)<<(double)RMN/N ;
    cout<<"RMN/N^2="<<left<<setw(11)<<(double)RMN/N/N ;
    cout<<"RMN/NlogN="<<left<<setw(11)<<(double)RMN/N/log((double)N)*log(2.0)<<endl ;
}

void testBubbleSort(int a[],int num)
{
    cout<<"排序前:"<<endl ;
    for(int i=0;i<num;i++)
    {
        cout<<a[i]<<"\t" ;
    }
    TIMER.start();
    BubbleSort<int>(a,num,KCN,RMN);
    cout<<"\tTimeSpared: "<<TIMER.time()<<"ms"<<endl ;
    cout<<"排序后:"<<endl ;
    for(int i=0;i<num;i++)
    {
        cout<<a[i]<<"\t" ;
    }
    cout<<"The result is:"<<endl ;
    cout<<"KCN="<<left<<setw(11)<<KCN ;
    cout<<"KCN/N="<<left<<setw(11)<<(double)KCN/N ;
    cout<<"KCN/N^2="<<left<<setw(11)<<(double)KCN/N/N ;
    cout<<"KCN/NlogN="<<left<<setw(11)<<(double)KCN/N/log((double)N)*log(2.0)<<endl ;
    cout<<"RMN="<<left<<setw(11)<<RMN ;
    cout<<"RMN/N="<<left<<setw(11)<<(double)RMN/N ;
    cout<<"RMN/N^2="<<left<<setw(11)<<(double)RMN/N/N ;
    cout<<"RMN/NlogN="<<left<<setw(11)<<(double)RMN/N/log((double)N)*log(2.0)<<endl ;
}

void testQuickSort(int a[],int num)
{
    cout<<"排序前:"<<endl ;
    for(int i=0;i<num;i++)
    {
        cout<<a[i]<<"\t" ;
    }
    TIMER.start();
    QuickSort<int>(a,num,KCN,RMN);
    cout<<"\tTimeSpared: "<<TIMER.time()<<"ms"<<endl ;
    cout<<"排序后:"<<endl ;
    for(int i=0;i<num;i++)
    {
        cout<<a[i]<<"\t" ;
    }
    cout<<"The result is:"<<endl ;
    cout<<"KCN="<<left<<setw(11)<<KCN ;
    cout<<"KCN/N="<<left<<setw(11)<<(double)KCN/N ;
    cout<<"KCN/N^2="<<left<<setw(11)<<(double)KCN/N/N ;
    cout<<"KCN/NlogN="<<left<<setw(11)<<(double)KCN/N/log((double)N)*log(2.0)<<endl ;
    cout<<"RMN="<<left<<setw(11)<<RMN ;
    cout<<"RMN/N="<<left<<setw(11)<<(double)RMN/N ;
    cout<<"RMN/N^2="<<left<<setw(11)<<(double)RMN/N/N ;
    cout<<"RMN/NlogN="<<left<<setw(11)<<(double)RMN/N/log((double)N)*log(2.0)<<endl ;
}

void testSelectSort(int a[],int num)
{
    cout<<"排序前:"<<endl ;
    for(int i=0;i<num;i++)
    {
        cout<<a[i]<<"\t" ;
    }
    TIMER.start();
    SelectSort<int>(a,num,KCN,RMN);
    cout<<"\tTimeSpared: "<<TIMER.time()<<"ms"<<endl ;
    cout<<"排序后:"<<endl ;
    for(int i=0;i<num;i++)
    {
        cout<<a[i]<<"\t" ;
    }
    cout<<"The result is:"<<endl ;
    cout<<"KCN="<<left<<setw(11)<<KCN ;
    cout<<"KCN/N="<<left<<setw(11)<<(double)KCN/N ;
    cout<<"KCN/N^2="<<left<<setw(11)<<(double)KCN/N/N ;
    cout<<"KCN/NlogN="<<left<<setw(11)<<(double)KCN/N/log((double)N)*log(2.0)<<endl ;
    cout<<"RMN="<<left<<setw(11)<<RMN ;
    cout<<"RMN/N="<<left<<setw(11)<<(double)RMN/N ;
    cout<<"RMN/N^2="<<left<<setw(11)<<(double)RMN/N/N ;
    cout<<"RMN/NlogN="<<left<<setw(11)<<(double)RMN/N/log((double)N)*log(2.0)<<endl ;
}

void testHeapSort(int a[],int num)
{
    cout<<"排序前:"<<endl ;
    for(int i=0;i<num;i++)
    {
        cout<<a[i]<<"\t" ;
    }
    TIMER.start();
    HeapSort<int>(a,num,KCN,RMN);
    cout<<"\tTimeSpared: "<<TIMER.time()<<"ms"<<endl ;
    cout<<"排序后:"<<endl ;
    for(int i=0;i<num;i++)
    {
        cout<<a[i]<<"\t" ;
    }
    cout<<"The result is:"<<endl ;
    cout<<"KCN="<<left<<setw(11)<<KCN ;
    cout<<"KCN/N="<<left<<setw(11)<<(double)KCN/N ;
    cout<<"KCN/N^2="<<left<<setw(11)<<(double)KCN/N/N ;
    cout<<"KCN/NlogN="<<left<<setw(11)<<(double)KCN/N/log((double)N)*log(2.0)<<endl ;
    cout<<"RMN="<<left<<setw(11)<<RMN ;
    cout<<"RMN/N="<<left<<setw(11)<<(double)RMN/N ;
    cout<<"RMN/N^2="<<left<<setw(11)<<(double)RMN/N/N ;
    cout<<"RMN/NlogN="<<left<<setw(11)<<(double)RMN/N/log((double)N)*log(2.0)<<endl ;
}

//随机生成数字
void RAND(SqList*L)
{
    int*randomness=new int[N];
    //随机序列
    int i ;
    char c ;
    loop1 :
    ;
    TIMER.curtime();
    printf("\t　       ─────────────────────\n");
    printf("\n\t\t\t请输入待排序数据的数量【>=2】: ");
    //检测是否为正确输入数
    while(scanf("%d",&L->length)!=1)
    {
        while((c=getchar())!='\n');
        printf("\n\t\t【×】Error:错误的输入,请按任意键重新输入→\n\t\t\t\t");
        _getch();
        system("cls");
        goto loop1 ;
    }
    if(L->length<2||L->length>N)
    {