简单排序

• 快速排序

#include<bits/stdc++.h>
using namespace std;
int a[100];
void swap1(int a[],int i,int j)
{
    int t=a[i];
     a[i]=a[j];
    a[j]=t;
}
int pro(int a[ ],int p,int r)
{
    int i=p;
    int j=r+1;
    int x=a[p];
    while(1)
     {
           while(i<r&&a[++i]<x);
           while(a[--j]>x);
           if(i>=j)
           {
                 break;
          }
           swap1(a,i,j);
    }
     swap1(a,p,j);
     return j;
}
void quicksort(int a[ ],int p,int r)
{
    if(p<r)
     {
           int q=pro(a,p,r);
           quicksort(a,p,q-1);
           quicksort(a,q+1,r);
     }
}
int main( )
{
     int n;
     cout<<"输入数的个数:"<<endl;
     cin>>n;
     cout<<"输入数:"<<endl;
     for(int i=0;i<n;i++)
    {
           cin>>a[i];
     }
     quicksort(a,0,n-1);
     cout<<"输出排序后的数组:"<<endl;
     for(int i=0;i<n;i++)
    {
           cout<<a[i]<<" ";
    }
     cout<<endl;
     return 0;
}

• 详情请看 快速排序

• 插序排序

#include<bits/stdc++.h>
using namespace std;
int a[100];
int main( )
{
     int n;
    cout<<"输入数的个数:"<<endl;
    cin>>n;
    cout<<"输入数:"<<endl;
    for(int i=0;i<n;i++)
    {
           cin>>a[i];
    }
     for(int i=0;i<n;i++)
     {
           int tmp=a[i];
           int j=i-1;
           while(j>=0&&a[j]>tmp)
           {
                 a[j+1]=a[j];
                 j--;
           }
           a[j+1]=tmp;
     }
     cout<<"输出排序后的数组:"<<endl;
     for(int i=0;i<n;i++)
     {
           cout<<a[i]<<" ";
     }
     cout<<endl;
    return 0;
}

• 冒泡排序

#include<bits/stdc++.h>
using namespace std;
int a[100];
int main( )
{
      int n;
      cout<<"输入数的个数:"<<endl;
      cin>>n;
      cout<<"输入数:"<<endl;
      for(int i=0;i<n;i++)
      {
            cin>>a[i];
      }
      for(int i=0;i<n-1;i++)
      {
           for(int j=0;j<n-i-1;j++)
           {
                 if(a[j]>a[j+1])
                 {
                       int t=a[j+1];
                       a[j+1]=a[j];
                       a[j]=t;
                 }
           }
      }
      cout<<"输出排序后的数组:"<<endl;
      for(int i=0;i<n;i++)
      {
            cout<<a[i]<<" ";
      }
      cout<<endl;
      return 0;
}

• 希尔排序

#include<bits/stdc++.h>
using namespace std;
int a[100];
int main( )
{
      int n;
      cin>>n;
      int t=n;
      for(int i=0;i<n;i++)
      {
            cin>>a[i];
      }
      while(t)
      {
            t/=2;
            for(int i=0;i<t;i++)
            {
                  for(int j=i+t;j<n;j=j+t)
                  {
                        if(a[j]<a[j-t])
                        {
                              int k=j-t;
                              int tep=a[j];
                              while(a[k]>tep&&k>=0)
                              {
                                    a[k+t]=a[k];
                                    k-=t;
                              }
                               a[k+t]=tep;
                        }

                  }
            }
      }
      for(int i=0;i<n;i++)
      {
            cout<<a[i]<<" ";
      }
      cout<<endl;
      return 0;
}

• 选择排序

#include<bits/stdc++.h>
using namespace std;
int a[100];
int main( )
{
      int n;
      cin>>n;
      for(int i=0;i<n;i++)
      {
            cin>>a[i];
      }
      for(int i=0;i<n;i++)
      {
            int minx=i;
            for(int j=i+1;j<n;j++)
            {
                  if(a[j]<a[minx])
                  {
                        minx=j;
                  }
            }
            int t=a[i];
            a[i]=a[minx];
            a[minx]=t;
      }
      for(int i=0;i<n;i++)
      {
            cout<<a[i]<<" ";
      }
      cout<<endl;
      return 0;
}

• 归并排序

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
#define MAX 55000
using namespace std;
ll n;
const int mod=1e9+7;
int a[MAX];
int L[MAX],R[MAX];
void mersort(int a[ ],int n,int left,int mid,int right )
{
      int i,j,k;
      int n1=mid-left;
      int n2=right-mid;
      for(i=0;i<n1;i++) L[i]=a[left+i];
      for(i=0;i<n2;i++) R[i]=a[mid+i];
      L[n1]=mod,R[n2]=mod;
      i=j=0;
      for(k=left;k<right;k++)
      {
            if(L[i]<=R[j])
            {
                  a[k]=L[i++];
            }
            else
            {
                  a[k]=R[j++];
            }
      }

}
void mergasort(int a[ ],int n,int left,int right)
{
      int mid;
      ll v1,v2,v3;
      if(left+1<right)
      {
            mid=(left+right)/2;
            mergasort(a,n,left,mid);
            mergasort(a,n,mid,right);
            mersort(a,n,left,mid,right);
      }
}
int main( )
{
     cin>>n;
     for(int i=0;i<n;i++)
     {
           cin>>a[i];
     }
     mergasort(a,n,0,n);
     for(int i=0;i<n;i++)
     {
           if(i)
           {
                 cout<<" ";
           }
           cout<<a[i];
     }
     cout<<endl;
     return 0;
}

• 详情请看 归并排序与逆序列