09-排序1 排序（25 分）

给定$N$个（长整型范围内的）整数，要求输出从小到大排序后的结果。

本题旨在测试各种不同的排序算法在各种数据情况下的表现。各组测试数据特点如下：

数据1：只有1个元素；

数据2：11个不相同的整数，测试基本正确性；

数据3：10

3个随机整数；

数据4：10

4个随机整数；

数据5：10

5个随机整数；

数据6：10

5个顺序整数；

数据7：10

5个逆序整数；

数据8：10

5个基本有序的整数；

数据9：10

5个随机正整数，每个数字不超过1000。

输入格式:

输入第一行给出正整数$N$（≤10​5​​），随后一行给出$N$个（长整型范围内的）整数，其间以空格分隔。

输出格式:

在一行中输出从小到大排序后的结果，数字间以1个空格分隔，行末不得有多余空格。

输入样例:

114 981 10 -17 0 -20 29 50 8 43 -5

输出样例:

-20 -17 -5 0 4 8 10 29 43 50 981

#include
    
     #include
     
      #include
      
       using namespace std;const int cutoff = 10000;int Incre[3] = {4,2,1};void SimpleSelectSort(int A[],int n){    int i,j,min,temp;    for(i=0;i
       
         A[child])            child++;        if(temp < A[child]) A[i] = A[child];        else break;    }    A[i] = temp;}void HeapSort(int A[],int n){    int i,temp;    for(i=(n-1)/2;i>=0;i--){        Adjust(A,i,n);    }    for(i=n-1;i>0;i--){        temp = A[0];        A[0] = A[i];        A[i] = temp;        Adjust(A,0,i);    }}void InsertSort(int A[],int n){    int i,j,temp;    for(i=1;i
        
         0 && temp
         
          =0 && temp
          
           =0;i--){ flag = 0; for(j=0;j
           
             A[j+1]){ temp = A[j]; A[j] = A[j+1]; A[j+1] = temp; flag = 1; } } if(!flag) break; }}//MergeSort Recurrencevoid Merge(int A[],int tmpA[],int l,int r,int rightEnd){ int leftEnd = r - 1,tmp = l; int num = rightEnd - l + 1; while(l <= leftEnd && r <= rightEnd){ if(A[l] <= A[r]) tmpA[tmp++] = A[l++]; else tmpA[tmp++] = A[r++]; } while(l <= leftEnd) tmpA[tmp++] = A[l++]; while(r <= rightEnd) tmpA[tmp++] = A[r++]; for(int i=0;i
            
             < n;j++) tmpA[j] = A[j];}void Merge_sort(int A[],int n){ int *tmpA = new int[n]; int len = 1; if(tmpA != NULL){ while(len < n){ Merge_pass(A,tmpA,n,len); len *= 2; Merge_pass(tmpA,A,n,len); len *= 2; } delete [] tmpA; } else throw "NO space";}//QuickSortvoid Swap(int *a,int *b){ int temp = *a; *a = *b; *b = temp;}int Median3(int A[],int left,int right){ int center = (left + right)/2; if(A[left] > A[center]) Swap(&A[left],&A[center]); if(A[left] > A[right]) Swap(&A[left],&A[right]); if(A[center] > A[right]) Swap(&A[center],&A[right]); Swap(&A[center],&A[right - 1]); return A[right - 1];}void Qsort(int A[],int left,int right){ if(cutoff <= right - left){ int pivot = Median3(A,left,right); int i = left,j = right - 1; while(1){ while(A[++i] < pivot) {} while(A[--j] > pivot) {} if(i < j) Swap(&A[i],&A[j]); else break; } Swap(&A[i],&A[right - 1]); Qsort(A,left,i-1); Qsort(A,i+1,right); } else InsertSort(A+left,right-left+1);}void QuickSort(int A[],int n){ Qsort(A,0,n-1);}//RadixSort myselfvoid RadixSort(int A[],int n){ int i,j,k,radix,R = 1,cnt = 0; vector
             
              v1[10],v2[10]; for(i=0;i
              
               = p) { p *= 10; ++d; } } return d;}void radixsort(int data[], int n) //基数排序{ int d = maxbit(data, n); int tmp[n]; int count[10]; //计数器 int i, j, k; int radix = 1; for(i = 1; i <= d; i++) //进行d次排序 { for(j = 0; j < 10; j++) count[j] = 0; //每次分配前清空计数器 for(j = 0; j < n; j++) { k = (data[j] / radix) % 10; //统计每个桶中的记录数 count[k]++; } for(j = 1; j < 10; j++) count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶 for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中 { k = (data[j] / radix) % 10; tmp[count[k] - 1] = data[j]; count[k]--; } for(j = 0; j < n; j++) //将临时数组的内容复制到data中 data[j] = tmp[j]; radix = radix * 10; }}int main(){ int n; cin>>n; int A[n]; for(int i=0;i
               
                >A[i]; RadixSort(A,n); for(int i=0;i