现有序列{9,3,5,1,6,2,8,4,7}，以此为例子，阐述各个常用排序算法。

直接插入排序：

每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。

第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。 直接插入排序属于稳定的排序，时间复杂性为o(n^2)，空间复杂度为O(1)。 9，3，5，1，6，2，8，4，7

3，9，5，1，6，2，8，4，7

3，5，9，1，6，2，8，4，7

1，3，5，9，6，2，8，4，7

1，3，5，6，9，2，8，4，7

1，2，3，5，6，9，8，4，7

1，2，3，5，6，8，9，4，7

1，2，3，4，5，6，8，9，7

1，2，3，4，5，6，7，8，9

希尔排序：

先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

取增量为5

则分为五个组（9，2）（3，8）（5，4）（1，7）（6），对这些分组内部进行插入排序， 得到：2，3，4，1，6，8，5，7，9

取增量为3

则分为三个组 （2，1，5）（3，6，7）（4，8，9）

得到：1，3，4，2，6，8，5，7，9

取增量为1

得到 1，2，3，4，5，6，7，8，9

9，3，5，1，6，2，8，4，7 增量＝5 对同一颜色进行内部插入排序 2，3，4，1，6，8，5，7，9 增量＝3

1，3，4，2，6，8，5，7，9 增量＝1

1，2，3，4，5，6，7，8，9

冒泡排序：

冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复以上过程，仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到最大数前的一对相邻数，将小数放前，大数放后，第二趟结束，在倒数第二个数中得到一个新的最大数。如此下去，直至最终完成排序。

9，3，5，1，6，2，8，4，7

3，5，1，6，2，8，4，7，9

3，1，5，2，6，4，7，8，9

1，3，2，5，4，6，7，8，9

1，2，3，4，5，6，7，8，9

1，2，3，4，5，6，7，8，9

1，2，3，4，5，6，7，8，9

1，2，3，4，5，6，7，8，9

快速排序：

设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。一趟快速排序的算法是：

1）设置两个变量I、J，排序开始的时候：I=1，J=N-1；

2）以第一个数组元素作为关键数据，赋值给X，即 X=A[0]；

3）从J开始向前搜索，即由后开始向前搜索（J=J-1），找到第一个小于X的值，让该值与X交换；

4）从I开始向后搜索，即由前开始向后搜索（I=I+1），找到第一个大于X的值，让该值与X交换； 5）重复第3、4步，直到 I=J；

935162847

735162849

43516287 9

23516487 9

23416587 9

23146587 9

123 4 5687 9

123 4 5 6 78 9

123456789

归并排序：

归并排序（MERGE SORT）是又一类不同的排序方法，合并的含义就是将两个或两个以上的有序数据序列合并成一个新的有序数据序列，因此它又叫归并算法。它的基本思想就是假设数组A有N个元素，那么可以看成数组A是又N个有序的子序列组成，每个子序列的长度为1，然后再两两合并，得到了一个 N/2 个长度为2或1的有序子序列，再两两合并，如此重复，直到得到一个长度为N的有序数据序列为止，这种排序方法称为2—路合并排序。 9，3，5，1，6，2，8，4，7

3，9， 1，5， 2，6， 4，8， 7

1，3，5，9， 2，4，6，8， 7 两次合并后

1，2，3，4，5，6，8，9， 7 第三次合并后

1，2，3，4，5，6，7，8，9 第四次合并后

选择排序：

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

选择排序是不稳定的排序方法。

n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果： ①初始状态：无序区为R[1..n]，有序区为空。

②第1趟排序

在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

……

③第i趟排序

第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。 9，3，5，1，6，2，8，4，7 第一次扫描，1最小，将1与第一个数交换 1，3，5，9，6，2，8，4，7 第二次扫描，2最小，将2与第二个数交换 1，2，5，9，6，3，8，4，7

1，2，3，9，6，5，8，4，7

1，2，3，4，6，5，8，9，7

1，2，3，4，5，6，8，9，7

