#include <cstdio>#include <cstring>#include <ctime>#include <algorithm>#include <cstdlib>#include <cmath>#include <fstream>using namespace std;class insertSort{public:    insertSort(int * a,int size){        this->a = a;        this->size = size;        b = new int[size];    }    ~insertSort(){        delete b;    }    void sort(){        for(int i =0;i<size;i++)b[i] =a[i];        swapTime = 0;        compTime = 0;        start = time(&start);        for(int i = 0;i<size; i++){          //  printf("%d\n",a[i]);          //  int minind = i;            int j = i;            for(j = i-1;j>=0;j--){                compTime++;                if(b[j]<=b[i]){                    break;                }            }            if(b[j]<=b[i]||j<0)j++;//要插入位置            int tmp = b[i];            for(int k = i;k>j;k--){                    b[k] = b[k-1];                    swapTime ++;            }            b[j] = tmp;        }        stop= time(&stop);    }    void print(){        puts("1 直接插入排序");        puts("展示结果");        for(int i =0;i<size;i++)printf("%d%c",b[i],i==size-1?‘\n‘:‘ ‘);        printf("关键字比较次数:%d\n",compTime);        printf("关键字排序次数:%d\n",swapTime);        printf("用时:%ld ms\n",stop-start);    }    int swapTime;    int compTime;private:    int * a;    int * b;    int size;    time_t start,stop;};class halfInsertSort{public:    halfInsertSort(int * a,int size){        this->a = a;        this->size = size;        b = new int[size];    }    ~halfInsertSort(){        delete b;    }    void sort(){       for(int i=0;i<size;i++)b[i]=a[i];        swapTime = 0;        compTime = 0;        start = time(&start);        for(int i = 0;i<size; i++){            int l=0,r=i;            while(r-l>1){                int mid = (l+r)>>1;                if(b[mid] > b[i]){                    r = mid;                }                else {                    l = mid;                }                compTime++;            }            if(b[l]<=b[i])l++;            int tmp = b[i];            for(int k = i;k>l;k--){                    b[k]=b[k-1];                    swapTime ++;            }            b[l]=tmp;        }        stop= time(&stop);    }    void print(){        puts("2 折半插入排序");        puts("展示结果");        for(int i =0;i<size;i++)printf("%d%c",b[i],i==size-1?‘\n‘:‘ ‘);        printf("关键字比较次数:%d\n",compTime);        printf("关键字排序次数:%d\n",swapTime);        printf("用时:%ld ms\n",stop-start);    }    int swapTime;    int compTime;private:    int * a;    int * b;    int size;    time_t start,stop;};class shellSort{public:    shellSort(int * a,int size){        this->a = a;        this->size = size;        b = new int[size];    }    ~shellSort(){        delete b;    }    void sort(){        for(int i =0;i<size;i++)b[i] =a[i];        swapTime = 0;        compTime = 0;        start = time(&start);        int times = int(log2(size+1));        for(int i = 1;i <=times;i++){            int d = int(pow(2,times-i+1)-1);            for(int j = 0;j < size;j++){                int tmp = b[j];                int k;                for(k= j-d;k>=0&&++compTime&&b[k]>tmp;k-=d){                    b[k+d] = b[k];swapTime++;                }                k+=d;                b[k] = tmp;            }        }        stop= time(&stop);    }    void print(){        puts("3 Shell排序");        puts("展示结果");        for(int i =0;i<size;i++)printf("%d%c",b[i],i==size-1?‘\n‘:‘ ‘);        printf("关键字比较次数:%d\n",compTime);        printf("关键字排序次数:%d\n",swapTime);        printf("用时:%ld ms\n",stop-start);    }    int swapTime;    int compTime;private:    int * a;    int * b;    int size;    time_t start,stop;};class bubbleSort{public:    bubbleSort(int * a,int size){        this->a = a;        this->size = size;        b = new int[size];    }    ~bubbleSort(){        delete b;    }    void sort(){        for(int i =0;i<size;i++)b[i] =a[i];        swapTime = 0;        compTime = 0;        start = time(&start);        for(int i = 0;i<size; i++){                for(int j = size - 1;j > i; j--){                    compTime++;                    if(b[j]<b[j-1]){                            swap(b[j-1],b[j]);                            swapTime+=3;                    }                }        }        stop= time(&stop);    }    void print(){        puts("4 冒泡排序");        puts("展示结果");        for(int i =0;i<size;i++)printf("%d%c",b[i],i==size-1?‘\n‘:‘ ‘);        printf("关键字比较次数:%d\n",compTime);        printf("关键字排序次数:%d\n",swapTime);        printf("用时:%ld ms\n",stop-start);    }    int swapTime;    int compTime;private:    int * a;    int * b;    int size;    time_t start,stop;};class quickSort{public:    quickSort(int * a,int size){        this->a = a;        this->size = size;        b = new int[size];    }    ~quickSort(){        delete b;    }    void partition2(int s,int t){        int low = s,high = t;        int key = b[s];        while(low < high){            while(low<high&&high--&&b[high] >= key){compTime++;}            if(low==high)break;            b[low] = b[high];            swapTime++;            while(low<high&&low++&&b[low]<=key){compTime++;}            if(low==high)break;            b[high] = b[low];            swapTime++;        }        b[low] = key;        if(low>s+1)partition2(s,low);        if(low+1<t)partition2(low+1,t);    }    void sort(){        for(int i =0;i<size;i++)b[i] =a[i];        swapTime = 0;        compTime = 0;        start = time(&start);        partition2(0,size);        stop= time(&stop);    }    void print(){        puts("5 快速排序");        puts("展示结果");        for(int i =0;i<size;i++)printf("%d%c",b[i],i==size-1?‘\n‘:‘ ‘);        printf("关键字比较次数:%d\n",compTime);        printf("关键字排序次数:%d\n",swapTime);        printf("用时:%ld ms\n",stop-start);    }    int swapTime;    int compTime;private:    int * a;    int * b;    int size;    time_t start,stop;};class simpleSelectSort{public:    simpleSelectSort(int * a,int size){        this->a = a;        this->size = size;        b = new int[size];    }    ~simpleSelectSort(){        delete b;    }    void sort(){        for(int i =0;i<size;i++)b[i] =a[i];        swapTime = 0;        compTime = 0;        start = time(&start);        for(int i=0;i<size;i++){            int minind =i;            for(int j=i+1;j<size&&++compTime;j++){                if(b[minind]>b[j]){                    minind = j;                }            }            if(i!=minind){                    swap(b[minind],b[i]);                    swapTime+=3;            }        }        stop= time(&stop);    }    void print(){        puts("6 简单选择排序");        puts("展示结果");        for(int i =0;i<size;i++)printf("%d%c",b[i],i==size-1?‘\n‘:‘ ‘);        printf("关键字比较次数:%d\n",compTime);        printf("关键字排序次数:%d\n",swapTime);        printf("用时:%ld ms\n",stop-start);    }    int swapTime;    int compTime;private:    int * a;    int * b;    int size;    time_t start,stop;};class heapSort{public:    heapSort(int * a,int size){        this->a = a;        this->size = size;        b = new int[size];    }    ~heapSort(){        delete b;    }    void heapAdjust(int i,int size){        int lchild = 2*i;        int rchild = 2*i+1;        int mx = i;        if(i<=size/2){            if(lchild<size&&b[lchild]>b[mx]){                mx = lchild;                compTime++;            }            if(rchild<size&&b[rchild]>b[mx]){                mx = rchild;                compTime++;            }        }        if(mx!=i){            swapTime+=3;            swap(b[mx],b[i]);            heapAdjust(mx,size);        }    }    void sort(){        for(int i =0;i<size;i++)b[i] =a[i];        swapTime = 0;        compTime = 0;        start = time(&start);        for(int i = size/2;i>=0;i--){            heapAdjust(i,size);        }        for(int i = size;i>0;i--){            swap(b[0],b[i-1]);            heapAdjust(0,i-1);        }        stop= time(&stop);    }    void print(){        puts("7 堆排序");        puts("展示结果");        for(int i =0;i<size;i++)printf("%d%c",b[i],i==size-1?‘\n‘:‘ ‘);        printf("关键字比较次数:%d\n",compTime);        printf("关键字排序次数:%d\n",swapTime);        printf("用时:%ld ms\n",stop-start);    }    int swapTime;    int compTime;private:    int * a;    int * b;    int size;    time_t start,stop;};class mergeSort{public:    mergeSort(int * a,int size){        this->a = a;        this->size = size;        b = new int[size];    }    ~mergeSort(){        delete b;    }    void merge(int s,int t){        //printf("s %d t %d\n",s,t);        int mid = (s+t)>>1;        if(s+1<mid)merge(s,mid);        if(t>mid+1)merge(mid,t);        int* tmp = new int[t-s+1];        int i = s,j = mid,k = s;        while(k<t){            if(i<mid&&j<t){                compTime++;                if(b[i]<b[j])tmp[k++-s]=b[i++];                else  tmp[k++-s]=b[j++];            }            else if(i<mid){                tmp[k++-s]=b[i++];            }            else{                tmp[k++-s]=b[j++];            }            swapTime ++;        }        while(--k>=s){                b[k]=tmp[k-s];swapTime++;        }      //  print();        delete tmp;    }    void sort(){        for(int i =0;i<size;i++)b[i] =a[i];        swapTime = 0;        compTime = 0;        start = time(&start);        merge(0,size);        stop= time(&stop);    }    void print(){        puts("8 归并排序");        puts("展示结果");        for(int i =0;i<size;i++)printf("%d%c",b[i],i==size-1?‘\n‘:‘ ‘);        printf("关键字比较次数:%d\n",compTime);        printf("关键字排序次数:%d\n",swapTime);        printf("用时:%ld ms\n",stop-start);    }    int swapTime;    int compTime;private:    int * a;    int * b;    int size;    time_t start,stop;};int printInstruction(){    puts("*************************************************");    puts("0 退出");    puts("1 直接显示结果");    puts("2 比较八种不同排序");    puts("3 重新生成数据");    puts("*************************************************");    int op;    scanf("%d",&op);    return op;}class generator{    public:    generator(){        this->size = 200;        this->bon = 200;        a = new int[size];        for(int i= 0;i<size;i++){            a[i] = rand()*bon/RAND_MAX;        }    }    generator(int size,int bon){        this->size = size;        this->bon = bon;        a = new int[size];        for(int i= 0;i<size;i++){            a[i] = rand()*bon/RAND_MAX;        }    }    ~generator(){        delete a;    }    void print(){        printf("容量:%d 生成数最大值:%d %p\n",size,bon,a);        for(int i =0;i<size;i++)printf("%d%c",a[i],i==size-1?‘\n‘:‘ ‘);    }    int* a;    int size;    int bon;};void sortPrint(generator * g){    insertSort * sort1=new insertSort(g->a,g->size);    halfInsertSort * sort2 = new halfInsertSort(g->a,g->size);    shellSort * sort3 = new shellSort(g->a,g->size);    bubbleSort * sort4 = new bubbleSort(g->a,g->size);    quickSort * sort5 = new quickSort(g->a,g->size);    simpleSelectSort* sort6 = new simpleSelectSort(g->a,g->size);    heapSort * sort7 = new heapSort(g->a,g->size);    mergeSort * sort8 = new mergeSort(g->a,g->size);    ofstream out("data.txt");    sort1->sort();    sort1->print();    out<<"("<<sort1->compTime<<","<<sort1->swapTime<<") ";    sort2->sort();    sort2->print();    out<<"("<<sort2->compTime<<","<<sort2->swapTime<<") ";    sort3->sort();    sort3->print();    out<<"("<<sort3->compTime<<","<<sort3->swapTime<<") ";    sort4->sort();    sort4->print();    out<<"("<<sort4->compTime<<","<<sort4->swapTime<<") ";    sort5->sort();    sort5->print();    out<<"("<<sort5->compTime<<","<<sort5->swapTime<<") ";    sort6->sort();    sort6->print();    out<<"("<<sort6->compTime<<","<<sort6->swapTime<<") ";    sort7->sort();    sort7->print();    out<<"("<<sort7->compTime<<","<<sort7->swapTime<<") ";    sort8->sort();    sort8->print();    out<<"("<<sort8->compTime<<","<<sort8->swapTime<<") ";    out<<endl;    delete sort1;    delete sort2;    delete sort3;    delete sort4;    delete sort5;    delete sort6;    delete sort7;    delete sort8;}int main(){    generator* g = new generator();    int op;    while((op=printInstruction())!=0){        switch(op){        case 1:            g->print();            break;        case 2:            sortPrint(g);            break;        case 3:            delete g;            int sz,bon;            puts("请输入样本容量");            scanf("%d",&sz);            puts("请输入随机生成数最大值");            scanf("%d",&bon);            g = new generator(sz,bon);            g->print();            break;        default:            break;        }    }    delete g;    return 0;}