摘 要：排序是编程过程中经常遇到的操作，它在很大程度上影响了程序的执行效率。目前关于排序的算法有很多，其中不乏非常精妙的算法。但是总体来说，作为一个计算机专业的学习者来说，必须要知道而且会亲自动手去实现文中列举的几种常见的算法。这不管对自己编程能力的提高还是日后的实习就业都会有莫大的帮助。
　　关键词：选择排序 算法 比较 归并排序 冒泡排序法
　　三种常见的排序算法大致可以分为两类：
　　第一类是低级排序算法，有选择排序、冒泡排序。
　　第二类是高级排序算法，有归并排序。
　　下面就分别介绍一下这几种排序算法，并会给出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），是一种稳定的排序算法。
　　三、结语
　　如上介绍的几种排序算法都是基于算法最基本的思想来实现的，其实对其中一些算法都会有几种可以改进的地方，如能亲自实现，这对学生的学习和工作都会有莫大的帮助。