1，2，3，4，5，6，7，9，8

1，2，3，4，5，6，7，8，9 第八次扫描，8最小，将8与第八个数交换 1，2，3，4，5，6，7，8，9

基数排序：

需而外构造十个数组或链表。对该例子进行一次分配就可排好。

第二篇：排序算法总结

按平均时间将排序分为四类： （1）平方阶(O(n2))排序

一般称为简单排序，例如直接插入、直接选择和冒泡排序； （2）线性对数阶(O(nlgn))排序 如快速、堆和归并排序； （3）O(n1+￡)阶排序

￡是介于0和1之间的常数，即0<￡<1，如希尔排序； （4）线性阶(O(n))排序 如桶、箱和基数排序。 各种排序方法比较

简单排序中直接插入最好，快速排序最快，当文件为正序时，直接插入和冒泡均最佳。 影响排序效果的因素

因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法应综合考虑下列因素： ①待排序的记录数目n； ②记录的大小(规模)；

③关键字的结构及其初始状态； ④对稳定性的要求； ⑤语言工具的条件； ⑥存储结构；

⑦时间和辅助空间复杂度等。 不同条件下，排序方法的选择

(1)若n较小(如n≤50)，可采用直接插入或直接选择排序。 当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。

(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；

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

快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短； 堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。

若要求排序稳定，则可选用归并排序。但本章介绍的从单个记录起进行两两归并的 排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件，然后再两两归并之。因为直接插入排序是稳定的，所以改进后的归并排序仍是稳定的。 排序算法的稳定性

1） 稳定的：如果存在多个具有相同排序码的记录，经过排序后，这些记录的相对次序仍然保持不变，则这种排序算法称为稳定的。 插入排序、冒泡排序、归并排序、分配排序（桶式、基数）都是稳定的排序算法。

2）不稳定的：否则称为不稳定的。

直接选择排序、堆排序、shell排序、快速排序都是不稳定的排序算法。

[原创]几种常用排序算法总结!您所在位置：编程爱好者网站 — 编程爱好者论坛

前两天为准备考软件设计师就顺便复习了下几个常用的排

序算法,今天贴出来,供大家参考!对其中的错漏之处,敬请指正! 排序

所谓排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。当待排序记录的关键字都不相同时，排序结果是惟一的，否则排序结果不惟一。

在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生改变，则称这种排序方法是不稳定的。

要注意的是，排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。 一.插入排序

插入排序的基本思想是每步将一个待排序的记录按其排序码值的大小，插到前面已经排好的文件中的适当位置，直到全部插入完为止。插入排序方法主要有直接插入排序和希尔排序。 ①.直接插入排序(稳定)

接插入排序的过程为：在插入第i个记录时，R1,R2,..Ri-1已经排好序，将第i个记录的排序码Ki依次和R1,R2,..,Ri-1的排序码逐个进行比较，找到适当的位置。使用直接插入排序，对于具有n个记录的文件，要进行n-1趟排序。 代码如下:

void Dir_Insert(int A[],int N) //直接插入排序 { int j,t;

for(int i=1;i<N;i++) {

t=A[i]; j=i-1; while(A[j]>t) {

A[j+1]=A[j]; j--; } A[j+1]=t; } }

②.希尔排序(不稳定)：

希尔(Shell)排序的基本思想是：先取一个小于n的整数d1作为第一个增量把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取得第二个增量d2<d1重复上述的分组和排序，直至所取的增量di=1，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。

一般取d1=n/2，di+1=di/2。如果结果为偶数，则加1，保证di为奇数。

希尔排序是不稳定的，希尔排序的执行时间依赖于增量序列，其平均时间复杂度为O(n^1.3). 代码如下:

void Shell(int A[],int n) //Shell排序 {

int i,j,k,t;

(n/2)%2 == 0 ? k = n/2+1 : k = n/2; //保证增量为奇数

