数据结构Word文档格式.docx
《数据结构Word文档格式.docx》由会员分享，可在线阅读，更多相关《数据结构Word文档格式.docx（24页珍藏版）》请在冰点文库上搜索。
r[j].key）保证的。
⑤
程序：
1.void
InsSort（RecordType
r[],
int
length）
2.{
3.
for（i
=
2;
I
<
length;
i++）
4.
{
5.
r[0]
r[i];
6.
j
i
–
1;
7.
while（r[0].key
r[j].key）
8.
9.
r[j
+
1]
r[j];
10.
}
11.
r[j+1]
r[0];
12.
13.}
折半插入排序：
因为是已经确定了前部分是有序序列，所以在查找插入位置的时候可以用折半查找的方法进行查找，提高效率。
比较时的时间减为O（n㏒n），但是移动元素的时间耗费未变，所以总是得时间复杂度还是O（n²
BinSort（RecordType
x
low
high
while（low
high）
mid
（low
/
if（x.key
r[mid].key）
else
13.
14.
15.
for（j
>
low;
--j）
16.
17.
r[low]
x;
18.
19.}
希尔排序：
又称缩小增量排序法。
把待排序序列分成若干较小的子序列，然后逐个使用直接插入排序法排序，最后再对一个较为有序的序列进行一次排序，主要是为了减少移动的次数，提高效率。
原理应该就是从无序到渐渐有序，要比直接从无序到有序移动的次数会少一些。
O（n的1.5次方）
O
（1）
不稳定排序。
{2,4,1,2}，2和1一组4和2一组，进行希尔排序，第一个2和最后一个2会发生位置上的变化。
ShellInsert（RecordType
length,
delta）
1
delta;
i++）/*1+delta为第一个子序列的第二个元素的下表*/
if（r[i].key
r[1
-
delta].key）
0
&
r[0].key
r[j].key;
-=delta）
delta]
11.}
12.void
ShellSort（RecordType
delta[],
n）
13.{
0;
n
++i）
ShellInsert（r,
delta[i]）;
16.}
三、交换类排序：
通过交换逆序元素进行排序的方法。
冒泡排序：
反复扫描待排序序列，在扫描的过程中顺次比较相邻的两个元素的大小，若逆序就交换位置。
第一趟，从第一个数据开始，比较相邻的两个数据，（以升序为例）如果大就交换，得到一个最大数据在末尾；
然后进行第二趟，只扫描前n-1个元素，得到次大的放在倒数第二位。
以此类推，最后得到升序序列。
如果在扫描过程中，发现没有交换，说明已经排好序列，直接终止扫描。
所以最多进行n-1趟扫描。
BubbleSort（RecordType
change
TRUE;
change;
FALSE;
I;
++j）
if（r[j].key
1].key）
r[j]
1];
17.}
快速排序：
冒泡排序一次只能消除一个逆序，为了能一次消除多个逆序，采用快速排序。
以一个关键字为轴，从左从右依次与其进行对比，然后交换，第一趟结束后，可以把序列分为两个子序列，然后再分段进行快速排序，达到高效。
平均T（n）=O（n㏒n），最坏O（n²
S（n）=O（㏒n）。
{3，2，2}
QKSort（RecordType
low,
pos;
if（low
pos
QKPass（r,
high）;
QKSort（r,
1）;
1,
10.}
11.int
QKPass（RecordType
left,
right）
12.{
RecordType
high;
r[left];
left;
right;
19.
20.
r[high].key
x.key）
21.
high--;
22.
23.
24.
r[high];
25.
low++;
26.
27.
r[low].key
28.
29.
30.
31.
r[high]
r[low];
32.
33.
34.
35.
36.
return
37.}
四、选择类排序：
每一趟在n–i+1（i=1,2,…,n-1）个记录中选取关键字最小的记录作为有序序列中的第i个记录。
简单选择排序：
第一趟时，从第一个记录开始，通过n–1次关键字的比较，从n个记录中选出关键字最小的记录，并和第一个记录进行交换。
第二趟从第二个记录开始，选择最小的和第二个记录交换。
以此类推，直至全部排序完毕。
不稳定排序，{3，3，2}。
SelectSort（RecordType
k
i;
n;
r[k],key）
j;
if（k
!
i）
r[i]
r[k];
r[k]
树形选择排序：
为了减少比较次数，两两进行比较，得出的较小的值再两两比较，直至得出最小的输出，然后在原来位置上置为∞，再进行比较。
直至所有都输出。
T（n）=O（n㏒n）。
较简单选择排序，增加了n-1个额外的存储空间存放中间比较结果，就是树形结构的所有根节点。
S（n）=O（n）。
堆排序：
把待排序记录的关键字存放在数组r[1…n]中，将r看成是一刻完全二叉树的顺序表示，每个节点表示一个记录，第一个记录r[1]作为二叉树的根，一下个记录r[2…n]依次逐层从左到右顺序排列，任意节点r[i]的左孩子是r[2i]，右孩子是r[2i+1]，双亲是r[i/2向下取整]。
然后对这棵完全二叉树进行调整建堆。
{5，5，3}
（1）
调整堆：
sift（RecordType
k,
m）
/*假设r[k...m]是以r[k]为根的完全二叉树，而且分别以r[2k]和r[2k+1]为根的左右子树为大根堆，调整r[k]，使整个序列r[k...m]满足堆的性质*/
t
/*暂存“根”记录r[k]*/
r[k].key;
k;
2
*
finished
while（j
m
finished）
if（j
r[j].key
/*若存在右子树，且右子树根的关键字大，则沿右分支“筛选”*/
if（x
/*筛选完毕*/
}/*继续筛选*/
t;
/*将r[k]填入到恰当的位置*/
23.}
（2）
建初堆：
crt_heap（recordType
--i）/*自第n/2向下取整
个记录开始进行筛选建堆*/
sift（r,
i,
n）;
6.}
（3）
HeapSort（RecordType
crt_heap（r,
length）;
--i）
b
r[1];
/*将堆顶记录和堆中的最后一个记录互换*/
r[1]
b;
/*进行调整，使r[1…i-1]变成堆*/
12.}
五、归并排序：
归并排序：
假设初始序列右n个记录，首先将这n个记录看成n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2向上取整个长度为2（n为奇数时，最后一个序列的长度为1）的有序子序列。
在此基础上，在对长度为2的有序子序列进行两两归并，得到若干个长度为4的有序子序列。
如此重复，直至得到一个长度为n的有序序列为止。
Merge（RecordType
r1[],
mid,
high,
r2[]）
/*已知r1[low...mid]和r1[mid
1...high]分别按关键字有序排列，将它们合并成一个有序序列，存放在r2[low...high]*/
while（（i
mid）
（j
high））
if（r1[i].key
r1[j].key）
r2[k]
r1[i];
++i;
r1[j];
++j;
++k;
while（i
k++;
i++;
j++;
33.}
34.void
MSort（RecordType
r3[]）
35.{
/*r1[low...high]经过排序后放在r3[low...high]中，r2[low...high]为辅助空间*/
37.
r2[N];
38.
==
39.
r3[low]
r1[low];
40.
41.
42.
43.
MSort（r1,
r2）;
44.
45.
Merge（r2,
r3）;
46.
47.}
48.void
MergeSort（RecordType
49.{
50.
/*对记录数组r[1...n]做归并排序*/
51.
MSort（r,
n,
r）;
52.}
六、分配类排序：
分配类排序是利用分配和收集两种基本操作。
多关键字排序：
链式基数排序：
先分配，再收集，就是先按照一个次关键字收集一下，然后进行收集（第一个排序），然后再换一个关键字把新序列分配一下，然后再收集起来，又完成一次排序，这样所有关键字分配收集完后，就完成了排序。
T（n）=O（d（n+rd））。
S（n）=O（rd）。
七、总结：
（1）简单排序法一般只用于n较小的情况（例如n<
30）。
当序列的记录“基本有序”时，直接插入排序是最佳的排序方法。
如果记录中的数据较多，则应采用移动次数较少的简单选择排序法。
（2）快速排序、堆排序和归并排序的平均时间复杂度均为O（n㏒n），但实验结果表明，就平均时间性能而言，快速排序是所有排序方法中最好的。
遗憾的是，快速排序在最坏情况下的时间性能为O（n²
堆排序和归并排序的最坏时间复杂度仍为O（n㏒n），当n较大时，归并排序的时间性能优于堆排序，但它所需的辅助空间最多。
（3）可以将简单排序法与性能较好的排序方法结合使用。
例如，在快速排序中，当划分子区间的长度小于某值时，可以转而调用直接插入排序法；
或者先将待排序序列划分成若干子序列，分别进行直接插入排序，然后再利用归并排序法，将有序子序列合并成一个完整的有序序列。
（4）基数排序的时间复杂度可以写成O（d·
n）。
因此，它最适合于n值很大而关键字的位数d较小的序列。
当d远小于n时，其时间复杂度接近O（n）。
（5）从排序的稳定性上来看，在所有简单排序法中，简单选择排序是不稳定的，其他各种简单排序法都是稳定的。
然而，在那些时间性能较好的排序方法中，希尔排序、快速排序、堆排序都是不稳定的，只有归并排序、基数排序是稳定的。
文章二
数据结构中各种排序算法比较
1快速排序（QuickSort）
快速排序是一个就地排序，分而治之，大规模递归的算法。
从本质上来说，它是归并排序的就地版本。
快速排序可以由下面四步组成。
如果不多于1个数据，直接返回。
一般选择序列最左边的值作为支点数据。
将序列分成2部分，一部分都大于支点数据，另外一部分都小于支点数据。
（4）
对两边利用递归排序数列。
快速排序比大部分排序算法都要快。
尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。
快速排序是递归的，对于内存非常有限的机器来说，它不是一个好的选择。
2归并排序（MergeSort）
归并排序先分解要排序的序列，从1分成2，2分成4，依次分解，当分解到只有1个一组的时候，就可以排序这些分组，然后依次合并回原来的序列中，这样就可以排序所有数据。
合并排序比堆排序稍微快一点，但是需要比堆排序多一倍的
升级会员 