C语言排序方法之内部排序.

1、2 内部排序 1、 概述 2、 插入排序 3、 交换排序 4、 选择排序 5、 归并排序 6、 基数排序 h概述 排序的分类： 内部排序：全部记录都可以同时调入内存进行的排序。 外部排序：文件中的记录太多，无法全部将其同时调入内 存进行的排序。 定义：设有记录序列： Rl R2 . Rn 其相应的关键字序列为：Ki. K2 . Kn ； 若存在一种确定的关系：Kx = Ky = . = Kz 则将记录序列Rl、R2 . Rr 排成按该关键字有序的 序列 Rx、Ry . Rz 的操作，称之为排序。 关系是任意的，如通常使用的小于、大于等关系。 稳定与不稳定：若记录序列中的任意两个记录Rx、Ry的

2、关键 字 Kx = Ky ; 如果在排序之前和排序之后， 它们的相对位置保持不变, 则这种排序方法是稳定的，否则是不稳定的。 3 # define MAXSIZE 20 typedef int KeyType； typedef struct KeyType key; InfoType otherinfo; RedType; typedef struct RedType r MAXSIZE + 1 ; / r0空或作哨兵 int len gth; SqList;6 2、插入排序 直接插入排序 例：36、24、10、6、12 存放在 r 数组的下标为 1 至 5 的 元素之中，川直接插入法将其排序

3、。结果仍保存在下标为 1 至 5 的元素之中。 0 1 2 3 4 5 36 24 10 6 12 r0用作哨兵。共执行5遍操作。 每遍操作：先将元素复制内容放入r0,再将本元素同已排序的序列，从尾 开始进行比较。在已排序的序列中寻找自己的位置，进行插入。或者寻找 不到，则一直进行到哨兵为止。意味着本元素最小，应该放在r1 o 每一遍，排序的序列将增加一个元素。如果序列中有n个元素，那么最多 进行n遍即可。 0 1 2 3 4 5 36 24 10 6 12 i 24 36 24 0 12 3 4 8 36 24 10 6 12 i 24 36 0 12 3 4 36 24 10 6 12 i

4、 24 24 36 0 12 3 4 10 36 24 10 6 12 j 10 24 36 10 0 12 3 4 36 24 10 6 12 10 24 36 0 1 36 24 10 6 12 j 10 24 36 11 0 1 2 3 4 5 36 24 10 6 12 10 10 24 36 0 12 3 4 36 24 10 6 12 I 6 10 24 36 6 13 0 12 3 4 36 24 10 6 12 i 6 10 24 36 0 12 3 4 16 36 24 10 6 12 I 6 10 24 36 15 0 12 3 4 36 24 10 6 12 i 6 10

5、 24 36 0 12 3 4 18 36 24 10 6 12 I 6 6 10 24 36 17 0 12 3 4 36 24 10 6 12 i 12 6 10 24 36 12 0 12 3 4 20 36 24 10 6 12 1 12 6 10 24 36 19 0 12 3 4 36 24 10 6 12 i 12 6 10 24 36 0 22 36 24 10 6 12 r 12 6 10 12 24 36 直接插入排序过程： 整个排序过程为 n-l趟插入，即先将序列中 第1 个记录看成是一个有序子序列，然后从第 2 个记录开始，逐个进行插入，直至整个序列有 序。 算法描述:

