开发者社区> 问答> 正文

起泡排序算法程序怎么写

起泡排序算法程序怎么写

展开
收起
知与谁同 2018-07-22 20:08:50 1833 0
2 条回答
写回答
取消 提交回答
  • 12535
    冒泡?for(i=0;i<N;i++)for(j=i+1;j<N;j++)if(a[i]<a[j]){t=a[i],a[i]=a[j];a[j]=t;}让每个元素和它后面的相比较,如果大或者小,就交换,就能实现升排序或者降排序。
    2019-07-17 22:50:49
    赞同 展开评论 打赏
  • 云栖社区聚能聊、问答管理员~发福利、搞怪,八卦我来,论技术、发话题、写博客你上!
    //有多种排序法。你看一下#include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #define MAXSIZE 200000typedef int keytype;
    typedef struct
    {
    keytype key;
    }recordtype;typedef struct
    {
    recordtype r[MAXSIZE + 1];
    int length;
    }table;/**************************************************************/
    /* 二 分 法 插 入 排 序 算 法 */
    /**************************************************************/
    void binarysort(table *tab)
    {
    FILE *fa;
    fa = fopen("二分法插入排序.txt","w");
    int i,j,left,right,mid;
    for (i = 2; i <= tab->length; i++) //依次插入从第2个开始的所有元素
    {
    tab->r[0].key = tab->r[i].key; //保存待插入的元素
    left = 1;
    right = i - 1;
    while (left <= right) //查找第i个元素的插入位置
    {
    mid = (left + right)/2; //取中间位置
    if (tab->r[i].key < tab->r[mid].key)
    right = mid - 1;
    else
    left = mid + 1;
    } //插入位置为left
    for (j = i - 1; j >= left; j--)
    tab->r[j + 1].key = tab->r[j].key; //后移、空出插入位置
    tab->r[left].key = tab->r[0].key; //插入第i个元素的副本
    }
    fprintf(fa,"经过二分法插入排序之后的结果为: \n");
    for( i = 1; i <= tab->length; i++)
    fprintf(fa,"%d ",tab->r[i].key);
    fclose(fa);
    }/**************************************************************/
    /* 冒 泡 排 序 算 */
    /**************************************************************/
    void bubblesort(table *tab)
    {
    FILE *fb;
    fb = fopen("冒泡排序.txt","w");
    int i,j,done;
    i = 1;
    done = 1;
    while(i <= tab->length && done) //最多进行tab->length 次冒泡、如果没有发生交换则结束
    {
    done = 0;
    for (j = 1; j <= tab->length - i; j++)
    if(tab->r[j + 1].key < tab->r[j].key)
    {
    tab->r[0].key = tab->r[j].key; //以第0个元素作为中间单元进行交换
    tab->r[j].key = tab->r[j + 1].key;
    tab->r[j + 1].key = tab->r[0].key;
    done = 1;
    }
    i++;
    }
    fprintf(fb,"\n经过冒泡排序之后的结果为: \n");
    for( i = 1; i <= tab->length; i++)
    fprintf(fb,"%d ",tab->r[i].key);
    fclose(fb);
    }/**************************************************************/
    /* 快 速 排 序 算 法 */
    /**************************************************************/
    void quicksort(table *tab,int left,int right)
    {
    int i,j;
    if (left < right)
    {
    i = left;
    j = right;
    tab->r[0].key = tab->r[i].key; //准备以本次最左边的元素值为标准进行划分、先保存其值
    do
    {
    while(tab->r[j].key > tab->r[0].key && i < j) //从右向左找第1个不小于标准值的位置j
    j--;
    if (i < j)
    {
    tab->r[i].key = tab->r[j].key; //将第j个元素置于左端并重置i
    i++;
    }
    while(tab->r[i].key = tab->r[0].key && i < j) //从左向右找第1个不小于标准值的位置i
    i++;
    if (i < j)
    {
    tab->r[j].key = tab->r[i].key; //将第i个元素置于左端并重置j
    j--;
    }
    } while (i != j);
    tab->r[i].key = tab->r[0].key; //将标准值放入它的最终位置、本次划分结束
    quicksort(tab,left,i - 1); //对标准值左边递归调用本函数
    quicksort(tab,i + 1,right); //对标准值右边递归调用本函数
    }
    }/**************************************************************/
    /* 直 接 选 择 排 序 算 法 */
    /**************************************************************/
    void simpleselectsort(table *tab)
    {
    FILE *fc;
    fc = fopen("直接选择排序.txt","w");
    int i,j,k;
    for (i = 1; i <= tab->length -1; i++) //每次选择一个最小的元素(的位置)、和第i个元素交换
    {
    k = i; //记下当前最小元素的位置
    for (j = i + 1; j <= tab->length; j++) //向右查找更小的元素
    if (tab->r[j].key < tab->r[k].key) //修改当前最小元素的位置
    k = j;
    if (k != i) /*如果第i次选到的最小元素位置k不等于i、则将第k、i个元素交换*/
    {
    tab->r[0].key = tab->r[k].key; //以没有用到的第0个元素作为中间单元进行交换
    tab->r[k].key = tab->r[i].key;
    tab->r[i].key = tab->r[0].key;
    }
    }
    fprintf(fc,"\n经过直接选择排序之后的结果为: \n");
    for( i = 1; i <= tab->length; i++)
    fprintf(fc,"%d ",tab->r[i].key);
    fclose(fc);
    }/**************************************************************/
    /* 堆 排 序 算 法 */
    /**************************************************************/
    void sift(table *tab,int k,int m)
    {
    int i,j,finished;
    i = k;
    j = 2 * i;
    tab->r[0].key = tab->r[k].key;
    finished = 0;
    while ((j <= m) && (!finished))
    {
    if((j < m) && (tab->r[j + 1].key < tab->r[j].key))
    j++;
    if(tab->r[0].key <= tab->r[j].key)
    finished = 1;
    else
    {
    tab->r[i].key = tab->r[j].key;
    i = j;
    j = 2 * j;
    }
    }
    tab->r[i].key = tab->r[0].key;
    }
    void heapsort(table *tab)
    {
    FILE *fd;
    fd = fopen("堆排序.txt","w");
    int i;
    for (i = tab->length/2; i >= 1; i--)
    sift(tab,i,tab->length); //对所有元素建堆
    for (i = tab->length; i >= 2; i--) //i表示当前堆的大小、即等待排序的元素的个数
    {
    tab->r[0].key = tab->r[i].key;
    tab->r[i].key = tab->r[1].key;
    tab->r[1].key = tab->r[0].key; /*上述3条语句为将堆中最小元素和最后一个元素交换*/
    sift(tab,1,i - 1);
    }
    fprintf(fd,"\n经过堆排序之后的结果为: \n");
    for( i = 1; i <= tab->length; i++)
    fprintf(fd,"%d ",tab->r[i].key);
    fclose(fd);
    }
    /**************************************************************/
    /* 归 并 排 序 算 法 */
    /**************************************************************/
    void merge(table *tabs,table *tabg,int u,int m,int v)
    {
    int i,j,k,t;
    i = u;
    j = m + 1;
    k = u;
    while(i <= m && j <= v)
    {
    if (tabs->r[i].key <= tabs->r[j].key)
    {
    tabg->r[k].key = tabs->r[i].key;
    i++;
    }
    else
    {
    tabg->r[k].key = tabs->r[j].key;
    j++;
    }
    k++;
    }
    if(i <= m)
    for(t = i; t <= m; t++)
    tabg->r[k + t - i].key = tabs->r[t].key;
    else
    for(t = j; t <= v; t++)
    tabg->r[k + t - j].key = tabs->r[t].key;}
    void mergepass(table *tabs, table *tabg, int len)
    {
    int i,j,n;
    n = tabg->length = tabs->length;
    i = 1;
    while(i <= n - 2 * len + 1)
    {
    merge(tabs,tabg,i,i + len - 1,i + 2 * len - 1);
    i = i + 2 * len;
    }
    if (i + len - 1 < n)
    merge(tabs,tabg,i,i + len - 1,n);
    else
    for(j = i; j <= n; j++)
    tabg->r[j].key = tabs->r[j].key;
    }
    void mergesort(table *tab)
    {
    FILE *fe;
    fe = fopen("归并排序.txt","w");
    int len,i;
    table temp; //中间变量
    len = 1; //初始时有序段的长度为1
    while (len < tab->length) //有序段的长度小于待排序元素的个数、继续归并
    {
    mergepass(tab,&temp,len); //一趟归并、结果在temp中
    len = 2 * len;
    mergepass(&temp,tab,len); //一趟归并、结果在tab中
    len = 2 * len;
    }
    fprintf(fe,"\n经过归并排序之后的结果为: \n");
    for( i = 1; i <= tab->length; i++)
    fprintf(fe,"%d ",tab->r[i].key);
    }
    double max(double x,double y)
    {
    double z;
    z =(x>y)?x:y;
    return z;
    }
    /**************************************************************/
    /* 主 函 数 */
    /**************************************************************/
    void main()
    {
    printf("\n\n\n\n");
    printf(" /**********************************************************/\n");
    printf(" /*****************本程序使用了二分法插入排序***************/\n");
    printf(" /****冒泡排序、快速排序、直接选择排序、堆排序、归并排序****/\n");
    printf(" /**************运用六种方法找出三种较快的方法**************/\n");
    printf(" /***************结果已经保存在各文件的.txt中***************/\n");
    printf(" /**********************************************************/\n");

    int i;
    double max1,max2,max3;
    table tab;
    FILE *fs;
    fs = fopen("快速排序及其各种排序的速度.txt","w"); srand(10);
    for(i = 1; i <= MAXSIZE; i++)
    tab.r[i].key = rand() + 2000;
    tab.length = MAXSIZE;
    clock_t start, finish;
    double duration[6];
    start = clock();
    binarysort(&tab);
    finish = clock();
    duration[0] = (double)(finish - start) / CLOCKS_PER_SEC;
    printf( "二分法插入排序所花费的时间 %f seconds:\n ", duration[0]);
    start = clock();
    bubblesort(&tab);
    finish = clock();
    duration[1] = (double)(finish - start) / CLOCKS_PER_SEC;
    printf( "冒泡排序所花费的时间 %f seconds:\n ", duration[1]);
    fprintf(fs,"\n经过快速排序之后的结果为: \n");
    for( i = 1; i <= tab.length; i++)
    fprintf(fs,"%d ",tab.r[i].key);
    start = clock();
    quicksort(&tab,1,10);
    finish = clock();
    duration[2] = (double)(finish - start) / CLOCKS_PER_SEC;
    printf( "快速排序所花费的时间 %f seconds:\n ", duration[2]);

    start = clock();
    simpleselectsort(&tab);
    finish = clock();
    duration[3] = (double)(finish - start) / CLOCKS_PER_SEC;
    printf( "直接选择排序所花费的时间 %f seconds:\n ", duration[3]);

    start = clock();
    heapsort(&tab);
    finish = clock();
    duration[4] = (double)(finish - start) / CLOCKS_PER_SEC;
    printf( "堆排序所花费的时间 %f seconds:\n ", duration[4]);

    start = clock();
    mergesort(&tab);
    finish = clock();
    duration[5] = (double)(finish - start) / CLOCKS_PER_SEC;
    printf( "归并排序所花费的时间 %f seconds:\n ", duration[5]);

    fprintf( fs,"\n\n 二分法插入排序所花费的时间 %f seconds:\n ", duration[0]);
    fprintf( fs,"冒泡排序所花费的时间 %f seconds:\n ", duration[1]);
    fprintf( fs,"快速排序所花费的时间 %f seconds:\n ", duration[2]);
    fprintf( fs,"直接选择排序所花费的时间 %f seconds:\n ", duration[3]);
    fprintf( fs,"堆排序所花费的时间 %f seconds:\n ", duration[4]);
    fprintf( fs,"归并排序所花费的时间 %f seconds:\n ", duration[5]);

    max1 = max(duration[0],duration[1]);
    max2 = max(duration[2],duration[3]);
    max3 = max(duration[4],duration[5]); printf("\n\n\n");
    printf(" /**********************************************************/\n");
    if(max1 == duration[0])
    printf(" /***********************冒泡排序排序快*********************/\n");
    else
    printf(" /**********************二分法插入排序快********************/\n");
    if(max2 == duration[2])
    printf(" /***********************直接选择排序快*********************/\n");
    else
    printf(" /*************************快速排序快***********************/\n");
    if(max3 == duration[4])
    printf(" /*************************归并排序快***********************/\n");
    else
    printf(" /************************堆排序排序快**********************/\n");
    printf(" /**********************************************************/\n"); fclose(fs); //system("pause"); }
    2019-07-17 22:50:49
    赞同 展开评论 打赏
问答分类:
问答地址:
问答排行榜
最热
最新

相关电子书

更多
数据+算法定义新世界 立即下载
袋鼠云基于实时计算的反黄牛算法 立即下载
Alink:基于Apache Flink的算法平台 立即下载