插入排序(Insertion Sort)：

　　插入排序(Insertion Sort)也是一种平均O(n^2)的排序算法。“它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序(即只需用到O(1)的额外空间的排序)，因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。”维基的这幅图很直观的解释了插入排序：

　　算法步骤为：

　　1、从有序数列 { a[0] } 和无序数列 { a ,a ,a ，…，a[n-1] }开始进行排序;

　　2、处理第i个元素时(i=1,2,3,…,n-1)，数列 { a[0],a ,a ，…，a[i-1] }是已有序的，而数列{ a[i],a[i+1]，…，a[n-1] }是无序的。用a[i]与a[i-1]，a[ i-2]，…，a[0]进行比较，找出合适的位置将a[i]插入;

　　3、重复第二步，共进行n-i次插入处理，数列全部有序。

　　复杂度：

　　最差时间复杂度：O(n^2)

　　最优时间复杂度：O(n^2)

　　平均时间复杂度：O(n^2)

　　稳定性：稳定

　　实现：

　　[cpp]

　　void insertSort(int arr[], int n)

　　{

　　for (int i = 1; i < n; i++)

　　if (arr[i] < arr[i - 1])

　　{

　　int j,t = arr[i];

　　for (j = i - 1; j >= 0 && arr[j] > t; j--)

　　arr[j + 1] = arr[j];

　　arr[j + 1] = t;

　　}

　　}

　　选择排序(Selection Sort)：

　　基本思想为：“首先在未排序序列中找到最小(大)元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小(大)元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。”类似于冒泡，也很容易理解，但它的交换次数明显比冒泡少得多，n比较小的时候，选择排序明显比冒泡快。

　　复杂度：

　　最差时间复杂度：O(n^2)

　　最优时间复杂度：O(n^2)

　　平均时间复杂度：O(n^2)

　　稳定性：不稳定

　　为什么是不稳定呢 看一个例子：对 4 5 6 4 2 3 进行选择排序。

　　开始时，我们找到最小元素 2 并把它和第一个元素 4 交换，这时 序列变成 2 5 6 4 4 2 3，好像没有问题是吗 但是，现在，两个 4 的位置和原来的位置相比已经改变了!所以说选择排序时不稳定的。这点要注意，因为也许有时候会在你毫无察觉的情况下导致一些问题。

　　实现：

　　[cpp]

　　void selectionSort(int arr[], int n)

　　{

　　for (int i = 0; i < n; i++)

　　{

　　int index = i;

　　//找出最小元素的索引

　　for(int j = i+1;j < n;++j)

　　{

　　if(arr[index] > arr[j])

　　index = j;

　　}

　　//把找到的最小元素和 arr[i] 交换

　　if(index != i)

　　{

　　int t = arr[index];

　　arr[index] = arr[i];

　　arr[i] = t;

　　}

　　}

　　}