Insertion Sort

平均時間複雜度是 O(n^2)
其它還有一些變形
insert的部份改用二元搜尋(加快insert速度)
以及使用linked list而不是用陣列(減少memory copy的overhead)

這種演算法沒用嗎? Quick Sort都比這個快
但當做學生作業似乎還不錯啊

#include 
using std::cout;
#define MININT 0 // any key must grater than this

class Element
{
public:
 Element(){}
 int getKey() const{ return key; }
 void setKey(int k) { key = k; }
private:
 int key;
};

void insert(const Element e, Element *lst, int i)
// insert lst[0] -- lst[i]
// lst must have i+2 capacity, cause we inset a new element to ordered list
// assume lst[0].getKey()  = MININT, make sure all keys are grater than this
{
 while( e.getKey() < lst[i].getKey() ) {
  lst[i+1] = lst[i];
  --i;
 }
 lst[i+1] = e;
}

void InsertionSort(Element* lst, const int n)
// sort lst[1] to lst[n]
{
 lst[0].setKey(MININT);
 for(int j = 2; j <=n; ++j)
  insert(lst[j], lst, j-1);
}

int main()
{
 Element *lst = new Element[6];
 lst[1].setKey(2);
 lst[2].setKey(3);
 lst[3].setKey(4);
 lst[4].setKey(5);
 lst[5].setKey(1);
 InsertionSort(lst, 5);
 for(int i =1 ; i < 6; ++i)
  cout << lst[i].getKey() << " ";

 return 0;
}