排序

快速排序

1.分而治之（递归）
选择主元，以及分。
细节重要

void quicksort(int left, int right, vector<int>& num) // 快速排序，从小到大
{
   
    if(left >= right)
        return;
    int i, j, base;
    i = left, j = right;
    base = num[left];  //取最左边的数为基准数
    while (i < j)
    {
   
        while (num[j] >= base && i < j)
            j--;
        while (num[i] <= base && i < j)
            i++;
        if(i < j)
        {
   
           swap(num[i],num[j]);
        }
    }
    //基准数归位
    num[left] = num[i];
    num[i] = base;
    quicksort(left, i - 1, num);//递归左边
    quicksort(i + 1, right, num);//递归右边
}
void Quick_sort() //快速排序
{
   
    clock_t start,finish;   //开始时间和结束时间
    double duration;        //算法所需时间
    vector<int>num;         //存随机数
    FILE *fw;
    if((fw=fopen("快速排序结果.txt","w+"))==NULL)//打开文件
    {
   
        cout<<"Wrong read."<<endl;
        exit(0);
    }
    for(int i=0; i<M; i++)
        num.push_back(mp[i]);

    start=clock();
    quicksort(0,M-1,num); //sort排序
    finish=clock();

    duration=(double)(finish - start)/CLOCKS_PER_SEC;//计算所需时间
    Map["快速排序"]=duration;
    cout<<"快速排序所需时间:\t"<<duration<<endl;

    for(int i=0; i<M; i++)//输入文件
    {
   
        fprintf(fw,"%d ",num[i]);
    }
    fclose(fw);
}

插入排序

void Insertion_sort() //插入排序
{
   
    clock_t start,finish;   //开始时间和结束时间
    double duration;        //算法所需时间
    int num[M];         //存随机数
    FILE *fw;
    if((fw=fopen("插入排序结果.txt","w+"))==NULL) //打开文件
    {
   
        cout<<"Wrong read."<<endl;
        exit(0);
    }
    for(int i=0; i<M; i++)
        num[i]=mp[i];

    start=clock();
    for(int i=1; i<M; i++)      //插入排序
    {
   
        for(int j=i; j>0; j--)
        {
   
            if(num[j-1]>num[j])
                swap(num[j],num[j-1]);
        }
    }

    finish=clock();

    duration=(double)(finish - start)/CLOCKS_PER_SEC;//计算所需时间
    Map["插入排序"]=duration;
    cout<<"插入排序所需时间:\t"<<duration<<endl;

    for(int i=0; i<M; i++)
    {
   
        fprintf(fw,"%d ",num[i]);
    }
    fclose(fw);
}

表排序

基数排序

希尔排序

void Shell_sotr() // 希尔排序
{
   
    clock_t start,finish;   //开始时间和结束时间
    double duration;        //算法所需时间
    int num[M];         //存随机数
    FILE *fw;
    if((fw=fopen("希尔排序结果.txt","w+"))==NULL) //打开文件
    {
   
        cout<<"Wrong read."<<endl;
        exit(0);
    }
    for(int i=0; i<M; i++)
        num[i]=mp[i];
    start=clock();
    /*希尔排序*/
    int h=1;
    while(h < M/3) h=3*h+1;  // 1,4,13,40...
    while(h>=1)
    {
   
        for(int i=h; i<M; i++)
        {
   
            for(int j=i; j>=h ; j-=h)
            {
   
                if(num[j-h]>num[j])
                {
   
                    swap(num[j-h],num[j]);
                }
            }
        }
        h=h/3;
    }

    finish=clock();

    duration=(double)(finish - start)/CLOCKS_PER_SEC;//计算所需时间
    Map["希尔排序"]=duration;
    cout<<"希尔排序所需时间:\t"<<duration<<endl;

    for(int i=0; i<M; i++)  //输入文件
    {
   
        fprintf(fw,"%d ",num[i]);
    }
    fclose(fw);
}