排序算法是计算机科学中最常见的一类算法，也是程序员在求职面试时最经常会被问到的。所以本文中，将会对几种常见的排序算法进行简单的介绍和分析。
插入排序（Insertion Sort）由 N-1 趟排序组成。对于 p = 1 趟到 p = N-1 趟，插入排序保证从位置 0 到位置 p 上的元素为已排序状态。下面的程序中，位置 p 上的元素存于 tmp，而在位置 p 之前所有更大的元素都被向右移动一个位置，最后 tmp 被正确放在的位置上。
下面的 C 代码是参考《编程珠玑》而对交换操作进行优化过的：
void insertion_sort (int d[], int N)
{
int j, p;
int tmp;
for (p = 1; p < N; p++)
{
tmp = d[p];
for (j = p; j > 0 && tmp < d[j-1]; j--)
d[j] = d[j-1];
d[j] = tmp;
}
}
冒泡排序的基本思路是：对待排元素进行 N 趟操作，在每一趟中使一个最大的元素冒至数组的尾端。下面是冒泡排序最原始的一个代码：
void bubble_sort (int d[], int N)
{
int i, j;
int tmp;
for (i = 0; i < N; i++)
for (j = 0; j < N - i; j++)
if (d[j] > d[j+1])
{
tmp = d[j]; d[j] = d[j+1]; d[j+1] = tmp;
}
}
可以看出，无论对于什么样的数组（甚至是本来就是按序排列的），上面的程序仍旧需要将每趟进行到底。所以下面的代码中使用了标志变量 FLAG 记录每趟中最后发生交换的位置，来避免多余的遍历和比较。
void bubble_sort (int d[], int N)
{
int i, bound, FLAG = N;
int tmp;
while (FLAG > 0)
{
bound = FLAG;
FLAG = 0;
for (i = 1; i < bound; i++)
if (d[i-1] > d[i])
{
tmp = d[i-1]; d[i-1] = d[i]; d[i] = tmp;
FLAG = i;
}
}
}
希尔排序（Shell Sort）又叫缩小增量排序，它通过比较相距一定间隔的元素来工作，各趟比较所用的距离随着算法的进行而较小，知道之比较相邻元素的最后一趟排序为止。希尔排序是冲破二次时间屏障的第一批算法之一。
void shell_sort (int d[], int N)
{
int i, j, increment;
for (increment = N / 2; increment > 0; increment =/ 2)
for (i = increment; i < N; i++)
{
tmp = d[i];
for (j = i; j >= increment; j -= increment)
if (tmp < d[j-increment])
d[j] = d[j-increment];;
else
break;
d[j] = tmp;
}
}
快速排序是一种分治的递归算法，它也是最快的已知排序算法。算法主要由下列步骤组成：
下面的代码是使用双向划分的快速排序，思路同样参考自《编程珠玑》：
void quick_sort (int data[], int left, int right)
{
if (left >= right)
return;
int pivot = data[left];
int i = left, j = right + 1;
int temp;
while (1)
{
do i++; while (i <= right && data[i] < pivot);
do j--; while (data[j] > pivot);
if (i > j)
break;
temp = data[i]; data[i] = data[j]; data[j] = temp;
}
temp = data[left]; data[left] = data[j]; data[j] = temp;
quick_sort(data, left, j - 1);
quick_sort(data, j + 1, right);
}
在递归的过程中，快速排序对于很小的子数组将花费大量的时间进行运算。这个时候可以使用插入排序之类的简单方法来排序这些很小的数组，程序的速度会更快。将上面快速排序代码中的第一个 if 语句改为
if (right - left < cutoff)
return;
其中 cutoff 是一个小整数。程序结束时，数组并不是有序的，而是被组合成一块一块随机排列的值，并且满足这样的条件：某一块中的元素小于它右边任何块中的元素。我们需要通过另一种排序算法对块的内部进行排序：
quick_sort(data, 0, n);
insertion_sort(data, n);