|
#include<bits/stdc++.h>
using namespace std;
int a[1000001],n;
int b[1000001],tmp[1000001];
int GetMax(int a[],int n)
{
?? ?int max=a[0];
?? ?for(int i=1;i<n;i++){
?? ??? ?if(a[i]>max) ? max = a[i];
?? ?}
?? ?return max;
}
void QuickSort(int q[], int l, int r)
{
?? ?if (l >= r) return;
?? ?int i = l - 1, j = r + 1, x = q[l + r >> 1];
?? ?while (i < j)
?? ?{
?? ? ? ?do i ++ ; while (q[i] < x);
?? ? ? ?do j -- ; while (q[j] > x);
??? ? ? if (i < j) swap(q[i], q[j]);
?? ?}
?? ?QuickSort(q, l, j), QuickSort(q, j + 1, r);
}
int ans;
void MergeSort(int q[],int l,int r)
{
?? ?if(l==r)return;
?? ?int i=l,mid=(l+r)/2,j=mid+1,k=l;
?? ?
?? ?MergeSort(q,l,mid);
?? ?MergeSort(q,mid+1,r);
?? ??? ?
?? ?while(i<=mid&&j<=r)
?? ?{
??? ? ? if(q[i]<=q[j]){
??? ? ? ??? ?tmp[k++]=q[i++];
??? ? ? }
??? ? ? else{
??? ? ? ??? ?ans=ans+j-k;
?? ? ? ??? ?tmp[k++]=q[j++];
?? ? ? ?}
?? ??? ?}
?? ?while(i<=mid) tmp[k++]=q[i++];
?? ?while(j<=r) tmp[k++]=q[j++];
?? ?for(int i=l;i<=r;i++)
? ??? ??? ?q[i]=tmp[i];
}
void MergeFindSort( int a[] , int n )
{
?? ?int low , high , mid ;
? ? int temp ;
? ? for ( int i=1 ; i<n ; i++ )
? ? {
? ? ? ? temp = a[i ];
? ? ? ? low = 0 ;
? ? ? ? high = i - 1 ;
? ? ? ? while ( low <= high )
? ? ? ? {
? ? ? ? ? ? mid = ( low + high ) / 2 ;
? ? ? ? ? ? if ( a[mid] > temp )
? ? ? ? ? ? ? ? high = mid - 1 ;
? ? ? ? ? ? else
? ? ? ? ? ? ? ? low = mid + 1 ;
? ? ? ? }
? ? ? ? for ( int j = i - 1 ; j > high ; j-- )
? ? ? ? ? ? a[j+1] = a[j] ;
? ? ? ? a [high+1] = temp ;
? ? }
}
void ShellSort(int arr[], int len)
{
?? ?int i, j, temp, jump=len>>1;
?? ?while (jump != 0)
?? ?{
?? ??? ?for (i = jump; i < len; i++)
?? ??? ?{
?? ??? ??? ?temp = arr[i];
?? ??? ??? ?j = i - jump;
?? ??? ??? ?while (j >= 0 && temp < arr[j])
?? ??? ??? ?{
?? ??? ??? ??? ?arr[j + jump] = arr[j];
?? ??? ??? ??? ?j=j-jump;
?? ??? ??? ?}
?? ??? ??? ?arr[j + jump] = temp;
?? ??? ?}
?? ??? ?jump/=2;;
?? ?}
}
void CountingSort(int a[],int n)
{
?? ?int m = GetMax(a,n);
?? ?int b[m+1]={0};
?? ?for(int j=0;j<n;j++) ? b[a[j]]++;
?? ?for(int i=0,k=0;i<=m||k<n;i++)
?? ?{
?? ??? ?while(b[i]>0){
?? ??? ??? ?a[k++] = i;
?? ??? ??? ?b[i]--;
?? ??? ?}
?? ?}?
}
void RadixSort(int*a,int length)
{
?? ?int max=a[0];
?? ?for(int i=1;i<length;i++)
?? ?{
?? ??? ?if(a[i]>max)
?? ??? ?{
?? ? ??? ??? ?max=a[i];
?? ??? ?}
?? ?}
?? ?int base=1;
?? ?int *b=(int*)malloc(sizeof(int)*length);
?? ?int i;
?? ?while(max/base>0)
?? ?{
?? ??? ?int t[10]={0};
?? ??? ?for(i=0;i<length;i++)
?? ??? ?{
? ?? ??? ??? ?t[a[i]/base%10]++;
?? ??? ?}
?? ??? ?for(i=1;i<10;i++)
?? ??? ?{
?? ??? ??? ?t[i]+=t[i-1];
?? ??? ?}
?? ??? ?for(i=length-1;i>=0;i--)
?? ??? ?{
?? ??? ??? ?b[t[a[i]/base%10]-1]=a[i];
?? ??? ??? ?t[a[i]/base%10]--;
?? ??? ?}
?? ??? ?for(i=0;i<length;i++)
?? ??? ?{
?? ??? ??? ?a[i]=b[i];
?? ??? ?}
?? ??? ?base=base*10;
?? ?}
}
void InsertSort(int* a, int n)
{
?? ?int i = 0;
?? ?for (i = 0; i < n - 1; i++)
?? ?{
?? ??? ?int end = i;
?? ??? ?int tmp = a[end + 1];
?? ??? ?while (end >= 0)
?? ??? ?{
?? ??? ??? ?if (tmp < a[end])
?? ??? ??? ?{
?? ??? ??? ??? ?a[end + 1] = a[end];
?? ??? ??? ??? ?end--;
?? ??? ??? ?}
?? ??? ??? ?else
?? ??? ??? ?{
?? ??? ??? ??? ?break;
?? ??? ??? ?}
?? ??? ?}
?? ??? ?a[end + 1] = tmp;
?? ?}
}
void BubbleSort(int a[],int n)
{
?? ?for(int i=0;i<n;i++)
?? ?{
?? ??? ?for(int j=0;j<n-i-1;j++)
?? ??? ?{
?? ??? ??? ?if(a[j]>a[j+1])
?? ??? ??? ?{
?? ??? ??? ??? ?int t=a[j];
?? ??? ??? ??? ?a[j]=a[j+1];
?? ??? ??? ??? ?a[j+1]=t;
?? ??? ??? ?}
?? ??? ?}
?? ?}
}
void SelectSort(int arry[], int len)
{ ? ? ?
?? ?int i;
? ? int j;
? ? for ( i = 0; i < len-1; i++)
? ? {
? ? ? ? int min = i;
? ? ? ? for (j = i + 1; j < len; j++)
?? ??? ?{
? ? ? ? ? ?if (arry[j] < arry[min])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? min = j;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? int temp = arry[min];
? ? ? ? arry[min] = arry[i];
? ? ? ? arry[i] = temp;
? ? }
}
int main()
{
?? ?cin>>n;
?? ?for(int i=0;i<n;i++)
?? ??? ?cin>>a[i];
?? ??? ?
?? ?cout<<endl<<endl;?
?? ?
?? ?cout<<"数组a中有";
?? ?
?? ?MergeSort(a,0,n-1);
?? ?cout<<ans;
?? ?stable_sort(a,a+n);
?? ?
?? ?cout<<"队逆序对";
?? ?
?? ?cout<<endl<<endl;
?? ?
?? ?RadixSort(a,n);
?? ?
?? ?CountingSort(a,n);
?? ?
?? ?ShellSort(a,n);
?? ?
?? ?MergeFindSort(a,n);
?? ?
?? ?InsertSort(a,n);
?? ?
?? ?BubbleSort(a,n);
?? ?
?? ?SelectSort(a,n);
?? ?
?? ?
?? ?QuickSort(a,0,n-1);
?? ?sort(a,a+n);
?? ?for(int i=0;i<n;i++)
??? ? ? cout<<a[i]<<" ";
?? ?return 0;
}
|