排序是一种很基本的算法，由于代码量不是很大，逻辑较清晰，因此排序算法在笔试中占有很重要的位置。排序算法有很多种大致分为插入排序，选择排序，交换排序，归并排序四种。插入排序分为直接插入排序和希尔排序。
直接插入排序的思想是：在要排序的一组数中，假设前面（n-1）（n>2）个数是有序的，现在要把第n个数插入到前面的有序数列中，使这n个数也是排好序的，如此反复循环。
代码如下：
void Sort(int *a, size_t size)
{
assert(a);
for (int index = 1; index < size; ++index) //认为第一个数是有序的，不用排
{
int tmp = a[index]; //哨兵位，tmp之前的序列都有序
int pos = index - 1; //待排序的数
while (pos >= 0 && a[pos] > tmp) //排序
{
a[pos + 1] = a[pos];
pos--;
}
a[pos + 1] = tmp;
}
}
希尔排序思想：排序时先将待排序的序列按照某个增量gap分成若干组，对这个组进行直接插入排序。然后减小增量gap的大小，对新的组进行插入排序，当增量gap等于1时排序完成。希尔排序的代码跟直接插入排序的代码很像。
代码如下：
void ShellSort(int *a, size_t size)
{
assert(a);
int gap = size;
while (gap > 1)
{
gap = gap / 3 + 1;
for (int index = gap; index <size; ++index)
{
int tmp = a[index];
int pos = index - gap;
while (pos >= 0 && a[pos] > tmp)
{
a[pos + gap] = a[pos];
pos -= gap;
}
a[pos + gap] = tmp;
}
}
}
void main() //测试
{
int a[] = { 2, 9, 4, 5, 3, 6,8,7,1,0 };
// ShellSort(a, sizeof(a) / sizeof(a[0]));
Sort(a, sizeof(a) / sizeof(a[0]));
for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
{
cout << a[i] << " ";
}
cout << endl;
}