首页 > 代码库 > 排序~~各种排序

排序~~各种排序

2024-07-13 13:27:49   224人阅读

poj2299

Ultra-QuickSort

Time Limit: 7000 MS Memory Limit: 65536 KB

64-bit integer IO format: %I64d , %I64u Java class name: Main

[Submit] [Status] [Discuss]

Description

In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence
9 1 0 5 4 ,

Ultra-QuickSort produces the output
0 1 4 5 9 .

Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.

Input

The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 -- the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.

Output

For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.

Sample Input

59105431230

Sample Output

60
#include <iostream>#include <string.h>#include <stdio.h>///#include <malloc.h>  ///要有头文件#include <stdlib.h>  ///上面的坑了我   会出现CE using namespace std;long long sum;  ///开始用int  不断的WAvoid Merge(int date[],int l,int m,int r){    int i,j,k;    int *pd;  ///动态内存空间的申请    pd=(int*)malloc((r-l+1)*sizeof(int)); ///malloc返回值是void  用（int*）强制转换  开辟（r-l+1）个int空间    i=l,j=m+1,k=0;   ///k是一个新的东东    while(i<=m&&j<=r)    {        if(date[j]>=date[i])        {            pd[k++]=date[i++];        }        else if(date[j]<date[i])        {            pd[k++]=date[j++];            sum+=(m+1-i);        }    }    while(i<=m)    pd[k++]=date[i++];    while(j<=r)    pd[k++]=date[j++];    for(int i=l,k=0;i<=r;i++,k++)    date[i]=pd[k];    free(pd);  ///释放pd所占的空间}///malloc 动态建立内存空间  可以是独立的指针也可以是数组名。。。///随机分配空间  不包含初始化内容void MergeSort(int date[],int l,int r){    int m;    if(l<r)    {        m=(r+l)/2;        MergeSort(date,l,m);        MergeSort(date,m+1,r);        Merge(date,l,m,r);    }}int main(){    int n;    int a[500005];    while(cin>>n)    {        if(n==0)        break;        sum=0;        for(int i=0;i<n;i++)        cin>>a[i];        MergeSort(a,0,n-1);        printf("%lld\n",sum);    }    return 0;}

题意：只可以移动连续的两个数  是数组一递增的顺序排列  最小的移动次数

阶梯思路：连续的两个进行移动   可以用冒泡吧~~~  不过好像太慢了    逆序数现代有木有学过   逆序数==本题答案

 

 

各种排序的简单介绍及用处：

冒泡排序（BubbleSort）：冒泡排序是最慢的排序算法。在实际运用中它是效率最低的算法。 时间复杂度是o（n^2)  一趟又一趟的比较  每次循环后会少比较一个

 

void BubbleSort(int a[],int n){    for(int i=n-1; i>0; i--)    {        exchange=0;        for(int j=0; j<=i-1; j++)        {            if(a[i]>a[j+1])            {                swap(a[i],a[j]);                exchange=1;            }        }        if(exchange=0)    }    return;}


并归排序（MergeSort）： 归并排序先分解要排序的序列，从1分成2，2分成4，依次分解，当分解到1个一组的时候，就可以排序这些分组，然后依次合并回原来的序列中，
                     这样就可以排序所有数据。合并排序比堆排序稍微快一点，但是需要比堆排序多一倍的内存空间，因为它需要一个额外的数组
                     ///并归往往不用来直接考察排序  而是用来求逆序数eg:poj2299
void Merge(int date[],int l,int m,int r){    int i,j,k;    int *pd;  ///动态内存空间的申请    pd=(int*)malloc((r-l+1)*sizeof(int)); ///malloc返回值是void  用（int*）强制转换  开辟（r-l+1）个int空间    i=l,j=m+1,k=0;   ///k是一个新的东东    while(i<=m&&j<=r)    {        if(date[j]>=date[i])        {            pd[k++]=date[i++];        }        else if(date[j]<date[i])        {            pd[k++]=date[j++];            sum+=(m+1-i);   ///逆序数的个数        }    }    while(i<=m)    pd[k++]=date[i++];    while(j<=r)    pd[k++]=date[j++];    for(int i=l,k=0;i<=r;i++,k++)    date[i]=pd[k];    free(pd);  ///释放pd所占的空间}///malloc 动态建立内存空间  可以是独立的指针也可以是数组名。。。///随机分配空间  不包含初始化内容void MergeSort(int date[],int l,int r){    int m;    if(l<r)    {        m=(r+l)/2;        MergeSort(date,l,m);        MergeSort(date,m+1,r);        Merge(date,l,m,r);    }}


快速排序（QuickSort）： 快速排序是一个就地排序，分而治之，大规模递归的算法。从本质上来说，它是归并排序的就地版本。快速排序可以由下面四步组成。

                                 （1） 如果不多于1个数据，直接返回。

             　　　　　　　（2） 一般选择序列最左边的值作为支点数据key值。在第一趟比较大小时key值保持不变  一遍后使大的在key值后面 小的在其前面

             　　　　　　　（3）将序列分成2部分，一部分都大于支点数据，另外一部分都小于支点数据。

             　　　　　　  （4）对两边利用递归排序数列。快速排序比大部分排序算法都要快。

            　　　　　　　 尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言没有比它更快的了。快速排序是递归的，对于内存非常有限的机器来说，它不是一个好的择

 

 void QuickSort(int a[],int l,int r) {     int i,j;     i=l;j=r;     a[0]=a[i];///令a[0]==key     while(i<j)     {         while(i<j&&a[j]>a[0]) j--;         if(i<j) a[i++]=a[j];         while(i<j%%a[i]<a[0]) i++;         if(i<j) a[j--]=a[i];     }     a[i]=a[0];     if(l<r)     QuickSort(a,i,i-1);     QuickSort(a,i+1,r); }

堆排序：堆排序适合于数据量非常大的场合（百万数据）。堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，因为快速排序，

           归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。堆排序会将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数据和序列的最后一个

           数据交换。接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据

请见下回分解~~~~~~

 

 

 

 


联系
我们