常用的排序方法（代碼總結）

1冒泡排序法

時間複雜度O（N^2）

#include<stdio.h>
const int maxn=0xffffff; 
int a[maxn];
void Sort1(int *a,int n)
{
  for(int i=1;i<n;i++)
  {
    for(int j=0;j<n-i;j++)
    {
      if(a[j]>a[j+1])
      {
        int k=a[j+1];
        a[j+1]=a[j];
        a[j]=k;
      }
    }
  }
}
void Sort2(int *a,int n)
{
  for(int i=0;i<n;i++)
  {
    for(int j=i;j<n;j++)
    {
      if(a[i]>a[j])
      {
        int k=a[j];
        a[j]=a[i];
        a[i]=k;
      }
    }
  }
}
int main()
{
  int n;
  scanf("%d",&n);
  for(int i=0;i<n;i++)
  scanf("%d",&a[i]);
  Sort1(a,n);
  //Sort2(a,n);兩種實作方式原理都是冒泡排序 
  printf("%d",a[0]);
  for(int i=1;i<n;i++)
  printf(" %d",a[i]);
}      

2插入排序

時間複雜度O（N^2）

#include<stdio.h>
const int maxn=0xffffff;
int a[maxn];
void InsertionSort(int *a,int n)
{
  for(int i=1;i<n;i++)
  {
    int j=i-1;
    int key=a[i];
    while(a[j]>key&&j>=0)
    {
      a[j+1]=a[j];
      j--;
    }
    a[j+1]=key;
  }
}
int main()
{
  int n;
  scanf("%d",&n);
  for(int i=0;i<n;i++)
  scanf("%d",&a[i]);
  InsertionSort(a,n);
  printf("%d",a[0]);
  for(int i=1;i<n;i++)
  printf(" %d",a[i]);  
}      

3.歸并排序

時間複雜度（N*logN）

參考：​​白話經典算法系列5​​

#include<stdio.h>
const int maxn=0xfffff;
int a[maxn];
int tmp[maxn];
void Mergearray(int first,int mid,int last)
{
  int i=first,j=mid+1;
  int k=0;
  while(i<=mid&&j<=last)
  {
    if(a[i]<=a[j])
       tmp[k++]=a[i++];
    else
       tmp[k++]=a[j++];
  }
  while(i<=mid)
      tmp[k++]=a[i++];
  while(j<=last)
      tmp[k++]=a[j++];
  //for(int i=0;i<k;i++)
     // a[first+i]=tmp[i];
}
void Mergesort(int first,int last)
{
  if(first<last)
  {
    int mid=(first+last)/2;
    Mergesort(first,mid);
    Mergesort(mid+1,last);
    Mergearray(first,mid,last);
  }
}
int main()
{
  int n;
  scanf("%d",&n);
  for(int i=0;i<n;i++)
      scanf("%d",&a[i]);
  Mergesort(0,n-1);
  for(int i=0;i<n;i++)
  {
    printf("%d",tmp[i]);
    if(i!=n-1)
    printf(" ");
  }
}      

上述代碼利用分治法+遞歸思想實作歸并排序的簡化代碼（可運作），但是建立了新的數組，占用了不必要的空間。

#include<stdio.h>
const int maxn=0xfffff;
int a[maxn];
void Mergearray(int first,int mid,int last,int tmp[])
{
  int i=first,j=mid+1;
  int k=0;
  while(i<=mid&&j<=last)
  {
    if(a[i]<=a[j])
       tmp[k++]=a[i++];
    else
       tmp[k++]=a[j++];
  }
  while(i<=mid)
      tmp[k++]=a[i++];
  while(j<=last)
      tmp[k++]=a[j++];
  for(int i=0;i<k;i++)
     a[first+i]=tmp[i];
}
void Mergesort(int first,int last,int tmp[])
{
  if(first<last)
  {
    int mid=(first+last)/2;
    Mergesort(first,mid,tmp);
    Mergesort(mid+1,last,tmp);
    Mergearray(first,mid,last,tmp);
  }
}
int main()
{
  int n;
  scanf("%d",&n);
  for(int i=0;i<n;i++)
      scanf("%d",&a[i]);
  int *p=new int[n];
  if(p!=NULL)
  { 
      Mergesort(0,n-1,p);
      delete [] p;
    for(int i=0;i<n;i++)
      {
        printf("%d",a[i]);
      if(i!=n-1)
        printf(" ");
    }
  }
}