几种经典排序算法优劣比较的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），是一种稳定的排序算法。