常见的排序方式有6种：
---简单排序里面的有：插入排序、选择排序、冒泡排序，时间复杂度为O(n^2)
---线性对数阶的排序: 归并排序(merge sort),快速排序，堆排序，时间复杂度为O(nlogn)
在n<=50的情况下，最好使用插入排序或者选择排序，由于选择排序移动次数比插入排序少，在数据量比较多的情况，推荐使用选择排序。
如果序列基本上正序了，则使用插入排序、冒泡排序或者随机的快速排序
在n非常大的情况下，使用O(nlogn)的算法，即归并排序、快速排序、堆排序。后2者是不稳定的排序，而merge排序是稳定的排序方式，快速排序是基于比较的排序中的最好的排序方法。
实验条件下算法运行时间：（单位毫秒，10万随机数）
冒泡排序: 56953
选择排序: 20109
插入排序: 14547
归并排序: 134
堆排序: 67
快速排序: 28
三种O(nlogn)的排序时间比较为：
排序算法 10万 100万 1000万
归并排序 134 1309 13985
堆排序 67 865 14292
快速排序 28 513 9815
下面给出insertion sort的原理和实现
insertion sort是稳定排序，在数据量非常小的情况下，非常快速。其原理就如同打牌的时候按顺序插入牌一样(来自introdution to algorithm)，从后面往前面找大于最新的牌的数，然后往后面替换，再将最新的牌插入进去完成了前面的牌是已经排序好的。核心算法如下：
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;
}
具体实现为:
#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;
}