简介：
有许多的关于数据计算的应用程序中都用到算法。甚至在我们开始运算数据之前，算法的重要性就浮在我们眼前了。比如，我们在查找照片上的人时，必须按从高到低的顺序。我们必须给业绩最好的员工最好的奖金，这就要求我们必须从高到低，或从大到小的顺序排列事物。
比如，我们查询数据库时，排序时，要加上Order By语句。我们寻找手机上的某本书时，必须从已经排好序的队列中找。如果你想高效的用二分查找法从数组中查找某个元素，你可能得排序好整个数组。有个问题要求我们必须以字典顺序返回结果时，那么我们想到要排序。
一般考虑：
假设有一种人，分给他们每人一副大乱顺序的扑克，要求他们按从大到小排序。一些人可能按桩的结构排，一些人还可能把牌都放在桌子上排好序，还有一些人可能在手中就排好序了。但他们所用的时间可能不一样。可能会出现很多样的排序方式。
在我们排序时，我们必须有几件事要考虑，首先就是时间。
另一个考虑的问题就是所用到的内存空间。
另一点要考虑的就是稳定性。
冒泡排序：
首先我们想到的就是冒泡排序，他的时间复杂度为O(n²)，但他要求的内存空间也很低。
for (int i = 0; i < data.Length; i++)
for (int j = 0; j < data.Length - 1; j++)
if (data[j] > data[j + 1])
{
tmp = data[j];
data[j] = data[j + 1];
data[j + 1] = tmp;
}
插入排序：
每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。
for (int i = 0; i <= data.Length; i++) {
int j = i;
while (j > 0 && data[i] < data[j - 1])
j--;
int tmp = data[i];
for (int k = i; k > j; k--)
data[k] = data[k - 1];
data[j] = tmp;
}
比如有这么一组数据，插入排序的过程为：
{18, 6, 9, 1, 4, 15, 12, 5, 6, 7, 11}
{ 6, 18, 9, 1, 4, 15, 12, 5, 6, 7, 11}
{ 6, 9, 18, 1, 4, 15, 12, 5, 6, 7, 11}
{ 1, 6, 9, 18, 4, 15, 12, 5, 6, 7, 11}
{ 1, 4, 6, 9, 18, 15, 12, 5, 6, 7, 11}
{ 1, 4, 6, 9, 15, 18, 12, 5, 6, 7, 11}
{ 1, 4, 6, 9, 12, 15, 18, 5, 6, 7, 11}
{ 1, 4, 5, 6, 9, 12, 15, 18, 6, 7, 11}
{ 1, 4, 5, 6, 6, 9, 12, 15, 18, 7, 11}
{ 1, 4, 5, 6, 6, 7, 9, 12, 15, 18, 11}
{ 1, 4, 5, 6, 6, 7, 9, 11, 12, 15, 18}
插入排序的优点就是我们只考虑要插入的元素。待排序元素已从小到大排好序(正序)或接近排好序时,所用的比较次数和移动次数较少。
归并排序：
递归的归并排序：思想就是把要排序的数组分成2部分，并且单独的对他们进行排序，然后比较这2个数组里的第一个元素，把小的那个元素从此数组里删除添加到结果数组里。
int[] mergeSort (int[] data) {
if (data.Length == 1)
return data;
int middle = data.Length / 2;
int[] left = mergeSort(subArray(data, 0, middle - 1));
int[] right = mergeSort(subArray(data, middle, data.Length - 1));
int[] result = new int[data.Length];
int dPtr = 0;
int lPtr = 0;
int rPtr = 0;
while (dPtr < data.Length) {
if (lPtr == left.Length) {
result[dPtr] = right[rPtr];
rPtr++;
} else if (rPtr == right.Length) {
result[dPtr] = left[lPtr];
lPtr++;
} else if (left[lPtr] < right[rPtr]) {
result[dPtr] = left[lPtr];
lPtr++;
} else {
result[dPtr] = right[rPtr];
rPtr++;
}
dPtr++;
}
return result;
}
没一次递归所用的时间复杂度为0(n),总共进行了0(log n)次，因此时间复杂度为0(n * log n)
{18, 6, 9, 1, 4, 15, 12, 5, 6, 7, 11}
{18, 6, 9, 1, 4} {15, 12, 5, 6, 7, 11}
{18, 6} {9, 1, 4} {15, 12, 5} {6, 7, 11}
{18} {6} {9} {1, 4} {15} {12, 5} {6} {7, 11}
{18} {6} {9} {1} {4} {15} {12} {5} {6} {7} {11}
{18} {6} {9} {1, 4} {15} {5, 12} {6} {7, 11}
{6, 18} {1, 4, 9} {5, 12, 15} {6, 7, 11}
{1, 4, 6, 9, 18} {5, 6, 7, 11, 12, 15}
{1, 4, 5, 6, 6, 7, 9, 11, 12, 15, 18}
堆排序
在堆排序中，我们创造一个堆的数据结构，它就像一棵树一样，最小的元素始终在根节点上。执行堆排序时，所以的元素必须都插入到堆中，然后把根节点从堆移到结果数组中。
/*
ary是存储记录的数组， start是需要调整为大顶堆的根记录下标， end是
它的最后一个叶子记录的下标。
注意，传入的start到end之间的记录，除去根记录，根记录的左右子二叉树都
是大顶堆，要完全符合大顶堆的性质调用此函数才有效。
下面函数要做的就是调整以start为根记录，end为最后一个叶子记录的完全二叉树为大顶堆。
*/
void Heapify(int ary[], unsigned int start, unsigned int end)
{
unsigned int left = 0;
unsigned int right = 0;
unsigned int max = 0;
left = start * 2;
right = start * 2 + 1;
/* 如果存在左子记录 */
while (left <= end)
{
/* 左右子记录中，先默认左子记录的关键字值最大，保存其下标 */
max = left;
/* 如果左右子记录都存在，改写max使其保存了拥有最大关键字值记录的下标 */
if (right <= end)
{
if (ary[left] < ary[right])
{
max = right;
}
else
{
max = left;
}
}
/* 现在max中是保存了左右子记录中（假设存在）关键字值最大的下标 */
if (ary[start] < ary[max])
{
/* 根记录的关键字值小于左右子记录中关键字值最大的 */
ary[0] = ary[max];
ary[max] = ary[start];
ary[start] = ary[0];
/* 从被交换的子记录中开始调整 */
start = max;
}
else
{
/* 二叉树符合大顶堆性质， 调整结束 */
break;
}
left = start * 2;
right = start * 2 + 1;
}
/* 调整到最二叉树的最后一个叶子结点上，二叉树也符合大顶堆性质， 调整结束 */
}
/* 进行堆排序，完成后ary中的记录下标从1到size，它们的关键字值是非递减的 */
void HeapSort(int ary[], unsigned int size)
{
/* 建堆 */
BuildHeap(ary, size);
for (unsigned int i = size; i > 0; i--)
{
/* 把根记录和最后一个叶子记录交换 */
ary[0] = ary[1];
ary[1] = ary[i];
ary[i] = ary[0];
/*
调整从1到i- 1组成的二叉树为大顶堆。
注意：
交换只是破坏了以ary【1】为根的二叉树大顶堆性质，它的左右
子二叉树还是具 备大顶堆性质。
*/
Heapify(ary, 1, i - 1);
}
}
/*
调整整棵二叉树（完全无序状态）使之成为大顶堆。
策略：
首先这课二叉树的结构是完全二叉树，我们可以从最后一个非叶子记录调整，
直到整棵二叉树的根记录。
比如二叉树有size个结点记录，那么最后一个非叶子结点的下标就
是size / 2（取整）， 我们就从size / 2, size / 2 - 1, ... ,
直到调整以1为下标的整棵二叉树为大顶堆。
因为以最后一个叶子记录为根的二叉树必定符合调用函数Heapify的条件，
位于同一层的非叶子结点必定也符合调用条件，Heapify函数处理完后这一层后，
上一层的非叶子记录对应的二叉树也符合了调用条件，
这样直到以整棵二叉树的根（即ary【1】）记录为根的二叉树也符合大顶堆的性质，
整个大顶堆就建立起来。
现在整棵二叉树的根记录就是该记录集中关键字值最大的记录。
*/
void BuildHeap(int ary[], unsigned int size)
{
/* 传入下标为i（size / 2 >= i >= 1）的记录为根，
下标为size的最后一个叶子记录的二叉树进行调整 */
for (unsigned int i = size / 2; i > 0; i--)
{
Heapify(ary, i, size);
}
}
/*
算法分析：
1.堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，
它们均是通过调用Heapify实现的。
堆排序的最坏时间复杂度为O(n * lgn)。堆排序的平均性能较接近于最坏性能。
BuildHeap最坏情况下时间复杂度为O（n），但是for循环在最坏情况下却
要O（n * lgn）的时间。
2.由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。
3.堆排序是就地排序，辅助空间为O(1)。
4.它是不稳定的排序方法。
*/
堆排序的时间复杂度为O(n * log n).
源文档 <http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=sorting>
快速排序
快速排序像哈夫曼树类似，首先把排序的数组分成2部分，使前部分小于关键字，后部分大于关键字。然后递归排序
void QuickSort(SeqList R，int low，int high)
{ //对R[low..high]快速排序
int pivotpos； //划分后的基准记录的位置
if(low<high){//仅当区间长度大于1时才须排序
pivotpos=Partition(R，low，high)； //对R[low..high]做划分
QuickSort(R，low，pivotpos-1)； //对左区间递归排序
QuickSort(R，pivotpos+1，high)； //对右区间递归排序
}
} //QuickSort
int Partition(SeqList R，int i，int j)
{//调用Partition(R，low，high)时，对R[low..high]做划分，
//并返回基准记录的位置
ReceType pivot=R[i]； //用区间的第1个记录作为基准 '
while(i<j){ //从区间两端交替向中间扫描，直至i=j为止
while(i<j&&R[j].key>=pivot.key) //pivot相当于在位置i上
j--； //从右向左扫描，查找第1个关键字小于pivot.key的记录R[j]
if(i<j) //表示找到的R[j]的关键字<pivot.key
R[i++]=R[j]； //相当于交换R[i]和R[j]，交换后i指针加1
while(i<j&&R[i].key<=pivot.key) //pivot相当于在位置j上
i++； //从左向右扫描，查找第1个关键字大于pivot.key的记录R[i]
if(i<j) //表示找到了R[i]，使R[i].key>pivot.key
R[j--]=R[i]; //相当于交换R[i]和R[j]，交换后j指针减1
} //endwhile
R[i]=pivot； //基准记录已被最后定位
return i；
} //partition
源文档 <http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.3.2.1.htm>
快速排序的最坏时间复杂度应为0(n2)，最好时间复杂度为O(nlgn)。
基树排序
基数排序是非比较排序算法,算法的时间复杂度是O(n). 相比于快速排序的O(nlgn),从表面上看具有不小的优势.但事实上可能有些出入,因为基数排序的n可能具有比较大的系数K.因此在具体的应用中,应首先对这个排序函数的效率进行评估.
基数排序的主要思路是,将所有待比较数值(注意,必须是正整数)统一为同样的数位长度,数位较短的数前面补零. 然后, 从最低位开始, 依次进行一次稳定排序(我们常用上一篇blog介绍的计数排序算法, 因为每个位可能的取值范围是固定的从0到9).这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列.
比如这样一个数列排序: 342 58 576 356, 以下描述演示了具体的排序过程(红色字体表示正在排序的数位)
第一次排序(个位):
3 4 2
5 7 6
3 5 6
0 5 8
第二次排序(十位):
3 4 2
3 5 6
0 5 8
5 7 6
第三次排序(百位):
0 5 8
3 4 2
3 5 6
5 7 6
结果: 58 342 356 576
源文档 <http://www.cnblogs.com/sun/archive/2008/06/26/1230095.html>
源文档 <http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=sorting>