C语言数据结构归并排序和快速排序的对比

我不是女神ヾ 2022-01-21 23:51 159阅读 0赞

/\*  
\*归并排序算法  
\*快速排序算法和其的对比  
\*归并排序函数基于递归的思想  
\*将其划分为 一个 两个 四个 八个。。。 直到不满足条件为止  
\*最后运用合并函数将两个划分块和并在一起 并保证优先排序  
\*/

#include<stdio.h>
    #include<stdlib.h>
    void Merge_sort(int *a,int i,int j,int *b);//归并排序算法函数
    void Merge(int *a,int s1,int e1,int s2,int e2,int *b);//合并函数
    void Quick_sort(int *n,int i,int j);//快速排序函数
    int  partition(int *n,int i,int j);//划分排序函数
    void main()
    {
        int m;//数据节点的个数
        int n[100];//待排序的数组
        int s[100];//合并的临时数组  起到临时存储的作用
        int i;
        printf("请输入数据的个数:\n");
        scanf("%d",&m);
        printf("请依次输入数据:\n");
        for(i=0;i<m;i++)
              scanf("%d",&n[i]);
        printf("===========归并排序算法============\n");
          Merge_sort(n,0,m-1,s);
          for(i=0;i<m;i++)
              printf("%d\t",n[i]);
          printf("\n");//换行
              printf("===========快速排序算法============\n");
              Quick_sort(n,0,m-1);
              for(i=0;i<m;i++)
                printf("%d\t",n[i]);
              printf("\n");
    
    
    
    }
    void Merge_sort(int *a,int i,int j,int *b)
    {
        int k;
        if(i<j)
        {
            k=(i+j)/2;
            Merge_sort(a,i,k,b);
            Merge_sort(a,k+1,j,b);//递归的思想的体现
            Merge(a,i,k,k+1,j,b);//合并递归之后的数组  最后输出
        }
    }
    void Merge(int *a,int s1,int e1,int s2,int e2,int *b)
    {
        int  k=s1;//k用于b数组的动态临时下标
        int i=s1;//用于之后将b数组中的数据赋值给a数组
          while(s1<=e1&&s2<=e2)//两个分组不为空
          {
              if(a[s1]<=a[s2])//将两个分组中数值较小的数组元素 赋值给临时数组b
                {
                    b[k++]=a[s1++];
                }
                else
                b[k++]=a[s2++];
            }
            if(s1<=e1)
                b[k++]=a[s1++];//若s1数组中有剩余元素直接将剩余元素移动到临时数组b中
              if(s2<=e2)
               b[k++]=a[s2++];//若s2数组中有剩余元素直接将剩余元素移动到临时数组b中
               k--;//此时k的值为当前b数组中最后一个元素的下标
               //将b数组中的元素移动到a数组中去
                 while(k>=i)
                 {
                     a[k]=b[k];
                     k--;//赋值操作
                 }
    }
    void  Quick_sort(int *n,int i,int j)
    {
        int k;
        if(i<j)
        {
            k=partition(n,i,j);
            Quick_sort(n,i,k);
            Quick_sort(n,k+1,j);
        }
    }
    int  partition(int *n,int i,int j)
    {
        int temp;//中间临时变量
        temp=n[i];
        while(i<j)
        {
            while(i<j&&temp<n[j])
            {
                j--;
            }
            if(i<j)
            {
                n[i++]=n[j];
            }
            while(n[i]<temp&&i<j)
            {
                i++;
    
            }
            if(i<j)
            n[j--]=n[i];
    
    
        }
           n[i]=temp;
           return i;//返回划分之后的节点的下标
    
    
    }