排序---快排-希尔排序-桶排-堆排序-归并排序

曾经终败给现在 2022-07-12 11:14 278阅读 0赞

#### 排序1（快速排序）：    ####

#### Problem Description ####

给定N(N≤10^5)个整数，要求用快速排序对数据进行升序排列，注意不得使用STL。

#### Input ####

连续输入多组数据，每组输入数据第一行给出正整数N(≤10^5)，随后给出N个整数，数字间以空格分隔。

#### Output ####

输出排序后的结果，数字间以一个空格间隔，行末不得有多余空格。

#### Example Input ####

8
    49 38 65 97 76 13 27 49

#### Example Output ####

13 27 38 49 49 65 76 97
     #include<stdio.h>
    int a[100000];
    void qqsort(int left,int right)
    {
        int i,j,mid;
        i=left; j=right;
        mid=a[i];  //将处于中间的比较的值赋值为a[i]
        if(i>=j)
            return ;
        while(i<j)
        {
            while(i<j&&a[j]>=mid)
                j--;        //如果比mid大，就继续比较前一个，直到找到
            a[i]=a[j];   //直到找到一个数比mid小的数，放到mid位置的前面去
            while(i<j&&a[i]<=mid)
                i++;      //如果比mid小，就继续比较后一个，直到找到
            a[j]=a[i];   //直到找到一个数比mid大的数，放到mid位置的后面去
        }
        a[i]=mid;
        qqsort(left,i-1);  //调整左边
        qqsort(j+1,right); //调整右边
    }
    int main()
    {
        int i,n;
        while(scanf("%d",&n)!=EOF)
        {
            for(i=0;i<n;i++)
            {
                scanf("%d",&a[i]);
            }
            qqsort(0,n-1);  //快速排序
            for(i=0;i<n;i++)
            {
                if(i!=n-1)
                {
                    printf("%d ",a[i]);
                }
                else
                {
                    printf("%d\n",a[i]);
                }
            }
        }
        return 0;
    }
     排序2（希尔排序）：                                          数据结构实验之排序六：希尔排序                                  Time Limit: 1000MS Memory Limit: 65536KB Problem Description 
      
       
       
        我们已经学习了各种排序方法，知道在不同的情况下要选择不同的排序算法，以期达到最好的排序效率；对于待排序数据来说，若数据基本有序且记录较少时， 直接插入排序的效率是非常好的，希尔排序就是针对一组基本有序的少量数据记录进行排序的高效算法。你的任务是对于给定的数据进行希尔排序，其中增量dk=n/(2^k)(k=1,2,3……) 
      
       Input 
      
       
       
        连续输入多组数据，每组输入数据的第一行给出一个正整数N(N <= 10000)，随后连续给出N个整数表示待排序关键字，数字间以空格分隔。 
       
        
        
          
       
        
      
       Output 
      
       
       
        输出dk=n/2和dk=1时的结果。 
      
       Example Input 
      
       
       
        10
    10 9 8 7 6 5 4 3 2 1
    10
    -5 9 7 -11 37 -22 99 288 33 66 
      
       Example Output 
      
       
       
        5 4 3 2 1 10 9 8 7 6
    1 2 3 4 5 6 7 8 9 10
    -22 9 7 -11 37 -5 99 288 33 66
    -22 -11 -5 7 9 33 37 66 99 288
    
     #include<stdio.h>
    #define maxn 10005
    
    int a[maxn];
    
    void ShellSort(int n,int dk)
    {
        int i,j,k;
        int temp;
        for(i=0;i<dk;i++)
        {
            for(j=i;j<n;j+=dk)
            {
                if(a[j+dk] < a[j] && j+dk<n)
                {
                    temp = a[j+dk];
                    k = j;
                    while(k>=0 && temp<a[k])
                    {
                        a[k+dk] = a[k];
                        k -= dk;
                    }
                    a[k+dk] = temp;
                }
            }
        }
    }
    
    void show(int n)
    {
        int i;
        for(i=0;i<n;i++)
        {
            if(i!=n-1)
            {
                printf("%d ",a[i]);
            }
            else
            {
                printf("%d\n",a[i]);
            }
        }
    }
    
    int main()
    {
        int i;
        int n;
        while(scanf("%d",&n)!=EOF)
        {
            for(i=0;i<n;i++)
            {
                scanf("%d",&a[i]);
            }
            ShellSort(n,n/2);
            show(n);
            ShellSort(n,1);
            show(n);
        }
        return 0;
    }
     
    
     
      
       排序3：bucket sort(桶排序）                                  数据结构实验之排序三：bucket sort 
      
       
       
                                   Time Limit: 250MS Memory Limit: 65536KB
      
       
     Problem Description 
      
       
       
        根据人口普查结果，知道目前淄博市大约500万人口，你的任务是帮助人口普查办公室按年龄递增的顺序输出每个年龄有多少人，其中不满1周岁的按0岁计算，1到2周岁的按1岁计算，依次类推，大于等于100岁的老人全部按100岁计算。 
      
       Input 
      
       
       
         输入第一行给出一个正整数N(<=5000000)，随后连续给出N个整数表示每个人的年龄，数字间以空格分隔。 
      
       Output 
      
       
       
         按年龄递增的顺序输出每个年龄的人口数，人口数为0的不输出，每个年龄占一行，数字间以一个空格分隔，行末不得有多余空格或空行。 
       
          
      
       Example Input 
      
       
       
        10
    16 71 17 16 18 18 19 18 19 20 
      
       Example Output 
      
       
       
        16 2
    17 1
    18 3
    19 2
    20 1
    71 1
     
      
       #include<stdio.h>
    #include<string.h>
    int a[105]; //全局变量的初始值，系统自动设置为0。
    
    void bucket_sort(int n)
    {
        int i;
        for(i=0;i<=100;i++)
        {
            if(a[i])
            {
                printf("%d %d\n",i,a[i]);
            }
        }
    }
    
    int main()
    {
        int i,n;
        int k;
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            scanf("%d",&k);
            if(k>100)
            {
                a[100]++;
            }
            else
            {
                a[k]++;
            }
        }
        bucket_sort(n);
        return 0;
    } 
    排序4（堆排序）：
                                     数据结构实验之排序四：寻找大富翁 
      
       
       
                                    Time Limit: 200MS Memory Limit: 512KB
      
       
     Problem Description 
      
       
       
        2015胡润全球财富榜调查显示，个人资产在1000万以上的高净值人群达到200万人，假设给出N个人的个人资产值，请你快速找出排前M位的大富翁。 
      
       Input 
      
       
       
        首先输入两个正整数N( N ≤ 10^6)和M(M ≤ 10)，其中N为总人数，M为需要找出的大富翁数目，接下来给出N个人的个人资产，以万元为单位，个人资产数字为正整数，数字间以空格分隔。 
      
       Output 
      
       
       
        一行数据，按降序输出资产排前M位的大富翁的个人资产值，数字间以空格分隔，行末不得有多余空格。 
       
          
      
       Example Input 
      
       
       
        6 3
    12 6 56 23 188 60 
      
       Example Output 
      
       
       
        188 60 56
    
     
      
       #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #define maxn 15
    typedef struct node
    {
        int a[maxn];
        int length;
    }Heap;
    Heap h;
    
    void init(int n,int m)
    {
        int i,j;
        int k;
        int min,u;
        for(i=1;i<=m;i++)
        {
            scanf("%d",&h.a[i]);
        }
        for(i=m+1;i<=n;i++)
        {
            scanf("%d",&k);
            min = h.a[1];
            u = 1;
            for(j=2;j<=m;j++)
            {
                if(h.a[j] < min)
                {
                    min = h.a[j];
                    u = j;
                }
            }
            if(k > h.a[u])
            {
                h.a[u] = k;
            }
        }
        h.length = m;
    }
    
    void HeapAdjust(int s,int e)
    {
        int j;
        int temp = h.a[s];
        for(j=2*s; j<=e ;j*=2)
        {
            if(j<e && h.a[j+1] < h.a[j])
            {
                j++;
            }
            if(temp < h.a[j])
            {
                break;
            }
            h.a[s] = h.a[j];
            s = j;
        }
        h.a[s] = temp;
    }
    
    void HeapSort(int m)
    {
        int i;
        int temp;
        for(i=h.length/2;i>=1;i--)
        {
            HeapAdjust(i,h.length);
        }
        for(i=h.length;i>1;i--)
        {
            temp = h.a[1];
            h.a[1] = h.a[i];
            h.a[i] = temp;
            HeapAdjust(1,i-1);
        }
        for(i=1;i<=m;i++)
        {
            if(i!=m)
            {
                printf("%d ",h.a[i]);
            }
            else
            {
                printf("%d\n",h.a[i]);
            }
        }
    }
    
    int main()
    {
        int n,m;
        scanf("%d%d",&n,&m);
        init(n,m);
        HeapSort(m);
        return 0;
    }排序5（归并排序）：
                                          数据结构实验之排序五：归并求逆序数 
      
       
       
                                       Time Limit: 50MS Memory Limit: 65536KB
      
       
      
       Problem Description 
      
       
       
        对于数列a1,a2,a3…中的任意两个数ai,aj (i < j)，如果ai > aj,那么我们就说这两个数构成了一个逆序对；在一个数列中逆序对的总数称之为逆序数，如数列 1 6 3 7 2 4 9中，(6,4)是一个逆序对，同样还有(3,2),(7,4),(6,2)，(6,3)等等，你的任务是对给定的数列求出数列的逆序数。 
      
       Input 
      
       
       
        输入数据N(N <= 100000)表示数列中元素的个数，随后输入N个正整数，数字间以空格间隔。 
       
          
      
       Output 
      
       
       
        输出逆序数。 
      
       Example Input 
      
       
       
        10
    10 9 8 7 6 5 4 3 2 1 
      
       Example Output 
      
       
       
        45
     #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #define maxn 100005
    
    int record[maxn];
    int add[maxn];
    long long sum;
    
    void MSort(int l,int mid,int r)
    {
        int i = l;
        int j = mid+1;
        int k = l;
        int x;
        while(i<=mid && j<=r)
        {
            if(record[i] <= record[j])
            {
                add[k++] = record[i++];
            }
            else
            {
                add[k++] = record[j++];
                sum += (mid - i + 1);
            }
        }
        while(i<=mid)
        {
            add[k++] = record[i++];
        }
        while(j<=r)
        {
            add[k++] = record[j++];
        }
        for(x=l;x<=r;x++)
        {
            record[x] = add[x];
        }
    }
    
    void MergeSort(int l,int r)
    {
        int mid = (l+r)/2;
        if(l<r)
        {
            MergeSort(l,mid);
            MergeSort(mid+1,r);
            MSort(l,mid,r);
        }
    }
    
    int main()
    {
        int i;
        int n;
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            scanf("%d",&record[i]);
        }
        MergeSort(0,n-1);
        printf("%lld\n",sum);
        return 0;
    }