c语言几种排序算法Word文件下载.docx
《c语言几种排序算法Word文件下载.docx》由会员分享，可在线阅读，更多相关《c语言几种排序算法Word文件下载.docx（17页珍藏版）》请在冰点文库上搜索。
11iTemp=pData[j-1];
12pData[j-1]=pData[j];
13pData[j]=iTemp;
14}
15}
16}
17}
18voidmain（）
19{
20intdata[]={10,9,8,7,6,5,4};
21BubbleSort（data,7）;
22for（inti=0;
7;
23cout<
<
data[i]<
"
"
;
24cout<
\n"
25}
倒序（最糟情况）
第一轮：
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次
交换次数：
其他：
8,10,7,9->
8,7,10,9->
7,8,10,9（交换0次）
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、选择排序
在要排序的一组数中，选出最小的一个数与第一个位置的数交换；
然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。
选择排序是不稳定的。
算法复杂度O（n2）--[n的平方]
26＃include<
27voidSelectSort（int*pData,intCount）
28{
29intiTemp;
30intiPos;
31for（inti=0;
Count-1;
32{
33iTemp=pData[i];
34iPos=i;
35for（intj=i+1;
j<
j++）
36{
37if（pData[j]<
iTemp）
38{
39iTemp=pData[j];
40iPos=j;
41}
42}
43pData[iPos]=pData[i];
44pData[i]=iTemp;
45}
46}
47voidmain（）
48{
49intdata[]={10,9,8,7,6,5,4};
50SelectSort（data,7）;
51for（inti=0;
52cout<
53cout<
54}
（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次）
2次
（iTemp=8）8,10,7,9->
（iTemp=7）8,10,7,9->
（iTemp=7）7,10,8,9（交换1次）
（iTemp=8）7,10,8,9->
（iTemp=8）7,8,10,9（交换1次）
（iTemp=9）7,8,9,10（交换1次）
遗憾的是算法需要的循环次数依然是1/2*（n-1）*n。
所以算法复杂度为O（n*n）。
我们来看他的交换。
由于每次外层循环只产生一次交换（只有一个最小值）。
所以f（n）<
=n所以我们有f（n）=O（n）。
所以，在数据较乱的时候，可以减少一定的交换次数。
3、直接插入排序
在要排序的一组数中，假设前面（n-1）[n>
=2]个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。
如此反复循环，直到全部排好顺序。
直接插入排序是稳定的。
55#include<
56voidSelectSort（int*pData,intCount）
57{
58intiTemp;
59intiPos;
60for（inti=0;
61{
62iTemp=pData[i];
63iPos=i;
64for（intj=i+1;
65{
66if（pData[j]<
67{
68iTemp=pData[j];
69iPos=j;
70}
71}
72pData[iPos]=pData[i];
73pData[i]=iTemp;
74}
75}
76voidmain（）
77{
78intdata[]={10,9,8,7,6,5,4};
79SelectSort（data,7）;
80for（inti=0;
81cout<
82cout<
83}
9,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次）
3次
8,10,7,9（交换0次）（循环1次）
7,8,10,9（交换1次）（循环2次）
7,8,9,10（交换1次）（循环1次）
4次
上面结尾的行为分析事实上造成了一种假象，让我们认为这种算法是简单算法中最好的，其实不是，因为其循环次数虽然并不固定，我们仍可以使用O方法。
从上面的结果可以看出，循环的次数f（n）<
=1/2*n*（n-1）<
=1/2*n*n。
所以其复杂度仍为O（n*n）（这里说明一下，其实如果不是为了展示这些简单排序的不同，交换次数仍然可以这样推导）。
现在看交换，从外观上看，交换次数是O（n）（推导类似选择法），但我们每次要进行与内层循环相同次数的‘=’操作。
正常的一次交换我们需要三次‘=’而这里显然多了一些，所以我们浪费了时间。
个人认为在简单排序算法中，选择法是最好的。
4、希尔排序
在直接插入排序算法中，每次插入一个数，使有序序列只增加1个节点，并且对插入下一个数没有提供任何帮助。
如果比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除
多个元素交换。
D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。
算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。
当增量减到1时，整个要排序的数被分成
一组，排序完成。
下面的函数是一个希尔排序算法的一个实现，初次取序列的一半为增量，以后每次减半，直到增量为1。
希尔排序是不稳定的。
=====================================================
这个排序非常复杂，看了程序就知道了。
首先需要一个递减的步长，这里我们使用的是9、5、3、1（最后的步长必须是1）。
工作原理是首先对相隔9-1个元素的所有内容排序，然后再使用同样的方法对相隔5-1个元素的排序，以次类推。
84＃include<
85voidShellSort（int*pData,intCount）
86{
87intstep[4];
88step[0]=9;
89step[1]=5;
90step[2]=3;
91step[3]=1;
92inti,Temp;
93intk,s,w;
94for（inti=0;
4;
95{
96k=step[i];
97s=-k;
98for（intj=k;
99{
100iTemp=pData[j];
101w=j-k;
//求上step个元素的下标
102if（s==0）
103{
104s=-k;
105s++;
106pData[s]=iTemp;
107}
108while（（iTemp<
pData[w]）&
&
（w>
=0）&
（w<
=Count））
109{
110pData[w+k]=pData[w];
111w=w-k;
112}
113pData[w+k]=iTemp;
114}
115}
116}
117voidmain（）
118{
119intdata[]={10,9,8,7,6,5,4,3,2,1,-10,-1};
120ShellSort（data,12）;
121for（inti=0;
12;
122cout<
123cout<
124}
呵呵，程序看起来有些头疼。
不过也不是很难，把s==0的块去掉就轻松多了，这里是避免使用0步长造成程序异常而写的代码。
这个代码我认为很值得一看。
这个算法的得名是因为其发明者的名字D.L.SHELL。
依照参考资料上的说法：
“由于复杂的数学原因避免使用2的幂次步长，它能降低算法效率。
”另外算法的复杂度为n的1.2次幂。
同样因为非常复杂并“我也不知道过程"
，我们只有结果了。
5、快速排序
快速排序是对冒泡排序的一种本质改进。
它的基本思想是通过一趟扫描后，使得排序序列的长度能大幅度地减少。
在冒泡排序中，一次扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1。
快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）的左边各数都比它小，右边各数都比它大。
然后又用同样的方法处理它左右两边的数，直到基准点的左右只有一个元素为止。
它是由C.A.R.Hoare于1962年提出的。
显然快速排序可以用递归实现，当然也可以用栈化解递归实现。
下面的函数是用递归实现的，有兴趣的朋友可以改成非递归的。
快速排序是不稳定的。
最理想情况算法时间复杂度O（nlog2n），最坏O（n2）
125＃include<
126voidrun（int*pData,intleft,intright）
127{
128inti,j;
129intmiddle,iTemp;
130i=left;
131j=right;
132middle=pData[（left+right）/2];
//求中间值
133do{
134while（（pData[i]<
middle）&
（i<
right））//从左扫描大于中值的数
135i++;
136while（（pData[j]>
（j>
left））//从右扫描大于中值的数
137j--;
138if（i<
=j）//找到了一对值
139{
140//交换
141iTemp=pData[i];
142pData[i]=pData[j];
143pData[j]=iTemp;
144i++;
145j--;
146}
147}while（i<
=j）;
//如果两边扫描的下标交错，就停止（完成一次）
148//当左边部分有值（left<
j），递归左半边
149if（left<
j）
150run（pData,left,j）;
151//当右边部分有值（right>
i），递归右半边
152if（right>
i）
153run（pData,i,right）;
154}
155voidQuickSort（int*pData,intCount）
156{
157run（pData,0,Count-1）;
158}
159voidmain（）
160{
161intdata[]={10,9,8,7,6,5,4};
162QuickSort（data,7）;
163for（inti=0;
164cout<
165cout<
166}
这里我没有给出行为的分析，因为这个很简单，我们直接来分析算法：
首先我们考虑最理想的情况
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）算法，但是通常情况下速度要慢于快速排序（因为要重组堆）。
6、堆排序
堆排序是一种树形选择排序，是对直接选择排序的有效改进。
堆的定义如下：
具有n个元素的序列（h1,h2,...,hn）,当且仅当满足（hi>
=h2i,hi>
=2i+1）或（hi<
=h2i,hi<
=2i+1）（i=1,2,...,n/2）时称之为堆。
在这里只讨论满足前者条件的堆。
由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项。
完全二叉树可以很直观地表示堆的结构。
堆顶为根，其它为左子树、右子树。
初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储顺序，使之成为一个堆，这时堆的根节点的数最大。
然后将根节点与堆的最后一个节点交换。
然后对前面（n-1）个数重新调整使之成为堆。
依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。
从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。
所以堆排序有两个函数组成。
一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。
堆排序是不稳定的。
算法时间复杂度O（nlog2n）。
====================================================
167voidsift（int*x,intn,ints）
168{
169intt,k,j;
170t=*（x+s）;
171k=s;
172j=2*k+1;
173while（j
174{
175if（j
176<
*（x+j+1））*判断是否满足堆的条件：
满足就继续下一轮比较，否则调整。
*&
*（x+j）/>
{
177j++;
178}
179if（t<
*（x+j））
180{
181*（x+k）=*（x+j）;
182k=j;
183j=2*k+1;
184}
185else
186{
187break;
188}
189}
190*（x+k）=t;
191}
192
193
194voidheap_sort（int*x,intn）
195{
196inti,k,t;
197int*p;
198for（i=n/2-1;
i>
=0;
i--）
199{
200sift（x,n,i）;
201}
202for（k=n-1;
k>
=1;
k--）
203{
204t=*（x+0）;
205*（x+0）=*（x+k）;
206*（x+k）=t;
207sift（x,k,0）;
208}
209}
210
211voidmain（）
212{
213#defineMAX4
214int*p,i,a[MAX];
215
216p=a;
217printf（"
Input%dnumberforsorting:
MAX）;
218for（i=0;
i
219{
220scanf（"
%d"
p++）;
221}
222printf（"
）;
223
224p=a;
225select_sort（p,MAX）;
226for（p=a,i=0;
227{
228printf（"
%d"
*p++）;
229}
230printf（"
231system（"
pause"
232}
其他的交换法，双向冒泡法等等就不具体介绍了。
三、几种排序算法的比较和选择
1.选取排序方法需要考虑的因素：
（1）待排序的元素数目n；
（2）元素本身信息量的大小；
（3）关键字的结构及其分布情况；
（4）语言工具的条件，辅助空间的大小等。
四、小结：
（1）若n较小（n<
=50），则可以采用直接插入排序或直接选择排序。
由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。
（2）若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。
升级会员 