常見的排序方式有6種：
---簡(jiǎn)單排序里面的有：插入排序、選擇排序、冒泡排序，時(shí)間復(fù)雜度為O(n^2)
---線性對(duì)數(shù)階的排序: 歸并排序(merge sort),快速排序，堆排序，時(shí)間復(fù)雜度為O(nlogn)
在n<=50的情況下，最好使用插入排序或者選擇排序，由于選擇排序移動(dòng)次數(shù)比插入排序少，在數(shù)據(jù)量比較多的情況，推薦使用選擇排序。
如果序列基本上正序了，則使用插入排序、冒泡排序或者隨機(jī)的快速排序
在n非常大的情況下，使用O(nlogn)的算法，即歸并排序、快速排序、堆排序。后2者是不穩(wěn)定的排序，而merge排序是穩(wěn)定的排序方式，快速排序是基于比較的排序中的最好的排序方法。
實(shí)驗(yàn)條件下算法運(yùn)行時(shí)間：（單位毫秒，10萬隨機(jī)數(shù)）
冒泡排序: 56953
選擇排序: 20109
插入排序: 14547
歸并排序: 134
堆排序: 67
快速排序: 28
三種O(nlogn)的排序時(shí)間比較為：
排序算法 10萬 100萬 1000萬
歸并排序 134 1309 13985
堆排序 67 865 14292
快速排序 28 513 9815
下面給出insertion sort的原理和實(shí)現(xiàn)
insertion sort是穩(wěn)定排序，在數(shù)據(jù)量非常小的情況下，非常快速。其原理就如同打牌的時(shí)候按順序插入牌一樣(來自introdution to algorithm)，從后面往前面找大于最新的牌的數(shù)，然后往后面替換，再將最新的牌插入進(jìn)去完成了前面的牌是已經(jīng)排序好的。核心算法如下：
for(int i=1;i<size;i++)
{
//get the new card
int temp = arr[i];
int j=i-1;
while((j>=0)&&(arr[j]>temp))//find the old card bigger than the new card
{
arr[j+1]=arr[j];
j--;
}
//get the position of the new card
arr[j+1]=temp;
}
具體實(shí)現(xiàn)為:
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;
int main(int argc,char* argv[])
{
int arr[]={5,6,1,2,7,3,8,10,4,9};
int size = sizeof(arr)/sizeof(arr[0]);
copy(arr,arr+size,ostream_iterator<int>(cout," "));
cout<<endl;
for(int i=1;i<size;i++)
{
int temp = arr[i];
int j=i-1;
while((arr[j]>temp)&&(j>=0))
{
arr[j+1]=arr[j];
j--;
}
arr[j+1]=temp;
}
copy(arr,arr+size,ostream_iterator<int>(cout," "));
cout<<endl;
system("pause");
return 0;
}