while(k > 0) {

for(j=k;j<n; j++) {

t = A[j]; i = j - k;

while(i>=0 && A[i]>t) {

A[i+k]=A[i]; i=i-k; } A[i+k]=t; }

if(k == 1) break;

(k/2)%2 ==0 ? k=k/2+1 : k=k/2; } } 二.选择排序

选择排序的基本思想是每步从待排序的记录中选出排序码最小的记录，顺序存放在已排序的记录序列的后面，直到全部排完。选择排序中主要使用直接选择排序和堆排序。

①.直接选择排序(不稳定)

直接选择排序的过程是：首先在所有记录中选出序码最小的记录，把它与第1个记录交换，然后在其余的记录内选出排序码最小的记录，与第2个记录交换......依次类推，直到所有记录排完为止。

无论文件初始状态如何，在第i趟排序中选出最小关键字的记录，需要做n-i次比较，因此，总的比较次数为n(n-1)/2=O(n^2)。当初始文件为正序时，移动次数为0；文件初态为反序时，每趟排序均要执行交换操作，总的移动次数取最大值3(n-1)。直接选择排序的平均时间复杂度为O(n^2)。直接选择排序是不稳定的。

代码如下:

void Dir_Choose(int A[],int n) //直接选择排序

{

int k,t;

for(int i=0;i<n-1;i++) { k=i;

for(int j=i+1;j<n;j++) {

if(A[j]<A[k]) k=j; } if(k!=i) {

t=A[i]; A[i]=A[k]; A[k]=t; }

} }

②.堆排序(不稳定)

堆排序是一种树形选择排序，是对直接选择排序的有效改进。n个关键字序列

K1,K2,...,Kn称为堆，当且仅当该序列满足(Ki<=K2i且Ki<=K2i+1)或(Ki>=K2i且Ki>=K2i+1),(1<=i<=n/2)。根结点(堆顶)的关键字是堆里所有结点关键字中最小者，称为小根堆；根结点的关键字是堆里所有结点关键字中最大者，称为大根堆。

若将此序列所存储的向量R[1..n]看作是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。

堆排序的关键步骤有两个：一是如何建立初始堆；二是当堆的根结点与堆的最后一个结点交换后，如何对少了一个结点后的结点序列做调整，使之重新成为堆。堆排序的最坏时间复杂度为O(nlog2n),堆排序的平均性能较接近于最坏性能。由于建初始堆所需的比较 次数较多，所以堆排序不适宜于记录较少的文件。堆排序是就地排序，辅助空间为O(1)，它是不稳定的排序方法。

三.交换排序

交换排序的基本思想是：两两比较待排序记录的排序码，并交换不满足顺序要求的那写偶对，直到满足条件为止。交换排序的主要方法有冒泡排序和快速排序.

①.冒泡排序(稳定的)

冒泡排序将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为ki的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R；凡扫描到违反本原则的轻气泡，就使其向上"漂浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。

冒泡排序的具体过程如下：

第一步，先比较k1和k2，若k1>k2，则交换k1和k2所在的记录，否则不交换。继续对k2和k3重复上述过程，直到处理完kn-1和kn。这时最大的排序码记录转到了最后位置，称第1次起泡，共执行n-1次比较。

与第一步类似，从k1和k2开始比较，到kn-2和kn-1为止，共执行n-2次比较。依次类推，共做n-1次起泡，完成整个排序过程。若文件的初始状态是正序的，一趟扫描即可完成排序。所需关键字比较次数为n-1次，记录移动次数为0。因此，冒泡排序最好的时间复杂度为O(n)。

若初始文件是反序的，需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1<=i<=n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较次数达到最大值n(n-1)/2=O(n^2),移动次数也达到最大值3n(n-1)/2=O(n^2)。因此，冒泡排序的最坏时间复杂度为O(n^2)。虽然冒泡排序不一定要进行n-1趟，但由于它的记录移动次数较多，故平均性能比直接插入排序要差得多。冒泡排序是就地排序，且它是稳定的。

代码如下:

