1.直接插入排序
直接插入排序的思想很简单，就是从排序序列开始，依次将每个元素插入到前面已经排序好的序列中，最终使整个序列有序，直接插入排序的时间复杂度O(n^2)，空间复杂度为O(1)，代码如下：
[cpp]
/**
* Time Complexity:O(n^2)
* Space Complexity:O(1)
*
* sorted data ; array[low...high]
*/
template
void DirectInsertSort(Type array[], int low, int high)
{
if (array == NULL || low >= high || low < 0)
{
return;
}
Type exchange;
int j;
for (int i = low + 1; i <= high; ++i)
{
exchange = array[i];
for (j = i - 1; j >= low; --j)
{
if (exchange < array[j])
{
array[j + 1] = array[j];
}
else
{
break;
}
}
array[j + 1] = exchange;
}
}
2.冒泡排序
我们对冒泡排序应该都比较深，因为这个名字很形象很好记 。排序的思想就是每个冒泡一遍序列，找出一个最大或最小的元素，放到它排序后的位置上直到序列有序。时间复杂度O(n^2)，空间复杂度为O(1)，代码如下：
[cpp]
/**
* Time Complexity:O(n^2)
* Space Complexity:O(1)
*
* sorted data: array[low...high]
*/
template
void BubbleSort(Type array[], int low, int high)
{
if (array == NULL || low >= high || low < 0)
{
return;
}
Type exchange;
bool change = false;
for (int i = low; i < high; ++i)
{
for (int j = low; j < high - i + low; ++j)
{
if (array[j] > array[j + 1])
{
exchange = array[j + 1];
array[j + 1] = array[j];
array[j] = exchange;
change = true;
}
}
if (!change)
{//如果冒泡过程中没有发生交换，则视序列已经排好序，减少无谓的比较
return;
}
change = false;
}
}
3.简单选择排序
简单选择排序的思想就是每次在未排序的序列中选取一个最小（或最大）的元素，放到最终的位置上，时间复杂度O(n^2)，空间复杂度为O(1)，代码如下：
[cpp]
/**
* Time Complexity:O(n^2)
* Space Complexity:O(1)
*
* sorted data ; array[low...high]
*/
template
void SelectSort(Type array[], int low, int high)
{
if (array == NULL || low >= high || low < 0)
{
return;
}
int index;
Type exchange;
for (int i = low; i < high; ++i)
{
index = i;
for (int j = i + 1; j <= high; ++j)
{
if (array[j] < array[index])
{
index = j;
}
}
exchange = array[i];
array[i] = array[index];
array[index] = exchange;
}
}
4.折半插入排序
折半插入排序和直接插入排序的差别就是在查找插入位置的方式上，直接插入排序是顺序查找插入位置，折半插入式通过二分搜索的思想来查找插入位置。总体来说直接插入排序的比较次数为1+2+3...+(n-1) ~ O(n^2)，二折半查找的比较次数在lg(n-1)+lg(n-2)+...1~O(lg(n!)) ~O(nlgn)（stirling公式）。所以折半查找的优势是减少了比较次数。代码如下：
[cpp]
/**
* Time Complexity:O(n^2)
* Space Complexity:O(1)
* sorted data ; array[low...high]
*/
template
void BinaryInsertSort(Type array[], int low, int high)
{
if (array == NULL || low >= high || low < 0)
{
return;
}
int left, right, mid, j;
Type exchange;
for (int i = low + 1; i <= high; ++i)
{
left = low;
right = i - 1;
while (left <= right)
{
mid = (left + right) / 2;
if (array[i] < array[mid])