排序算法

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<stack>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<set>
#include<map>
#define MAX 100
using namespace std;
int n,a[MAX];
/*冒泡排序*/
void bubblesort(int a[],int n){
     int  tmp;
     for(int i=n-1;i>0;i--){
         for(int j=0;j<i;j++){
             if(a[j]>a[j+1]){  /*比较相邻的两个数，如果前面的数比后面的大，交换顺序*/
                  tmp=a[j];
                  a[j]=a[j+1];
                  a[j+1]=tmp;
              }
          }
      }
      for(int i=0;i<n;i++)  /*输出*/
          cout<<a[i]<<" ";
      cout<<endl;
}

/*选择排序*/
void selectionsort(int a[],int n){
    int tmp,cnt;
    for(int i=0;i<n-1;i++){
         cnt=i;
         /*每次比较找出当前最小值，与未排序部分的第一个数交换位置*/
         for(int j=i+1;j<n;j++)                        
             if(a[cnt]>a[j]) cnt=j;
         if(cnt!=i){
             tmp=a[i];
             a[i]=a[cnt];
             a[cnt]=tmp;
         }
     }
     for(int i=0;i<n;i++) cout<<a[i]<<" ";
     cout<<endl;
}

/*插入排序*/
void insrtsort(int a[],int n){
     for(int i=1;i<n;i++){
         int tmp;
         for(int j=0;j<i;j++){        
         /*将一个数与它前面已排序的数比较，如果找到比它大的数，将这个数到比较数前面的数的位置往后移，将这个数放到找到的位置上*/
              if(a[i]<a[j]){                                           
                  tmp=a[i];
                  for(int k=i-1;k>=j;k--)
                      a[k+1]=a[k];
                   a[j]=tmp;
               }
           }
       }
       for(int i=0;i<n;i++)  cout<<a[i]<<" ";
       cout<<endl;
}

/*计数排序*/
void countsort(int a[],int n){
    int b[5000],size=a[0];
    memset(b,0,sizeof(b));
    for(int i=0;i<n;i++){    /*将要排序的数作为下标，统计每个数出现的次数*/
         b[a[i]]++;
         if(size<a[i])
             size=a[i];
     }
     for(int i=0;i<=size;i++){      /*按数字大小输出出现的数*/
         if(b[i])
             for(int j=0;j<b[i];j++)
                  cout<<i<<" ";
      }
      cout<<endl;
}

/*快速排序*/
void quicksort(int a[],int left,int right){
    if(left<right){                         
        int key=a[left];
        int low=left;
        int high=right;
         while(low<high){   /*所有的数都比较一遍，即i==j结束*/ 
               /*从后往前找找到第一个比key小的数，与low交换*/
               while(low<high&&a[high]>key)     
                     high--;
               a[low]=a[high];
               /*从前往后找找到第一个比key大的数与high交换*/ 
               while(low<high&&a[low]<key)                 
                   low++;
               a[high]=a[low];
          }
           a[low]=key;      /*一次比较确定一个数的位置*/
           quicksort(a,left,low-1);     /*左边的数递归排序*/ 
           quicksort(a,low+1,right);     /*右边的数递归排序*/
     }
}
void qp(){   /*输出*/ 
    quicksort(a,0,n-1);
    for(int i=0;i<n;i++)  cout<<a[i]<<" ";
    cout<<endl;
}

/*归并排序*/ 
void merge(int a[],int b[],int s,int u,int v) {     /*将数组有序的两个部分合并成有序的一个*/ 
    int i=s,j=u+1,q=s;  
    while(i<=u&&j<=v) {    /*两个部分进行比较，小的数放到b数组里*/
         if(a[i]<=a[j])     b[q++]=a[i++];         
         else      b[q++]=a[j++];  
     }    
     while(i<=u)                  /*将剩余元素放到b*/ 
          b[q++]=a[i++];  
     while(j<=v)         
          b[q++]=a[j++];  
}  
void mergepass(int a[],int b[],int n,int t)  { 
    int i=0,j;  
    /*将相邻的两个长度为t的各自有序的子序列合并成一个长度为2t的子序列*/
    while(n-i>=2*t )  {                                
         merge(a,b,i,i+t-1,i+2*t-1);  
         i=i+2*t;  
    }    
    if(n-i>t)      /*若剩下的元素个数大于一个子序列的长度继续排序*/ 
        merge(a,b,i,i+t-1,n-1);  
    else  {       /*若剩下的元素个数小于子序列长度直接将剩下的数赋值*/ 
         for(j=i;j<n;++j )   b[j]=a[j];  
    }
}  
void mergesort(int a[],int n)  {  
    int t=1;  
    int *b=(int *)malloc(sizeof(int) *n); 
    while(t<n)  {           /*排序个数逐渐增大*/
         mergepass(a,b,n,t);  
         t*=2;  
         mergepass(b,a,n,t);  
         t*=2;  
     }  
free(b); 
}  
void mp(){
     mergesort(a,n);
     for(int i=0;i<n;i++)  cout<<a[i]<<" ";
     cout<<endl;
} 

/*堆排序*/
void heapadjust(int a[],int i,int n){            
    int lchild=2*i;
    int rchild=2*i+1;
    int maxn=i;
    if(i<=n/2){   /*将叶节点和跟节点进行比较，最大的成为跟节点*/
        if(lchild<=n&&a[lchild]>a[maxn])  maxn=lchild;
        if(rchild<=n&&a[rchild]>a[maxn])  maxn=rchild;
         int tmp;
         if(maxn!=i){
             tmp=a[i];
             a[i]=a[maxn];
             a[maxn]=tmp;
             heapadjust(a,maxn,n);
         }
    }
} 
void buildheap(int a[],int n){             /*建堆*/
    for(int i=n/2;i>0;i--)  heapadjust(a,i,n);
} 
void heapsort(int a[],int n){
    buildheap(a,n);
    int tmp;
    int i;
    for(i=n;i>0;i--){
         tmp=a[1];
         a[1]=a[i];
         a[i]=tmp;
         heapadjust(a,1,i-1);
    }
}
void hp(){
    heapsort(a,n);
    for(int i=1;i<=n;i++)  cout<<a[i]<<" ";
    cout<<endl;
}
int main(){
    while(cin>>n){
         for(int i=0;i<n;i++)   cin>>a[i];
         bubblesort(a,n);
         selectionsort(a,n);
         insrtsort(a,n);
         countsort(a,n);
         qp();
         mp();
         for(int i=n;i>0;i--)    /*为了方便，将所有数的下标加一*/
             a[i]=a[i-1];
         hp();
     }
     return 0;
}