void QP(int A[],int n) //优化的冒泡排序 {

int count=0,t,flag; for(int i=0;i<n-1;i++)

{

flag=0;

for(int j=0;j<n-i;j++) {

if(A[j+1]<A[j]) {

t=A[j]; A[j]=A[j+1]; A[j+1]=t; flag=1; count+=3; } }

if(flag==0) break; } }

②.快速排序：(不稳定的)

快速排序采用了一种分治的策略，通常称其为分治法，其基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。快速排序的具体过程如下：

第一步，在待排序的n个记录中任取一个记录，以该记录的排序码为准，将所有记录分成两组，第1组各记录的排序码都小于等于该排序码，第2组各记录的排序码都大于该排序码，并把该记录排在这两组中间。

第二步，采用同样的方法，对左边的组和右边的组进行排序，直到所有记录都排到相应的位置为止。 代码如下:

void Quick_Sort(int A[],int low,int high) //low和high是数组的下标 {

if(low<high) {

int temp,t=A[low]; int l=low,h=high; while(l<h) {

while(A[l]<t) l++; while(A[h]>=t) h--; if(h>l) {

temp=A[l]; A[l]=A[h]; A[h]=temp; } }

Quick_Sort(A,low,l-1); Quick_Sort(A,l+1,high); } } 四.归并排序

归并排序是将两个或两个以上的有序子表合并成一个新的有序表。初始时，把含有n个结点的待排序序列看作由n个长度都为1的有序子表组成，将它们依次两两归并得到长度为2的若干有序子表，再对它们两两合并。直到得到长度为n的有序表，排序结束。归并排序是一种稳定的排序，可用顺序存储结构，也易于在链表上实现，对长度为n的文件，需进行log2n趟二路归并，每趟归并的时间为O(n),故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。归并排序需要一个辅助向量来暂存两个有序子文件归并的结果，故其辅助空间复杂度为O(n),显然它不是就地排序。

五.基数排序

设单关键字的每个分量的取值范围均是C0<=Kj<=Crd-1(0<=j<=rd),可能的取值个数rd称为基数．基数的选择和关键字的分解因关键字的类型而异．

(1).若关键字是十进制整数，则按个、十等位进行分解，基数rd=10,C0=0,C9=9,d为最长整数的位数．

(2).若关键字是小写的英文字符串，则rd=26,C0='a',C25='z',d为最长字符串的长度．基数排序的基本思想是：从低位到高位依次对待排序的关键码进行分配和收集，经过d趟分配和收集，就可以得到一个有序序列．

按平均时间将排序分为四类： （1）平方阶(O(n2))排序

一般称为简单排序，例如直接插入、直接选择和冒泡排序；

（2）线性对数阶(O(nlgn))排序 如快速、堆和归并排序； （3）O(n1+￡)阶排序

￡是介于0和1之间的常数，即0<￡<1，如希尔排序；

（4）线性阶(O(n))排序 如基数排序。

各种排序方法比较简单排序中直接插入最好，快速排序最快，当文件为正序时，直接插入和冒泡均最佳。

影响排序效果的因素因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法应综合考虑下列因素： ①待排序的记录数目n； ②记录的大小(规模)；

③关键字的结构及其初始状态； ④对稳定性的要求； ⑤语言工具的条件； ⑥存储结构；

⑦时间和辅助空间复杂度等。 不同条件下，排序方法的选择

(1)若n较小(如n≤50)，可采用直接插入或直接选择排序。当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。

