C++程序设计中关于排序的探讨

摘要：排序就是在计算机中对不规则数据进行升序或降序排列实现的方法；排序算法有冒泡排序、选择排序和插入排序等，各种算法的实现其复杂度都不一样，复杂度的大小体现了算法的优劣。

关键词：冒泡排序；选择排序；插入排序

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2012）31-7504-04

排序（Sorting）是C++程序设计中基本并且常用的算法，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。本文将讨论三种排序算法的实现，并对三种排序算法进行比较分析。

1　排序的分类

1.1　按是否涉及数据的内、外存交换分为[1]：

1）内部排序：　内部排序（简称内排序），是带排序纪录存放在计算机内存中进行的排序过程。

2）外部排序：　外部排序（简称外排序），是带排序纪录的数量很大，以至于内存一次不能容纳全部纪录，在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序的排序方法。

1.2　按策略划分内部排序可分为

1）插入排序，包括：直接插入排序，其它插入排序，希尔排序；

2）快速排序，包括：冒泡排序，快速排序；

3）选择排序，包括：简单选择排序，树形选择排序，堆排序；

4）归并排序；

5）基数排序，包括：多关键字的排序，链式基数排序。

2　排序的实现

由于排序有很多种方法，本文主要讨论内部排序的几种实现。

2.1冒泡排序

算法实现思想：将被排序的数组R[1...n]垂直排列，即将元素R[1]到R[n]排列垂直如气泡状，约定数据小的为轻气泡，大的为重气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上”飘浮[2]”。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止（图1）。

2.2　简单选择排序

算法实现思想：　对于一组数据{K1，K2，…，Kn}，首先从K1，K2，…，Kn中选择最小值，假如它是Kz，则将Kz与K1对换，然后从K2，K3，…，Kn中选择最小值Kz，再将Kz与K2对换.　如此进行选择和调换n-2趟，第（n-1）趟，从Kn-1、Kn中选择最小值Kz将Kz与Kn-1对换，最后剩下的就是该序列中的最大值，一个由小到大的有序序列就这样形成.　即：　在要排序的一组数中，选出最小的一个数与第一个位置的数交换，然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止（图2）。

直接插入排序（Straight　Insertion　Sort）是一种最简单的排序方法，它的基本思想是将任一数插入到已排好序的数据序列中并保持序列的排序。如果数组a[n]中存放的数据序列是升序，当插入的数num比已有序列最后一个数大，则将插入到序列的末尾；如果插入的数num不比序列最后一个数大，则将它依次与a[0]～a[n-1]进行比较，直到出现a[i]>=num为止，这时表示a[0]～a[i-1]各元素的值比num小，这时将a[i]～a[n-1]各元素向后移一人位置，把a[i]空出，最后将num放在a[i]中，最终完成插入排序。

程序设计如下：

3　排序算法的分析

3.1　排序算法比较

3.1.1　简单选择排序

1）关键字比较次数

无论文件初始状态如何，在第i趟排序选出最小关键字的记录，需做n-i次比较，因此总的比较次数为：　n（n-1）/2　=　O（n2）。

2）记录的移动次数

当初始文件为“正序”时，移动次数为0　；当文件初态反序时，每趟排序均要执行交换操作，其中的移动次数取最大值（n-1）　；

3）时间复杂度

简单选择排序的平均时间复杂度[1]为O（n2）　。

4）稳定性分析

简单选择排序是不稳定的。

3.1.2　冒泡排序

1）关键字比较次数

若初始序列为“正序”序列，则只需进行一趟排序，在排序过程中进行（n-1）次关键字的比较。反之，若初始序列为“逆序”序列，则需进行（n-1）趟排序，需进行n（n-1）/2次比较。

2）记录的移动次数

当初始文件为“正序”时，移动次数为0　；当文件初态“反序”时，每趟排序均要执行交换操作，其中的移动次数取最大值n（n-1）/2　；

3）时间复杂度

冒泡排序的平均时间复杂度为O（n2）　。但当原始关键字序列已有序时，只进行一趟比较就结束，此时时间复杂度为O（n）.

4）稳定性分析

冒泡排序是稳定的。

3.1.3　直接插入排序

1）关键字比较次数

若初始序列为“正序”序列，则只需进行一趟排序，在排序过程中进行（n-1）次关键字的比较。反之，若初始序列为“逆序”序列，则需进行（n+2）（n-1）/2次比较。

2）记录的移动次数

当初始文件为“正序”时，最小移动次数为0　；当文件初态“反序”时，记录移动的次数也达最大值[1]：（n+4）（n-1）/2　；

3）时间复杂度

直接插入排序的平均时间复杂度为O（n2）　。

4）稳定性分析

冒泡排序是稳定的。

3.2　排序算法的分析

1）若n较小（如n≤50），可采用直接插入或简单选择排序。

当记录规模较小时，直接插入排序较好；否则因为简单选择移动的记录数少于直接插人，应选简单选择排序为宜。

2）若文件初始状态基本有序（指正序），则应选用直接插人、冒泡排序为宜；

3）若n较大，则应采用时间复杂度为O（nlgn）[3]的排序方法：快速排序、堆排序或归并排序。

快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短。

参考文献：

[1]　严蔚敏，吴伟民.数据结构[M].北京：清华大学出版社，2002.

[2]　孙宏昌，王燕来.C语言程序设计[M].　北京：高等教育出版社，2002.

[3]　谭浩强.C++程序设计题解[M].北京：清华大学出版社，2005.