第8章 排序 北京师范大学 教育技术学院 杨开城.

Presentation on theme: "第8章 排序 北京师范大学 教育技术学院 杨开城."— Presentation transcript:

1 第8章 排序 北京师范大学 教育技术学院 杨开城

2 一、基本概念 排序：指将一组数据元素按照一个或多个关键字排列成有序序列的过程。
排序的稳定性：如果任意两个关键字相同的数据元素Ei和Ej，在排序前后相对位置不变(比如Ei在排序之前和之后都位于Ej的前面)，那么称这种排序是稳定的，否则称这种排序是不稳定的。 内排序：待排序的序列在排序过程中全部都存放在内存中。 外排序：待排序序列在排序过程中需要访问外存储器(比如文件)。

3 二、内排序——插入排序(1) ⑴直接插入排序 void insort(elemtype r[ ],int n)
{/*对表长是n的顺序表r进行升序排序*/ int i,j; elemtype tmp; for(i=1;i<n;i++)/*i从1开始，r[0]自身是有序子序列*/ { /*将r[i]有序插入r[0..i-1]中，使得r[0..i]有序*/ tmp=r[i];/*将r[i]暂时保存在tmp中，为数据元素的移动准备空间*/ j=i-1; while(j>=0&&r[j]>tmp) {/*自右向左扫描有序子序列，如果数据元素比tmp大，就向右移动一个单元*/ r[j+1]=r[j]; j--; } r[j+1]=tmp; /*tmp的正确为止是j+1*/ 最好时间复杂度 最坏时间复杂度

4 二、内排序——插入排序(2) ⑵二路插入排序 void binsort(elemtype r[ ],int n)
{ int first,last; int i,j,k; elemtype *a; a=(elemtype*)malloc(n*sizeof(elemtype));/*分配存放有序子序列的数组a*/ if(a==NULL)return; a[0]=r[0];/*以r[0]为界，将r[0]复制到a[0]*/ first=last=0;/*初始化首单元和尾单元指针*/

5 二、内排序——插入排序(3) for(k=1;k<n;k++) /*依次将r[k]插入到a中的有序子序列中*/
{ if(r[k]>=a[0]) /*将r[k]插入到a[0]的右边*/ { i=last; while(i>=0&&a[i]>r[k]) { a[i+1]=a[i]; i--; } a[i+1]=r[k]; last++; } else /*将r[k]插入到a[0]的左边，即从数组末尾向左插*/ { first--; if(first==-1)first=n-1; i=first+1; while(i<n&&a[i]<=r[k])/*为了使排序是稳定的，此处使用<=*/ { a[i-1]=a[i]; i++; } a[i-1]=r[k]; } }/*属于for语句*/

6 二、内排序——插入排序(4) i=first;/*将有序序列从a复制到r中*/ k=0; while(k<n) {
r[k]=a[i]; k++; i=(i+1)%n; } free(a); 最好时间复杂度 最坏时间复杂度

7 二、内排序——插入排序(5) ⑶希尔排序

8 二、内排序——插入排序(6) void ShellInsert(elemtype r[ ],int n,int dlta)
{ /*对表长为n的顺序表r进行一趟希尔排序*/ int i,j,k; elemtype tmp; /*以dlta为间隔取数据元素为子序列，对子序列进行直接插入排序， 子序列的数量必定是dlta*/ for(i=0;i<dlta;i++) for(j=dlta+i;j<n;j+=dlta) { tmp=r[j]; k=j-dlta; while(k>=0&&r[k]>tmp) { r[k+dlta]=r[k]; k-=dlta; } r[k+dlta]=tmp;

9 二、内排序——插入排序(7) void ShellSort(elemtype r[ ],int n) { int dlta;
dlta=(n+1)/2; /*间隔的初始值*/ while(dlta>1) ShellInsert(r,n,dlta); dlta=(dlta+1)/2; /*间隔值折半*/ } ShellInsert(r,n,1); /*最后一趟希尔排序*/

10 二、内排序——交换排序(1) ⑴起泡排序 void BubbleSort(elemtype r[ ],int n)
{ /*对表长是n的顺序表r进行起泡排序*/ int i,j; elemtype tmp; for(i=1;i<n;i++) { /*一共需要n-1趟起泡*/ for(j=0;j<n-i;j++) /*起泡区间是r[0..n-i]*/ if(r[j]>r[j+1]) /*发现逆序关系，交换数据元素*/ { tmp=r[j]; r[j]=r[j+1]; r[j+1]=tmp; } 时间复杂度：

11 二、内排序——交换排序(2) ⑵起泡排序的改进 ①如果在一趟起泡过程中，没有发生交换操作，就不再需要起泡操作；
②记下最后一次交换操作的位置t，下次起泡区间是r[0..t]而不是r[0..n-i]。 ③用“传送”代替交换。 ④在两个方向上都起泡。 void BubbleSort1(elemtype r[N],int n) { /*改进的起泡排序*/ int low,high,i,j; int t; elemtype tmp; high=n-1; low=0; t=0;/*从左向右方向上，起泡区间初始起点是0，终点是n-1*/

12 二、内排序——交换排序(3) while(high>low) { /*开始从左向右起泡*/
low=t;/*起泡区间被标识为r[low..high]*/ i=low; t=0; /*假定未发生交换*/ while(i<high) { if(r[i]>r[i+1]) /*发现逆序，执行传送操作*/ { tmp=r[i];/*保存r[i]*/ while(i<high&&tmp>r[i+1]) /*将比tmp小的数据元素向左移动*/ { r[i]=r[i+1]; i++; } r[i]=tmp;/*将tmp放到正确的位置上*/ t=i-1;/*如果这是最后一次传送，那么t就是新起泡区间的终点*/ } i++; if(t==0)break;/*未发生交换，r已经有序，跳出*/

13 二、内排序——交换排序(4) /*开始自右向左起泡*/ high=t;/*设定起泡区间的新终点*/ i=high; t=0;
while(i>low) { if(r[i]<r[i-1]) /*发现逆序，执行传送操作*/ { tmp=r[i]; while(i>low&&tmp<r[i-1]) { r[i]=r[i-1]; i--; } r[i]=tmp; t=i+1; /*如果这是最后一次传送，那么t就是新起泡区间的起点*/ i--; if(t==0)break;/*未发生交换操作，r已经有序，跳出*/

14 二、内排序——交换排序(5) ⑶快速排序 【基本思想】以某个数据元素PK（通常是r[0]）为分界，将序列划分为两个子序列，左边的子序列的数据元素都不大于PK，右边的子序列的数据元素都不小于PK。然后对左右子序列进行同样的分割操作，直到子序列长度是1为止。

15 二、内排序——交换排序(6) void Part(elemtype r[ ],int l,int h,int *pivotloc)
{/*将序列r的区间r[l..h]分割成两个子序列，最终的分界点由pivotloc返回*/ int low,high; elemtype pivotkey;/*PK值*/ low=l;high=h;/*初始化high，low*/ pivotkey=r[low];/*保存PK值，PK的初始位置是low*/ while(high!=low) /*未分割完，继续分割循环*/ { while(low<high&&r[high]>=pivotkey) high--;/*high的下行*/ if(low<high) { r[low]=r[high]; /*将r[high]放到PK的左边，PK的位置变为high*/ low++;/*准备low上行*/ } while(low<high&&r[low]<=pivotkey) low++;/*low上行*/ { r[high]=r[low]; /*将r[low]放到PK的右边，PK的位置变为low*/ high--;/*准备high上行*/ } } r[high]=pivotkey;/*high是PK的位置，将PK复制到r[high]*/ *pivotloc=high;/*表明分界点的位置*/

16 二、内排序——交换排序(7) void QuickSort(elemtype r[ ],int l,int h)
{ /*对序列区间r[l..h]进行快速排序。要调用QuickSort对一个表长是n的序列进行排序，可以这样调用：QuickSort(r,0,n-1);*/ int i; if(h>l) {/*如果序列长度大于1*/ Part(r,l,h,&i);/*分割序列，分界点是i*/ /*递归调用快速排序算法，对两个子序列分别进行快速排序*/ QuickSort(r,l,i-1); QuickSort(r,i+1,h); } 最好时间复杂度： 最坏时间复杂度：

17 二、内排序——选择排序(1) ⑴简单选择排序 void SelectSort(elemtype r[ ],int n)
{/*对表长是n的序列r进行直接选择排序*/ int i,j,k; elemtype tmp; for(i=1;i<n;i++) { /*进行n-1次选择*/ k=0; /*先假定最大值是r[0]*/ for(j=k+1;j<=n-i;j++)/*选择区间是r[0..n-i]*/ if(r[j]>r[k]) k=j; /*记录新的最大值的位置*/ if(k!=n-i) {/*如果最大值不是最后一个单元，则与最后一个单元交换*/ tmp=r[n-i]; r[n-i]=r[k]; r[k]=tmp; }

18 二、内排序——选择排序(2) ⑵树形选择排序
树形选择排序,又称锦标赛排序。它的基本思想就是将序列中的相邻元素两两比较，选出较大值，然后将这些两两比较的结果再两两比较，这种重复操作直至选出序列的最大值为止。

19 二、内排序——选择排序(3) ⑶堆排序 一个顺序存储的完全二叉树，如果任何一个结点的值都不小于或不大于它左右子树（如果有的话）中所有结点的值，那么这个顺序存储的序列就是堆。这个二叉树的根被称为堆顶，最后一层最右端的叶子结点称为堆底。 由于堆是一个顺序存储的完全二叉树，所以一个长度是n的序列要成为一个堆，必须存储在容量是n+1的顺序表中，其中0号单元不用。 堆顶r[1]是整个序列的最大值或者最小值。堆顶是最大值的堆被称为大顶堆或者极大堆；堆顶是最小值的堆被称为小顶堆或者极小堆。

20 二、内排序——选择排序(4) 【堆排序的基本思想】 【需要解决的2个问题】
首先将一个序列构建成堆；然后将堆顶与堆底交换，再去掉堆底，剩余的序列可能不是堆，将它再调整成堆，再将堆顶与堆底交换。如此重复直到堆只有一个结点为止。 【需要解决的2个问题】 ②如何将一个替换掉堆顶的堆重新调整成堆？ 一个完全二叉树，根的左右子树都是堆，而整棵二叉树不是堆。问如何将这棵二叉树调整成堆。 ①如何将一个序列建成一个堆？

21 二、内排序——选择排序(5) ②如何将一个替换掉堆顶的堆重新调整成堆？
一个完全二叉树，根的左右子树都是堆，而整棵二叉树不是堆。问如何将这棵二叉树调整成堆。

22 二、内排序——选择排序(6) ①如何将一个序列建成一个堆？

23 二、内排序——选择排序(7) void Adjust(elemtype r[ ],int k,int n)
{/*将表长是n的序列r看成是完全二叉树的顺序存储，将以r[k]为根的子树调整成大顶堆*/ int i,j; elemtype tmp; tmp=r[k]; /*用tmp保存r[k]*/ i=k; while(2*i<=n) /*逐层上浮的相应结点，确定r[k]下沉的终点位置*/ {/*r[i]不是叶子结点，继续循环*/ j=2*i; /*r[j]是r[k]的左孩子，准备上浮左孩子结点*/ if(j+1<=n&&r[j+1]>r[j]) j++;/*右孩子比左孩子大，上浮右孩子结点*/ if(tmp<r[j]) /*上浮结点r[j]*/ { r[i]=r[j]; i=j; /*i可能是r[k]的下沉终点*/ } else break; } r[i]=tmp;/*将r[k]复制到下沉终点的位置上，调整完毕*/

24 二、内排序——选择排序(8) void HeapSort(elemtype r[ ],int n)
{/*对序列r进行堆排序，序列长度是n*/ int i; elemtype tmp; /*自下而上、从右向左依次调整非叶子结点处的子树成为堆， 第一个需要调整的非叶子结点是r[n/2]*/ for(i=n/2;i>=1;i--) Adjust(r,i,n); for(i=n;i>=2;i--) {/*进行n-1次选择，即摘取堆顶，与堆底交换。选择后将剩余部分调整成堆*/ tmp=r[i]; /*r[i]是堆底,r[1]是堆顶，堆底和堆顶交换*/ r[i]=r[1]; r[1]=tmp; Adjust(r,1,i-1);/*将序列r[1..i-1]调整成堆*/ } 时间复杂度：

25 二、内排序——索引排序(1) 索引排序 void indexsort(elemtype r[ ],int n,int index[ ])
{/*index是r的索引表，对索引表进行排序，表长是n*/ int i,j,tmp; for(i=1;i<n;i++) { tmp=index[i]; j=i-1; while(j>=0&&r[index[j]]>r[tmp]) index[j+1]=index[j]; j--; } index[j+1]=tmp;

26 二、内排序——索引排序(2) 索引排序后的物理重排
void arrange(elemtype r[ ],int n,int index[ ]) {/*index是r的有序索引表，r的表长是n，对r按照索引进行物理重排*/ int i,j,k; elemtype tmp; for(i=0;i<n;i++) if(index[i]!=i) /*r[i]需要调整*/ { tmp=r[i];/*用tmp保存r[i]*/ j=i; k=index[j];/*自此，r[k]应该放到r[j]的位置上，除非k等于i*/

27 二、内排序——索引排序(3) while(k!=i) { r[j]=r[k]; /*r[j]空闲，将r[k]复制到r[j]中*/
index[j]=j; /*调整索引表指针值*/ j=k; /*这时r[j]又空闲*/ k=index[j]; } /*while循环退出，说明k等于i，而r[i]已经是调整好的数据，需要放到r[j]中去的数据是原来的r[i],它保存在tmp中*/ r[j]=tmp; index[j]=j;

28 二、内排序——计数排序(1) 计数排序 【基本思想】设定一个计数器数组，记录每个数据元素比它小的数据元素的个数。 计数排序需要物理重排

29

30 二、内排序——计数排序(2) void CountSort(elemtype r[ ],int n)
{ int *count; int i,j,k; elemtype tmp1,tmp2; count=(int *)malloc(n*sizeof(int)); if(count==NULL) return; for(i=0;i<n;i++) count[i]=0;/*将计数器都清零*/ for(i=0;i<n-1;i++) for(j=i+1;j<n;j++)/*每次比较都同时维护两个计数器，j只需从i+1开始*/ if(r[i]>=r[j]) count[i]++; /*如果r[i]大，则count[i]增1，否则count[j]增1*/ else count[j]++;

31 二、内排序——计数排序(3) /*下面开始对r进行物理重排*/ for(i=0;i<n;i++)
if(count[i]!=i) /*开始调整r[i]*/ { j=i; /*j指向要调整的单元*/ k=count[j];/*k指向要覆盖的单元*/ tmp1=r[j];/*用tmp1保存要移动的数据单元*/ while(k!=i) /*调整循环*/ { tmp2=r[k]; /*用tmp2保存要被覆盖的数据单元*/ r[k]=tmp1; /*将tmp1复制到r[k]中*/ j=k; /*j指向k，r[j]已经保存在tmp2中了*/ k=count[j]; /*k指向下一个要覆盖的单元*/ count[j]=j; /*调整计数器信息*/ tmp1=tmp2;/*将r[j]保存到tmp1中，准备移动到r[k]，tmp2要保存那个r[k]*/ } r[i]=tmp1;/*tmp1所保存的数据应该位于r[i]*/ count[i]=i; } free(count);

32 二、内排序——归并排序(1) 归并排序 void MergeSort(elemtype r[ ],int n) /*对长度是n的序列r进行归并排序*/ { int low,high,len; len=1;/*有序子表长度一开始是1*/ while(len<n) /*只要子表长度小于n，就需要一趟合并操作*/ { low=0; /*合并区间的起点一开始是0*/ while(low+len<n) /*开始一趟合并操作*/ { /*从low开始算，至少存在两个子序列没有合并，继续合并*/ high=low+2*len-1; /*确定合并区间的终点*/ if(high>=n)high=n-1; /*说明第2个子序列要短一些*/ /*调用函数SegmentMerge，将区间r[low..high]内的2个子序列合并*/ if(!SegmentMerge(r,low,high,len)) return; low=high+1;/*确定下一个合并区间的起点*/ } len*=2;/*有序子序列的长度增倍*/

33 二、内排序——归并排序(2) int SegmentMerge(elemtype r[ ],int low,int high,int len) {/*r[low..high]区间内存在着两个长度是n的有序子序列，将它们合并成1个有序子序列*/ elemtype *r1,*r2;/*r1,r2是两个辅助空间，分别存放两个有序子序列*/ int size1,size2;/*分别是r1,r2空间的大小*/ int i,j,k; size1=len;size2=high-low+1-len;/*确定r1,r2的大小*/ r1=(elemtype *)malloc(size1*sizeof(elemtype)); r2=(elemtype *)malloc(size2*sizeof(elemtype)); if(r1==NULL||r2==NULL)return 0; /*将区间r[low..high]中的2个子序列分别复制到r1,r2中*/ for(i=0;i<size1;i++) r1[i]=r[low+i]; for(i=0;i<size2;i++) r2[i]=r[low+size1+i];

34 二、内排序——归并排序(3) /*下面开始将r1,r2有序合并到r[low..high]中*/ i=0; j=0; k=low;
while(i<size1&&j<size2) if(r1[i]<=r2[j]) r[k++]=r1[i++]; else r[k++]=r2[j++]; while(i<size1) r[k++]=r1[i++]; while(j<size2) r[k++]=r2[j++]; /*释放辅助空间，返回*/ free(r1); free(r2); return 1; } 时间复杂度：

35 二、内排序——基数排序(1) 基数排序是一种利用多关键字排序的思想对单关键字序列进行排序的方法。 对多关键字数据元素进行排序有两种方式：
最高位优先法（MSD）：先排最高位关键字 最低位优先法（LSD）：先排最低位关键字。 基数排序的基本思想是：将单个关键字看成是多个关键字的组合，利用多关键字的LSD方法，对序列进行d（d是多关键字的个数）趟排序，最终成为有序序列。 链式基数排序：将序列组织成静态链表的基数排序 链式基数排序的基本操作： 分配 收集

36

37 二、内排序——基数排序(2) 链式基数排序 typedef struct { int key; int next; }REC;
void RadixSort(int r[ ],int d,int radix,int n) { REC *rec; int *head,*tail; char str[6],formatstr[10]; int i,j,k; rec=(REC *)malloc((n+1)*sizeof(REC));/*0号单元是头结点，需要n+1单元*/ head=(int *)malloc(radix*sizeof(int)); tail=(int *)malloc(radix*sizeof(int)); if(rec==NULL||head==NULL||tail==NULL)return; rec[0].next=1; for(i=0;i<n;i++) { rec[i+1].key=r[i]; rec[i+1].next=i+2; } rec[n].next=0;

38 二、内排序——基数排序(3) /*按照LSD的方法，从个位开始，进行d次分配和收集*/ for(i=d-1;i>=0;i--) {
for(j=0;j<radix;j++) /*将所有的队列初始化为空队列*/ { head[j]=0; tail[j]=0; } /*遍历整个静态链表，开始一趟分配*/ k=rec[0].next;/*k指向第1个整数*/ while(k!=0) { sprintf(formatstr,"%%0%dd",d); sprintf(str,formatstr,rec[k].key); j=str[i]-'0'; if(tail[j]==0) /*队列空时，队首队尾指针都是k*/ head[j]=tail[j]=k; else/*如果队不空，则将队尾元素的后继指向当前整数，并修改队尾指针*/ { rec[tail[j]].next=k; tail[j]=k; } k=rec[k].next;/*k指向静态链表中下一个整数*/ }

39 二、内排序——基数排序(4) /*开始一趟收集*/ j=0; while(head[j]==0) j++; /*寻找第一个非空队列*/
rec[0].next=head[j];/*收集后的静态链表第1个整数就是该非空队列的首单元*/ k=j+1; while(k<radix) /*将剩余的队列按照顺序首尾相连即可*/ { if(head[k]!=0) { rec[tail[j]].next=head[k]; j=k; } k++; } rec[tail[j]].next=0;/*设置最后一个非空队列尾单元的后继是0*/ }//for /*至此，rec中静态链表已经有序，将它复制到r中*/ i=0; k=rec[0].next; while(k!=0) { r[i++]=rec[k].key; k=rec[k].next; } free(tail);free(head);free(rec); return; }

40 三、外排序——K路平衡归并 K路归并：一次归并多个归并段的归并排序。它比二路归并效率更高 K路归并排序中的选择结构： 堆 胜者树 败者树

41 三、外排序——置换－选择排序 用于形成长度不等的初始归并段 有序归并段 工作区（设W=6） 数据输入序列 51,49,39,46,38,29
51,49,39,46,38,29,14,61,75,3,1,12,15,3,63,27… 51,49,39,46,38,29 14,61,75,3,1,12,15,3,63,27… 29 51,49,39,46,38,□ 51,49,39,46,38,14 61,75,3,1,12,15,3,63,27… 29,38 51,49,39,46,□,14 51,49,39,46,61,14 75,3,1,12,15,3,63,27… 29,38,39 51,49,□,46,61,14 51,49,75,46,61,14 3,1,12,15,3,63,27… 29,38,39,46 51,49,75,□,61,14 51,49,75,3,61,14 1,12,15,3,63,27… 29,38,39,46,49 51,□,75,3,61,14 51,1,75,3,61,14 12,15,3,63,27… 29,38,39,46,49,51 □,1,75,3,61,14 12,1,75,3,61,14 15,3,63,27… 29,38,39,46,49,51,61 12,1,75,3,□,14 12,1,75,3,15,14 3,63,27… 29,38,39,46,49,51,61,75 12,1,□,3,15,14 12,1,3,3,15,14 63,27… 三、外排序——置换－选择排序 用于形成长度不等的初始归并段

42 三、外排序——哈夫曼归并树

43 导航图(1)

44 导航图(2)

45 导航图(3)

46 导航图(4)

47 导航图(5)

48 导航图(6)

49 导航图(7)

50 导航图(8)

51 导航图(9)