‘壹’ 基于比较的排序算法
基于比较的排序算法，应该是最符合人们直觉的方法。在各种算法的技术书上，已经证明了基于比较的排序算法的时间最优复杂度为O(nlogn)。
下面是几种常见的基于比较的排序算法：
1. 选择排序：这应该是最直观的排序方法。在排序n个元素时，第一次遍历，找到最小的元素，将其与第一个元素互换；第二次遍历，找到次小的元素，将其与第二个元素交换；直至剩下最后一个元素。
2. 冒泡排序：这应该是我们学到的第一种排序算法。基本思想就是，通过依次比较相邻的两个元素，如后值比前值小，则交换这两个值，小值被交换到前面，大值被交换到后面。这样一次遍历后，最大值被放到最后。而小值被交换到n-1前。然后再次遍历前n-1，n-2，直至最后2个元素。整个儿过程，小值随着不断的遍历过程，逐渐被交换到前面，很像气泡逐渐从水底逐渐冒出。所以被称为冒泡算法。
3. 插入排序：这个算法的思想很直观。按照《算法导论》中的解释，这个算法可以参照我们平时打扑克的情形。当抓取一张牌的时候，按顺序比较手牌，将其插入到恰当的位置。这样保证了手中所有的牌依然有序。当已排序的值数量较多时，由于已经保证了有序，那么在确定新值插入位置的时候，可以通过二分查找的方法来去确定插入位置。
4. 希尔排序：在冒泡算法中，所以小值只能以步长为1的速度向前面移动。希尔排序在步长上作了优化，开始以一个较大的m步长进行分组，每组进行插入排序，这样就实现了步长为m的移动。然后逐渐缩小步长m直至1。所以根本思想是尽可能的将元素移动较远的位置代替移动一位。
5.归并排序：该思想利用的是解决问题的一个常用思想，divide-and-conquer，即分而治之的思想。将n个元素每次2分，变为两个n/2个元素组，直至1个元素——1个元素，自然是排好序了。然后，再两两合并元素组，最终合并为一个元素组。归并算法，因为需要归并，所以必然需要一个额外的n空间来实现归并。
6.快速排序：同样是分而治之的思想，将原始数据分为2组。但是与归并算法直接将原始数据分为两部分不同的是，快排选择一个中值，新的两个子组，一个子组所有的元素都小于中值，另外一个子组所有的元素都大于等于中值，直至元素个数为1。当元素个数为1时，实际上快排已经完成了排序。这点与归并排序也不同，快排在子组完成以后，无需额外的操作。很明显，快排的效率依赖于中值的选择。如果中值可以将数据分为两个数量相等的子组，那么效率则为最高的。快排无需额外的存储空间，可以in-place进行排序。
7.堆排序：该思想是将原始元素视为一个平衡二叉树。然后要求父节点必须大于子节点的规则，调整该平衡二叉树。由于是平衡二叉树，所以数据被完美的等分。这样根节点即为最大值。这时，堆排序完成了最大值的选择。为排序，则将根节点与最后一个子节点交换。此时，树的规则被破坏，需要从根节点逐级verify规则。
‘贰’ 几种经典排序算法优劣比较的C++程序实现
一、低级排序算法
1.选择排序
（1）排序过程
给定一个数值集合，循环遍历集合，每次遍历从集合中选择出最小或最大的放入集合的开头或结尾的位置，下次循环从剩余的元素集合中遍历找出最小的并如上操作，最后直至所有原集合元素都遍历完毕，排序结束。
（2）实现代码
//选择排序法
template
void Sort：：SelectSort（T* array， int size）
{
int minIndex；
for（int i = 0； i < size； i++）
{
minIndex = i；
for（int j = i + 1； j < size； j++）
{
if（array[minIndex] > array[j]）
{
minIndex = j；
}
}
if（minIndex ！= i）
{
Swap（array， i， minIndex）；
}
}
}
（3）分析总结
选择排序时间复杂度比较高，达到了O（n^2），每次选择都要遍历一遍无序区间。选择排序对一类重要的元素序列具有较好的效率，就是元素规模很大，而排序码却比较小的序列。另外要说明的是选择排序是一种不稳定的排序方法。
2.冒泡排序
（1）排序过程
冒泡排序的过程形如其名，就是依次比较相邻两个元素，优先级高（或大或小）的元素向后移动，直至到达序列末尾，无序区间就会相应地缩小。下一次再从无序区间进行冒泡操作，依此循环直至无序区间为1，排序结束。
（2）实现代码
//冒泡排序法
template
void Sort：：BubbleSort（T* array， int size）
{
for（int i = 0； i < size； i++）
{
for（int j = 1； j < size - i； j++）
{
if（array[j] < array[j - 1]）
{
Swap（array， j， j - 1）；
}
}
}
}
（3）分析总结
冒泡排序的时间复杂度也比较高，达到O（n^2），每次遍历无序区间都将优先级高的元素移动到无序区间的末尾。冒泡排序是一种稳定的排序方式。
二、高级排序算法
（1）排序过程
归并排序的原理比较简单，也是基于分治思想的。它将待排序的元素序列分成两个长度相等的子序列，然后为每一个子序列排序，然后再将它们合并成一个序列。
（2）实现代码
//归并排序
template
void Sort：：MergeSort（T* array， int left， int right）
{
if（left < right）
{
int mid = （left + right） / 2；
MergeSort（array， left， mid）；
MergeSort（array， mid + 1， right）；
Merge（array， left， mid， right）；
}
}
//合并两个已排好序的子链
template
void Sort：：Merge（T* array， int left， int mid， int right）
{
T* temp = new T[right - left + 1]；
int i = left， j = mid + 1， m = 0；
while（i <= mid && j <= right）
{
if（array[i] < array[j]）
{
temp[m++] = array[i++]；
}
else
{
temp[m++] = array[j++]；
}
}
while（i <= mid）
{
temp[m++] = array[i++]；
}
while（j <= right）
{
temp[m++] = array[j++]；
}
for（int n = left， m = 0； n <= right； n++， m++）
{
array[n] = temp[m]；
}
delete temp；
}
（3）分析总结
归并排序最好、最差和平均时间复杂度都是O（nlogn），是一种稳定的排序算法。