算法----插入排序（insert sort）

插入排序就是每次選取一個元素插入到已經排序的子數組中，如此循環，直到所有的元素都完成排序。

算法實現：

void sort::insert_sort(int* a, const int n)
{
 for(int i=1; i<n; i++)
 {
  for(int j=i; j>0 && a[j] < a[j-1]; j--)
  {
   swap(a,j,j-1);
  }
 }
}

上述算法的時間復雜度為O(N^2)。但是插入排序的算法性能與待排序的數組有關，當數組已排序，則可在線性時間內完成，如果數組為逆序，則需要O(N^2)的時間才能完成排序。因此插入排序算法的時間復雜度在N~N^2之間。當數組規模較小或者存在多個局部有序的子數組時，算法的執行速度會更快。

歸並排序的實現 http://www.linuxidc.com/Linux/2014-09/107316.htm

直接插入排序的三種實現 http://www.linuxidc.com/Linux/2014-09/107313.htm

直接選擇排序及交換二個數據的正確實現 http://www.linuxidc.com/Linux/2014-09/107315.htm

排序總結之選擇式排序  http://www.linuxidc.com/Linux/2014-09/106564.htm