(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；

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

快速排序是目前基于比较的内部排序中被认为是最好的方

法，当待排序的关键字是随机分布时，快速排序的平均时间最短； 堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。

若要求排序稳定，则可选用归并排序。但从单个记录起进行两两归并的 排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件，然后再两两归并之。因为直接插入排序是稳定的，所以改进后的归并排序仍是稳定的。

排序的算法有很多，对空间的要求及其时间效率也不尽相同。下面列出了一些常见的排序算法。这里面插入排序和冒泡排序又被称作简单排序，他们对空间的要求不高，但是时间效率却不稳定；而后面三种排序相对于简单排序对空间的要求稍高一点，但时间效率却能稳定在很高的水平。基数排序是针对关键字在一个较小范围内的排序算法。

插入排序 冒泡排序 选择排序 快速排序 堆排序 归并排序 基数排序 希尔排序

插入排序是这样实现的： 首先新建一个空列表，用于保存已排序的有序数列（我们称之为"有序列表"）。

从原数列中取出一个数，将其插入"有序列表"中，使其仍旧保持有序状态。 重复2号步骤，直至原数列为空。

插入排序的平均时间复杂度为平方级的，效率不高，但是容易实现。它借助了"逐步扩大成果"的思想，使有序列表的长度逐渐增加，直至其长度等于原列表的长度。 冒泡排序

冒泡排序是这样实现的： 首先将所有待排序的数字放入工作列表中。

从列表的第一个数字到倒数第二个数字，逐个检查：若某一位上的数字大于他的下一位，则将它与它的下一位交换。 重复2号步骤，直至再也不能交换。

冒泡排序的平均时间复杂度与插入排序相同，也是平方级的，但也是非常容易实现的算法。 选择排序

选择排序是这样实现的： 设数组内存放了n个待排数字，数组下标从1开始，到n结束。 i=1 从数组的第i个元素开始到第n个元素，寻找最小的元素。

将上一步找到的最小元素和第i位元素交换。 如果i=n－1算法结束，否则回到第3步 选择排序的平均时间复杂度也是O(n&sup2;)的。 举例：

564 比如说这个，我想让它从小到大排序，怎么做呢？ 第一步：从第一位开始找最小的元素，564中4最小，与第一位交换。结果为465

第二步：从第二位开始找最小的元素，465中5最小，与第二位交换。结果为456 第三步：i=2，n=3，此时i=n-1，算法结束 完成 快速排序

现在开始，我们要接触高效排序算法了。实践证明，快速排序是所有排序算法中最高效的一种。它采用了分治的思想：先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序，这样整个列表就有序了。这是一种先进的思想，也是它高效的原因。因为在排序算法中，算法的高效与否与列表中数字间的比较

次数有直接的关系，而"保证列表的前半部分都小于后半部分"就使得前半部分的任何一个数从此以后都不再跟后半部分的数进行比较了，大大减少了数字间不必要的比较。但查找数据得另当别论了。 堆排序

堆排序与前面的算法都不同，它是这样的： 首先新建一个空列表，作用与插入排序中的"有序列表"相同。

找到数列中最大的数字，将其加在"有序列表"的末尾，并将其从原数列中删除。 重复2号步骤，直至原数列为空。 堆排序的平均时间复杂度为nlogn,效率高（因为有堆这种数据结构以及它奇妙的特征，使得"找到数列中最大的数字"这样的操作只需要O(1)的时间复杂度，维护需要logn的时间复杂度），但是实现相对复杂（可以说是这里7种算法中比较难实现的）。 看起来似乎堆排序与插入排序有些相像，但他们其实是本质不同的算法。至少，他们的时间复杂度差了一个数量级，一个是平方级的，一个是对数级的。

各算法的时间复杂度

平均时间复杂度 插入排序 O(n2) 冒泡排序 O(n2) 选择排序 O(n2) 快速排序 O(n log n) 堆排序 O(n log n) 归并排序 O(n log n) 基数排序 O(n) 希尔排序 O(n1.25)

编辑本段排序算法源代码及复杂度分析 一、简单排序算法

由于程序比较简单，所以没有加什么注释。所有的程序都给出了完整的运行代码，并在我的VC环境

下运行通过。因为没有涉及MFC和WINDOWS的内容，所以在BORLAND C++的平台上应该也不会有什么

问题的。在代码的后面给出了运行过程示意，希望对理解有帮助。 1.冒泡法：

这是最原始，也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡： #include <iostream> using namespace std; void BubbleSort(int * pData, int Count) { int iTemp; for

(int i=0; i<Count; i++) { for (int j=Count-1; j>i; j--) { if

(pData[j]<pData[j-1]) { iTemp = pData[j-1]; pData[j-1] = pData[j];

pData[j] = iTemp; } } } } void main() { int data[7] = {10,9,8,7,6,5,4}; BubbleSort(data,7); for (int i=0; i<7; i++) {

cout<<data[i]<<"

";

}

cout<<endl; system("PAUSE"); } 倒序(最糟情况)

