C/C++ 插入排序(Insertion Sort)

插入排序：將已知序列分別依照數值大小去排序
例子：玩撲克牌會將手上排依照號碼大小分別插入相對的位址


輸入：n個數字的序列
輸出：排列好得序列

最差時間複雜度 O(n^2)
最優時間複雜度 O(n)
平均時間複雜度 O(n^2)
最差空間複雜度  O(n) ，需要輔助空間O(1)



虛擬碼：

INSERTION-SOFT(A)

for i ← 2 to length[A]
 do key ← A[i]

 j = i -1

 while j >0 and A[j] > key
  do A[j+1] ← A[j]
  j ← j-1

 A[j+1] ← key

程式碼：

#include <iostream>

using namespace std;


void soft(int m_array [], int length){
 cout << "排序前:";
 for(int i=0; i<length; i++){
  if(i == (length-1)){
   cout << m_array[i] << endl; 
  }else{
   cout << m_array[i] << ", ";
  }
 }

 for(int i=1; i<length; i++){
  int temp = m_array[i];
  int j = i-1;

  while(j>=0 && m_array[j]>temp){
   m_array[j+1] = m_array[j];
   j--;
  }
  m_array[j+1] = temp;
 }

 cout << "排序後:";
 for(int i=0; i<length; i++){
  if(i == (length-1)){
   cout << m_array[i] << endl; 
  }else{
   cout << m_array[i] << ", ";
  }
 }
}



int main(){

 int A[] = {8,11,99,1,4,558,41,71,81,99,5};
 int length = sizeof(A)/sizeof(int);
 soft(A, length);

 system("pause");
 return 1;
}

參考資料：
http://zh.wikipedia.org/wiki/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F