##直接插入排序：
有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法-插入排序法。
算法描述：

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到下一位置中
6. 重复步骤2-5

代码实现：
void insertion_sort(int a[],int n)
{
int i,j;
int temp;
for(i=1;i=0&&a[j]>temp)
{
a[j+1]=a[j];
j–;
}
if(j!=i-1)
{
a[j+1]=temp;
}
}
}

##希尔排序：
希尔排序是插入排序的一种，直接插入排序是增量为1的希尔排序，所以代码只要把增量改一下就可以了。
代码实现：

#include <iostream>
using namespace std;               
void shell_sort(int a[],int n)
{
  int d,i,j,temp;
  for(d=n/2;d>=1;d=d/2)
  {
    for(i=d;i<n;i++)
    {
      temp=a[i];
      for(j=i-d;j>0&&a[j]>temp;i=j-d)
      {
        a[j+d]=a[j];
      }
      a[j+d]=temp;
    }
  }
}

##冒泡排序
算法描述：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
   代码实现：
   void bubble_sort(int a[],int n)
   {
   int i,j,temp;
   for(j=0;j<n-1;j++)
   {

   for(i=0;i<n-1-j;i++)
   {
     if(a[i]>a[i+1])
     {
       temp=a[i];
       a[i]=a[j];
       a[j]=temp;
     }
   }
   

   }
   }

##快速排序
快速排序（Quicksort）是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
算法介绍：
设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。
一趟快速排序的算法是：
1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索(j–)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；
5）重复第3、4步，直到i=j；
代码实现：

#include <iostream>
using namespace std;   
void quick_sort(int a[].int low,int high)  //low,high为数组中首元素与尾元素的下标
{
  if(low>=high)
  {
    return;
  }
  int first=low;
  int last=high;
  int key=a[first];
  while(first<last)
  {
    while(first<last&&a[last]>=key)
    {
      last--;
    }
    a[first]=a[last];
    while(first<last&&a[first]<=key)
    {
      first++;
    }
    a[last]=a[first];
  }
  a[first]=key;
  quick_sort(a,low.first-1);
  quick_sort(a,last+1,high);
}

##选择排序
算法描述：
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
对于数组a[n]来说，第一趟排序是从a[1]…a[n]中选出最小的元素与a[1]交换，第二趟排序是从a[2]…a[n]中选出最小的元素与a[2]交换，依次类推
代码实现：

#include <iostream>
using namespace std;       
void select_sort(int *a,int n)
{
  int i,j,min,t;
  for(i=0;i<n-1;i++)
  {
    min=i;
    for(j=i+1;j<n;j++)
    {
      if(a[min]>a[j])
      {
        min=j;
      }
    }
    if(min!=i)
    {
      t=a[min];
      a[min]=a[i];
      a[i]=t;
    }
  }
}

##归并排序
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个有序的子序列，再把有序的子序列合并为整体有序序列。
以二路归并为例，介绍一下归并过程：
比较a[i]和a[j]的大小，若a[i]≤a[j]则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加1，如此循环下去直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。
对于一个无序数组a[]，使用归并排序，代码如下：

#include <iostream>
using namespace std;
void merge(int r[],int r1[],int s,int m,int t)
{
  int i=s;
  int j=m+1;
  int k=s;
  while(i<=m&&j<=t)
  {
    if(r[i]<=r[j])
    {
      r1[k++]=r[i++]
    }
    else
    {
      r1[k++]=r[j++];
    }
  }
  if(i<=m)
  {
    while(i<=m)
    {
      r1[k++]=r[i++]
    }
  }
  else
  {
    while(j<=t)
    {
      r1[k++]=r[j++]
    }
  }
  for(int n=s;n<=t;n++)
  {
    r[n]=r1[n]
  }
} 
void merge_sort(int r[],int r1[].int s,int t)
{
  if(s<t)
  {
    int m=(s+t)/2;
    merge_sort(r,r1,s,m);
    merge_sort(r,r1,m+1,t);
    merge(r,r1,s,m,t);
  }
}
int main()
{
  int r[8]={10,3,5,1,9,34,54,456};
  int r1[8];
  merge_sort(r,r1.0,7);
  for(int q=0;q<8;q++)
  {
    cout<<" "<<r[q];
  }
  return 0;
}

##总结
直接插入排序： 平均时间复杂度o(n^2),最坏情况o(n^2),空间复杂度o(1),稳定
冒泡排序： 平均时间复杂度o(n^2),最坏情况o(n^2),空间复杂度o(1),稳定
简单选择排序： 平均时间复杂度o(n^2),最坏情况o(n^2),空间复杂度o(1),不稳定
快速排序： 平均时间复杂度o(nlog2n),最坏情况o(n^2),空间复杂度o(log2n),不稳定
堆排序： 平均时间复杂度o(nlog2n),最坏情况o(nlog2n),空间复杂度o(1),不稳定
归并排序： 平均时间复杂度o(nlog2n),最坏情况o(nlog2n),空间复杂度o(n),稳定