第一轮：10，9，8，7->10，9，7，8->10，7，9，8->7，10，9，8(交换3次)

第二轮：7，10，9，8->7，10，8，9->7，8，10，9(交换2次) 第一轮：7，8，10，9->7，8，9，10(交换1次)

循环次数：6次 交换次数：6次

其他： 第一轮：8，10，7，9->8，10，7，9->8，7，10，9->7，8，10，9(交换2次)

第二轮：7，8，10，9->7，8，10，9->7，8，10，9(交换0次)

第一轮：7，8，10，9->7，8，9，10(交换1次)

循环次数：6次 交换次数：3次 上面我们给出了程序段，现在我们分析它：这里，影响我们算法性能的主要部分是循环和交换，

显然，次数越多，性能就越差。从上面的程序我们可以看出循环的次数是固定的，为1+2+...+n-1。 写成公式就是1/2*(n-1)*n。 现在注意，我们给出O方法的定义： 若存在一常量K和起点n0，使当n>=n0时，有f(n)<=K*g(n)，则f(n) =

O(g(n))。（呵呵，不要说没学好数学呀，对于编程数学是非常重要的！！！）

现在我们来看1/2*(n-1)*n，当K=1/2，n0=1，g(n)=n*n时，1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以f(n)

=O(g(n))=O(n*n)。所以我们程序循环的复杂度为O(n*n)。 再看交换。从程序后面所跟的表可以看到，两种情况的循环相同，交换不同。其实交换本身同数据源的

有序程度有极大的关系，当数据处于倒序的情况时，交换次数同循环一样（每次循环判断都会交换），

复杂度为O(n*n)。当数据为正序，将不会有交换。复杂度为O(0)。乱序时处于中间状态。正是由于这样的 原因，我们通常都是通过循环次数来对比算法。 2.交换法：

交换法的程序最清晰简单，每次用当前的元素一一的同其后的元素比较并交换。 #include <iostream.h> void ExchangeSort(int* pData，int Count) { int iTemp; for(int i=0;i<Count-1;i++)

