首页 > 代码库 > Poj 2299 Ultra-QuickSort
Poj 2299 Ultra-QuickSort
1.Link：
http://poj.org/problem?id=2299
2.Content：
Ultra-QuickSort
Time Limit: 7000MS Memory Limit: 65536K Total Submissions: 41876 Accepted: 15208 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 output0 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
59105431230Sample Output
60Source
Waterloo local 2005.02.05
3.Method:
4.Code:
1 #include<iostream> 2 #include<stdio.h> 3 using namespace std; 4 int a[500002]; 5 6 //递归2路归并排序 7 /*void Merge(long long a[],long long b[],int s,int m,int t) 8 { 9 int i=s,j=m+1,k=s; 10 while((i<=m)&&(j<=t)) 11 { 12 if(a[i]<=a[j]) b[k++]=a[i++]; 13 else b[k++]=a[j++]; 14 } 15 while(i<=m) b[k++]=a[i++]; 16 while(j<=t) b[k++]=a[j++]; 17 } 18 void MSort(long long a[],long long b[],int s,int t ,int size) 19 { 20 int m; 21 long long c[size]; 22 if(s==t) b[s]=a[t]; 23 else 24 { 25 m=(s+t)/2; 26 MSort(a,c,s,m,size); 27 MSort(a,c,m+1,t,size); 28 Merge(c,b,s,m,t); 29 } 30 } 31 void MergeSort(long long a[],int size) 32 { 33 MSort(a,a,0,size-1,size); 34 }*/ 35 36 37 // 非递归合并排序 38 /*template<class T> 39 void Merge(T a[],T b[],int s,int m,int t) 40 { 41 int i=s,j=m+1,k=s; 42 while(i<=m&&j<=t) 43 { 44 if(a[i]<a[j]) b[k++]=a[i++]; 45 else b[k++]=a[j++]; 46 } 47 while(i<=m) b[k++]=a[i++]; 48 while(j<=t) b[k++]=a[j++]; 49 } 50 template<class T> 51 void MergePass(T a[],T b[],int s,int t) 52 { 53 int i; 54 for(i=0;i+2*s<=t;i=i+2*s) 55 { 56 Merge(a,b,i,i+s-1,i+2*s-1); 57 } 58 //剩下的元素个数少于2s 59 if(i+s<t) Merge(a,b,i,i+s-1,t); 60 else for(int j=i;j<=t;j++) b[j]=a[j]; 61 } 62 template<class T> 63 void MergeSort(T a[],int n) 64 { 65 T *b=new T[n]; 66 //T b[n]; 67 int s=1; 68 while(s<n) 69 { 70 MergePass(a,b,s,n); 71 s+=s; 72 MergePass(b,a,s,n); 73 s+=s; 74 } 75 }*/ 76 77 long long count=0; 78 //求逆序对 79 void Merge(int a[],int b[],int s,int m,int t) 80 { 81 int i=s,j=m+1,k=s; 82 //int count=0; 83 while(i<=m&&j<=t) 84 { 85 if(a[i]<=a[j]) b[k++]=a[i++]; 86 else 87 { 88 b[k++]=a[j++]; 89 count+=m-i+1; 90 } 91 92 } 93 while(i<=m) b[k++]=a[i++]; 94 while(j<=t) b[k++]=a[j++]; 95 //return count; 96 } 97 void MergePass(int a[],int b[],int s,int t) 98 { 99 int i;100 //int count=0;101 for(i=0;i+2*s<=t;i=i+2*s)102 {103 Merge(a,b,i,i+s-1,i+2*s-1);104 }105 //剩下的元素个数少于2s106 if(i+s<t) Merge(a,b,i,i+s-1,t-1);107 else for(int j=i;j<=t;j++) b[j]=a[j]; 108 //return count;109 }110 void MergeSort(int a[],int n)111 {112 int *b=new int[n];113 //int b[n];114 //int count=0;115 int s=1;116 while(s<n)117 {118 MergePass(a,b,s,n);119 s+=s;120 MergePass(b,a,s,n);121 s+=s;122 }123 }124 125 126 127 int main()128 {129 130 //测试排序正确性 131 /*int a[10];132 for(i=0;i<10;i++) a[i]=10-i;133 for(i=0;i<10;i++) cout<<a[i]<<" ";134 cout<<endl;135 cout<<MergeSort(a,10)<<endl;136 for(i=0;i<10;i++) cout<<a[i]<<" ";*/137 138 int size;139 int i;140 while((cin>>size)&&size!=0)141 {142 count=0;143 for(i=0;i<size;i++)144 {145 scanf("%lld",&a[i]);146 }147 MergeSort(a,size);148 printf("%lld\n",count);149 //测试排序正确性150 //for(i=0;i<size;i++) printf("%lld ",a[i]);151 }152 //system("pause");153 return 1;154 }
5.Reference:
Poj 2299 Ultra-QuickSort
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。