6、 直接插入排序 24 void straisort(JD r,int n) int i,j; for(i=2;i=n;i+) rO=ri; j=i-1 ； while(rO .keyrj .key) rU+l=rj; j-； rj+l=rO; 23 0 1 2 3 4 5 6 7 例 i=l (49 38 65 97 76 13 27 i=2 38 (38 49) 65 97 76 13 27 i=3 65 (38 49 I 65) 76 13 27 i=4 97 (38 49 65 97 76 13 27 i=5 76 (38 49 65 76 9 1 27 i=6 13 (13 38 49

7、 65 76 97) i=7 27 ( 3 J 27 38 49 65 76 97 .1 .1 .1 J .1 J J J J J J 排序结果：(13 27 38 49 65 76 9刀 typedef 26 算法评价 时间复杂度 若待排序记录按关键字从小到大排列（正序） 关键字比较次数： 1 = 1 i=2 记录移动次数： H 艺 2 = 2（n 1） i=2 0 12 3 5 6 7 若待排序记录按关键字从大到小排列（逆序） 记录移动次数： 0- +1）=（丝+律（匚） ；=2 乙 1 2 3 4 5 6 7 97 76 65 49 38 27 1313 27 38 49 关键n Z=2

8、 （池 25 28 若待排序记录是随机的，取平均值 关键字比较次数： 兰+ . 4 记录移动次数： 三 4 T(n)=O(n2) 空间复杂度：S(n)=O(l) 27 折半插入排序 排序过程： 用折半査找方法确定插入位置的排序叫C 例 i=l (30) 13 70 85 39 42 6 20 i=2 13 (13 30) 70 85 39 42 6 20 i=7 6 (6 13 30 39 42 70 85) 20 i=8 20 13 30 3? 42 70 掣) 20 s m J i=8 20 q 早 3? J 39 42 70 85) 20 s m i=8 20 (6 13 t3?t s

9、mj 39 42 70 85 ) 20 i=8 20 (6 早 J V s 39 42 70 85 ) 20 i=8 20 (6 13 20 30 39 42 70 8530 void binsort(JD r,int n) int i,j,x,s,m,k; for(i=2;iv=n;i+) rO=ri; x=ri.key; s=l; j=i-l; while(s=j) m=(s+j)/2; if(x=s;k) rk+l=rk; 29 算折半插入排序 rsJ=rOJ 32 希尔排序（缩小增量法） 排序过程： 先取一个正整数dln,把所有相隔dl的 记录放一组，组内进行直接插入排序；然后 取 d

10、20)&(x.keyr2.key,则交换；然后 比较第二个记录与第三个记录；依次类推，直至第 个记录和第 n 个记录比较为止第趟冒泡排 序，结果关键字最大的记录被安置在最后一个记录 上 对前个记录进行第二趟冒泡排序，结果使关键 字次大的记录被安置在第 n1 个记录位置 重复上述过程，直到“在-趟排序过程中没有进行 过交换记录的操作”为止 37 1 38 38 38 38 13 13 2 49 49 49 13 27 27 3 65 65 13 27 30 30 4 76 13 27 30 38 38 5 13 27 30 49 49 6 27 30 65 65 7 30 76 76 8

11、 97 97 第 趟 弟 笔 第 四 趟 第 五 趟 例 时间复杂度 最好情况（正序） 比较次数：n-l 移动次数：0 最坏情况（逆序） 比较次数: = l(n2 -n) ;=! 2 移动次数：3 工(刃-,)=(?2 - -n) i=n) i= 2 T(n)=O(n2) 空间复杂度：S(n)=O(l)void bubble_sort(JD r,int n) int m,i,j,flag=l; JD x; m=n-l; while(m0)&(flag= 1) flag=O; for(j= 1 ;jv=m;j+) if(rjJ.keyrj+l.key) Aag=l； x=rj; rj=r

12、fj+l; rj+l=x; 算法描述: 算法评价 冒泡拮序 快速排序 基本思想： 通过一趟排序，将待排序记录分割成独 立的两部分，其中一部分记录的关键字均比 另一部分记录的关键字小，则可分别对这两 部分记录进行排序，以达到整个序列有序。 41 須E序过程：对rs . t中记录进行一 趟快速排序,附设两个扌旨针i和j,设枢轴记 录rp=rs, x=rp.key 初始时令i=s,j=t 首先从j所指位置向 前搜索 第一个关键 字小于x的记录，并和rp交换 再从i所指位置起向后扌叟索，找到第一 个关键字大于x的记录，和rp交换 重复上述两步，直至i=j为止 再分另u对两个子序歹u进彳亍，决速羽E序，

13、 直到每个子序列只含有一个记录为止44 void qksort(JD r,int t,int w) int i,j,k; JD x; if(t=w) return; i=t; j=w; x=ri; while(ij) while(i=x.key) j; ri=rUJ; i+; while(ij)&(ri.key=x.key) i+; if(ij) rj=ri; j-; X 11 27 38 13 49 t t t 1 1 1 咐 (27 38 13) 49 (13) 27 (38) 49 13 27 38 49 76 97 65 50 t T t t J J J J (76 97 65

14、 50) (50 65) (97) 50 65 76 97 - ri=x； 初始关键字: 完46 例 1J 初始关键字： x. key=49 27 38 13 49 76 97 65 50 t t t t J T t t 1 1 1 J J j 完成一趟排序： (27 38 13) 49 (76 97 65 50) 算法描述:圜 快速排序 算法评价 T(n)=O(nlog2n) 最坏情况(每次总是选到最小或最大元素 作枢轴)T(n)=O(n2) T(n)=O(n2) 空间复杂度：需栈空间以实现递归 最坏情况：S(n)=O(n) 一般情况：S(n)=O(Iog2n)时间(每次总是选到中问值作枢轴

15、) 48 课外学习 看书P263277 题集 10.1 (1 ) (2) (3) 补充题： 1. 写出希尔排序的算法 2. 写出快速排序的算法 47 4、选择排序(Selection Sort) 简单选择排序(Simple Selection Sort) 排序过程 首先通过n-1次关键字比较， 从n个 记录中找出关键字最小的记录，将 它与第一个记录交换； 再通过m2次比较，从剩余的n-1个 记录中找出关键字次小的记录，将 它与第二个记录交换； 重复上述操作，共进行n-1趟排序 后，排序结束。50 例i=l 初始： 13 38 t i 65 t J 97 t J 76 t j 49 27 1 J T J k 1 i=2 趟： 13 27 65 97 76 49 38 t t t t 1 j j j j j 二趟： 13 27 65 97 76 49 38 算法描述 void smp_sclcsort(JD rJ Jnt