{ //共（count-1)轮，每轮得到一个最小值 for(int j=i+1;j<Count;j++) {

//每次从剩下的数字中寻找最小值，于当前最小值相比，如果小则交换 if(pData[j]9，10，8，7->8，10，9，7->7，10，9，8(交换3次)

第二轮：7，10，9，8->7，9，10，8->7，8，10，9(交换2次) 第一轮：7，8，10，9->7，8，9，10(交换1次)

循环次数：6次 交换次数：6次 其他： 第一轮：8，10，7，9->8，10，7，9->7，10，8，9->7，10，8，9(交换1次) 第二轮：7，10，8，9->7，8，10，9->7，8，10，9(交换1次) 第一轮：7，8，10，9->7，8，9，10(交换1次)

循环次数：6次 交换次数：3次 从运行的表格来看，交换几乎和冒泡一样糟。事实确实如此。循环次数和冒泡一样 也是1/2*(n-1)*n，所以算法的复杂度仍然是O(n*n)。由于我们无法给出所有的情况，所以

只能直接告诉大家他们在交换上面也是一样的糟糕（在某些情况下稍好，在某些情况下稍差）。 3.选择法：

现在我们终于可以看到一点希望：选择法，这种方法提高了一点性能（某些情况下）

这种方法类似我们人为的排序习惯：从数据中选择最小的同第一个值交换，在从省下的部分中 选择最小的与第二个交换，这样往复下去。 #include <iostream.h>

void SelectSort(int* pData，int Count) { int iTemp; int

iPos; for(int i=0;i<Count-1;i++) { iTemp = pData; iPos = i; for(int j=i+1;j<Count;j++)

{

if(pData[j]<iTemp)

{ iTemp = pData[j]; iPos = j;

} } pData[iPos] = pData; pData = iTemp; } } void main() { int

data[] = {10，9，8，7，6，5，4}; SelectSort(data，7); for (int i=0;i<7;i++)

cout<<data<<" "; cout<<"\n"; } 倒序(最糟情况) 第一轮：10，9，8，7->(iTemp=9)10，9，8，7->(iTemp=8)10，9，8，7->(iTemp=7)7，9，8，10(交换1次)

第二轮：7，9，8，10->7，9，8，10(iTemp=8)->(iTemp=8)7，8，9，10(交换1次)

第一轮：7，8，9，10->(iTemp=9)7，8，9，10(交换0次) 循环次数：6次 交换次数：2次 其他：

第一轮：8，10，7，9->(iTemp=8)8，10，7，9->(iTemp=7)8，10，7，9->(iTemp=7)7，10，8，9(交换1次)

第二轮：7，10，8，9->(iTemp=8)7，10，8，9->(iTemp=8)7，8，10，9(交换1次)

第一轮：7，8，10，9->(iTemp=9)7，8，9，10(交换1次) 循环次数：6次 交换次数：3次

遗憾的是算法需要的循环次数依然是1/2*(n-1)*n。所以算法复杂度为O(n*n)。

我们来看他的交换。由于每次外层循环只产生一次交换（只有一个最小值）。所以f(n)<=n

所以我们有f(n)=O(n)。所以，在数据较乱的时候，可以减少一定的交换次数。 4.插入法：

插入法较为复杂，它的基本工作原理是抽出牌，在前面的牌中寻找相应的位置插入，然后继续下一张 #include <iostream.h> void InsertSort(int* pData，int Count) { int iTemp; int iPos;

for(int

i=1;i<Count;i++) { iTemp = pData[i]; //保存要插入的数 iPos = i-1; //被插入的数组数字个数

while((iPos>=0) && (iTemp9，10，8，7(交换1次)(循环1次)

第二轮：9，10，8，7->8，9，10，7(交换1次)(循环2次) 第一轮：8，9，10，7->7，8，9，10(交换1次)(循环3次)

循环次数：6次 交换次数：3次 其他： 第一轮：8，10，7，9->8，10，7，9(交换0次)(循环1次)

第二轮：8，10，7，9->7，8，10，9(交换1次)(循环2次) 第一轮：7，8，10，9->7，8，9，10(交换1次)(循环1次) 循环次数：4次 交换次数：2次 上面结尾的行为分析事实上造成了一种假象，让我们认为这种算法是简单算法中最好的，其实不是，

因为其循环次数虽然并不固定，我们仍可以使用O方法。从上面的结果可以看出，循环的次数f(n)<=

1/2*n*(n-1)<=1/2*n*n。所以其复杂度仍为O(n*n)（这里说明一下，其实如果不是为了展示这些简单 排序的不同，交换次数仍然可以这样推导）。现在看交换，从

外观上看，交换次数是O(n)（推导类似

选择法），但我们每次要进行与内层循环相同次数的‘=’操作。

正常的一次交换我们需要三次‘=’ 而这里显然多了一些，所以我们浪费了时间。

最终，我个人认为，在简单排序算法中，选择法是最好的。 二、高级排序算法

高级排序算法中我们将只介绍这一种，同时也是目前我所知道（我看过的资料中）的最快的。

它的工作看起来仍然象一个二叉树。首先我们选择一个中间值middle程序中我们使用数组中间值，然后

把比它小的放在左边，大的放在右边（具体的实现是从两边找，找到一对后交换）。然后对两边分别使 用这个过程（最容易的方法——递归）。 1.快速排序： 来回震荡的方式。

写这段代码的作者认为这样可以在冒泡的基础上减少一些交换（我不这么认为，也许我错了）。 反正我认为这是一段有趣的代码，值得一看。 #include

<iostream.h> void Bubble2Sort(int* pData，int Count) { int iTemp; int

left = 1; int right =Count -1; int t; do { //正向的部分 for(int

i=right;i>=left;i--) { if(pData void ShellSort(int* pData，int Count) {

int step[4]; step[0] = 9; step[1] = 5; step[2] = 3; #include <iostream.h> void run(int* pData，int left，int right) step[3] = 1; int

{ int i，j;

int middle，iTemp; i = left; j = right; middle = pData[left]; do{ while((pData[i]<middle) && (i<right))//从左扫描大于中值的数 i++;

while((pData[j]>middle) && (j>left))//从右扫描大于中值的数 j--; if(i<=j)//找到了一对值 { //交换 iTemp = pData[i]; pData[i] = pData[j]; pData[j] = iTemp; i++;

j--; } }while(i<=j);//如果两边扫描的下标交错，就停止（完成一次） //当左边部分有值(left<j)，递归左半边 if(left<j) run(pData，left，j); //当右边部分有值(right>i)，递归右半边 if(right>i)

run(pData，i，right); } void QuickSort(int* pData，int Count) {

run(pData，0，Count-1); } void main() { int data[] = {10，9，8，7，6，5，4};

QuickSort(data，7); for (int i=0;i<7;i++) cout<<data<<" "; cout<<"\n";

} 这里我没有给出行为的分析，因为这个很简单，我们直接来分析算法：首先我们考虑最理想的情况

1.数组的大小是2的幂，这样分下去始终可以被2整除。假设为2的k次方，即k=log2(n)。 2.每次我们选择的值刚好是中间值，这样，数组才可以被等分。

第一层递归，循环n次，第二层循环2*(n/2)...... 所以共有n+2(n/2)+4(n/4)+...+n*(n/n) =

n+n+n+...+n=k*n=log2(n)*n 所以算法复杂度为O(log2(n)*n) 其他的情况只会比这种情况差，最差的情况是每次选择到的middle都是最小值或最大值，那么他将变

成交换法（由于使用了递归，情况更糟）。但是你认为这种情况发生的几率有多大？？呵呵，你完全 不必担心这个问题。实践证明，大多数的情况，快速排序总是最好的。

如果你担心这个问题，你可以使用堆排序，这是一种稳定的O(log2(n)*n)算法，但是通常情况下速度要慢 于快速排序（因为要重组堆）。 三、其他排序 1.双向冒泡：

通常的冒泡是单向的，而这里是双向的，也就是说还要进行反向的工作。 代码看起来复杂，仔细理一下就明白了，是一个

iTemp; int k，s，w; for(int i=0;i<4;i++) { k = step; s = -k; for(int

j=k;j<Count;j++) { iTemp = pData[j]; w = j-k;//求上step个元素的下标 if(s ==0) { s = -k; s++; pData[s] = iTemp; } while((iTemp=0) && (w<=Count)) { pData[w+k] = pData[w]; w = w-k; } pData[w+k] = iTemp; } } }

void main() { int data[] = {10，9，8，7，6，5，4，3，2，1，-10，-1};

ShellSort(data，12);

for

(int

i=0;i<12;i++)

cout<<data<<" "; cout<<"\n";

} 呵呵，程序看起来有些头疼。不过也不是很难，把s==0的块去掉就轻松多了，这里是避免使用0 步长造成程序异常而写的代码。这个代码我认为很值得一看。

这个算法的得名是因为其发明者的名字D.L.SHELL。依照参考资料上的说法：“由于复杂的数学原因

避免使用2的幂次步长，它能降低算法效率。”另外算法的复杂度为n的1.2次幂。同样因为非常复杂并