中央广播电视大学开放教育试点课程 数据结构 辅导教师 倪政林

数据结构 第一章 绪论 第二章 线性表 第三章 稀疏矩阵和广义表 第四章 栈和队列 第五章 树和二叉树 第六章 二叉树的应用 第七章 图 第八章 查找 第九章 排序

第九章 排序 9.1 基本概念 1、一些重要的基本概念 排序域：用来排序的域称排序域，以后用x.stn来标识。（X为记录名） 第九章 排序 9.1 基本概念 1、一些重要的基本概念 排序域：用来排序的域称排序域，以后用x.stn来标识。（X为记录名） 2、稳定排序：对于有重码的排序域在一定的排序算法下如果其原有的顺序发生了改变则这种排序为不稳定排序，否则称稳定排序。如（23，14，45，36，23） 其稳定排序为: (14,23,23,36,45) 不稳定排序为: (14,23,23,36,45) 3、分类：内部排序和外部排序

9.2 选择排序 9.2.1、 直接选择排序：每次从未排序的表中选择 一个最小的值和其第一位元素互换位置。被换到 前面的元素不再参与下一轮的互换。 2、 举例：0 36 25 48 12 65 43 20 58 1 12 25 48 36 65 43 20 58 2 12 20 48 36 65 43 25 58 3 12 20 25 36 65 43 48 58 4 12 20 25 36 65 43 48 58 5 12 20 25 36 43 65 48 58 6 12 20 25 36 43 48 65 58 7 12 20 25 36 43 48 58 65

3、 直接选择算法设计： A＝{36,25,48,12,65,43,20,58} Void selecsort(elemtype A[],int n) { elemtype x; int i,j,k; for(i=1;i<=n-1;i++) {k=i-1; for(j=i; j<=n-1; j++) if( A[j].stn < A[k].stn ) k=j; if( k != i-1 ) {x=A[i-1]; A[i-1]= A[k]; A[k] = x;} }

4、 插入排序：每次从原表中选择一个元素插入到已排序的表中，在被插入的表中从后向前遍历。算法如下：原表为：a，被插入的表为b（数据结构见第二章） for(i=0;i<=a.length;i++) ( 注：初始b.length=0) { if( b.length=0) {b.length=1;b.data[b.length]=a.data[i];} Else {j = b.length; b.length++; while (b.data[j] > a.data[i]) {b.data[j+1] = b.data[j];j--;} b.data[j+1]=a.data[i]; }

5、直接选择排序和插入排序的比较 1、直接选择排序：共进行N－1次的选择和交换，每次选择需比较N－1次，其中1＝＜I＜＝N－1， 每次交换最多需移动3次记录，故 总比较次数：C=∑(n-i)=(n2-n)/2 总移动次数（最大值）：M＝∑3=3(n-1) 时间复杂度为：O（n2)， 空间复杂度为：O(n)，不稳定的排序 2、插入排序： 时间复杂度为： O（n2)， 空间复杂度为：O(n2)，是一种稳定的排序

9,2,2 堆排序：利用大根堆的特性进行排序的 过程。排序过程包括两部分，一是构建初始堆， 二是利用堆进行排序的过程。 1 2 3 4 5 9,2,2 堆排序：利用大根堆的特性进行排序的 过程。排序过程包括两部分，一是构建初始堆， 二是利用堆进行排序的过程。 1、图例演示 筛72，不动 45 45 1 2 36 18 36 18 3 4 5 6 53 30 48 72 53 30 48 72 93 15 36 93 15 36 7 8 9

筛53 下移一层 筛18，下移一层 45 45 36 18 36 48 93 30 48 72 53 30 18 72 53 15 36 93 15 36

筛45，下移二层 筛36 下移二层 93 45 72 48 93 48 53 30 18 53 30 18 45 72 36 36 15 15 36 36

2、排序 93与36对换 筛36，下移二层 72 36 48 53 48 72 36 30 18 53 30 18 45 45 36 36 15 15 93 93

72与15对换 15 筛15 下移两层 53 53 48 45 48 36 30 18 45 36 30 18 15 36 72 93 36 72 93

53与36对换 筛36 下移一层 36 48 45 48 45 36 36 30 18 15 36 30 18 15 53 72 93 53 72 93

48与18对换 18 筛18 下移二层 45 45 36 36 36 36 30 48 15 18 30 48 15 53 72 93 53 72 93

Void sift(elemtype a[ ] , int n, int i) {elemtype x=a[i] int j=2*i+1; 3、算法设计 3.1 筛第i位置的元素 Void sift(elemtype a[ ] , int n, int i) {elemtype x=a[i] int j=2*i+1; While(j<=n-1) { if (j<n-1 && a[j].stn < a[j+1}.stn) j++; if(x.stn<a[j].stn) {a[i]=a[j]; i=j ; j=2*i + 1;} else break; } A[i]=x; }

3.2 堆排序算法如下： Void heapsort ( elemtype a[ ] ,int n) { elemtype x; int i; for (i=n/2 -1; i >= 0; i--) sift ( a, n, i); //建立初始堆 for (i=1 ; i <= n-1 ;i++) {x=a[0]; a[0]=a[n-i]; a[n-i] = x; sift (a, n-i ,0); }

3.3 堆排序算法性能分析： 1、 筛选总次数为：n+ | n/2 |-1次 2、每次筛选的时间复杂度为O(log2n), 整个堆的筛选时间为：O(nlog2n) 3、是一种不稳定的排序。

9.3 交换排序 交换排序包括：气泡排序和快速排序 9.3.1 气泡排序：又称冒泡排序（图解如下） 1.下标0 1 2 3 4 5 6 7 9.3 交换排序 交换排序包括：气泡排序和快速排序 9.3.1 气泡排序：又称冒泡排序（图解如下） 1.下标0 1 2 3 4 5 6 7 (0) 36 25 48 12 65 43 20 58 (1) 12 36 25 48 20 65 43 58 (2) 12 20 36 25 48 43 65 58 (3) 12 20 25 36 43 48 58 65 (4) 12 20 25 36 43 48 58 65 (5) 12 20 25 36 43 48 58 65 (6) 12 20 25 36 43 48 58 65 (7) 12 20 25 36 43 48 58 65

2 气泡排序的算法设计如下： Void bubblesort(elemtype a[ ], int n ) {elemtype x; 2 气泡排序的算法设计如下： Void bubblesort(elemtype a[ ], int n ) {elemtype x; int i ,j, flag ; For(i=1;i<=n-1;i++) {flag=0; for(j=n-1;j>=I; j--) if(a[j].stn < a[j-1].stn {x=a[j]; a[j]=a[j-1]; a[j-1]=x; flag=1;} if(flag==0) break; }

3 气泡排序的算法分析： 1、平均时间复杂度为： 2、气泡排序通常比直接插入排序和直接选择排序需。 3 气泡排序的算法分析： 1、平均时间复杂度为： 2、气泡排序通常比直接插入排序和直接选择排序需。 移动较多次数的记录，所以它是三种简单排序方法中 速度最慢的一个。 3、气泡排序是稳定的。

9.3.2 快速排序：（又称划分排序） 1、思想：是目前最快的一种排序，是对气泡排序的一 种改进。它从两端向中间进行交换。（图例如下：） 9.3.2 快速排序：（又称划分排序） 1、思想：是目前最快的一种排序，是对气泡排序的一 种改进。它从两端向中间进行交换。（图例如下：） 0 1 2 3 4 5 6 7 8 9 开始: 45 53 18 36 72 30 48 93 15 36 i j 45 36 18 36 72 30 48 93 15 53 i j i j 45 36 18 36 15 30 48 93 72 53 j i 30 36 18 36 15 45 48 93 72 53 一次划分的过程

2、 算法设计： void quicksort(elemtype a[ ] ,int s, int t) { int i=s ,j=t+1; elemtype x=a[s]; do { do i++; while(a[i].stn < x.stn); do j-- ; while(a[j].stn > x.stn); if(i < j){ elemtype temp = a[i]; a[i] = a[j] ; a[j] = temp; } } while(i<j); a[s]=a[j]; a[j]=x; //以上为一个划分的过程 if (s<j-1) quicksort(a,s,j-1); if (j+1<t) quicksort(a,j+1,t); }

3、 完整图例如下： 45 53 18 36 72 30 48 93 15 36 30 36 18 36 15 45 48 93 72 53 18 15 30 36 36 45 48 93 72 53 15 18 30 36 36 45 48 93 72 53 15 18 30 36 36 45 48 53 72 93

4、 性能分析 1）是一种不稳定的排序。 2）平均和最好的情况下时间复杂度为：O(nlog2n) 其空间复杂度为：O(log2n) 4）进行改进。

9.4 归并排序 1、思想介绍：将两个或多个有序表合并成一个有 序表的过程，称二路归并（或N路归并） 2、图例如下： 9.4 归并排序 1、思想介绍：将两个或多个有序表合并成一个有 序表的过程，称二路归并（或N路归并） 2、图例如下： 开始: 0: 45 53 18 36 72 30 48 93 15 36 1: 45 53 18 36 30 72 48 93 15 36 2: 18 36 45 53 30 48 72 93 15 36 3: 18 30 36 45 48 53 72 93 15 36 4: 15 18 30 36 36 45 48 53 72 93

3、 将两个有序表进行两路归并算法如下： void twomerge(elemtype a[ ] , elemtype r[ ] , int s, int m, int t) { int i , j , k ; i=s ; j=m+1 ; k=s ; while( i<=m && j<=t ) if(a[i].stn <= a[j].stn) {r[k] = a[i] ; i++ ; k++ ;} else{ r[k] = a[j]; j++; k++;} while (i <= m) {r[k]=a[i]; i++; k++;} while(j <= t) {r[k] = a[j]; j++; k++;} }

4、对若干个有序表进行一趟二路归并排序 void mergepass(elemtype a[ ] , elemtype r[ ] , int n, int len ) {int p=0; while(p+2*len-1 <= n-1 ) {twomerge(a, r, p, p+len-1, p+2*len-1 ) ; p+ = 2*len ; } if(p+len-1 < n-1) twomerge(a , r , p , p+len-1 , n-1 ); else for(int i = p; i<=n-1; i++ ) r[i]=a[i]; }

Void mergesort (elemtype a[ ],int n) { elemtype *r=new elemtype[n]; 5、 两路归并的总算法如下： Void mergesort (elemtype a[ ],int n) { elemtype *r=new elemtype[n]; int len=1 while(len<n) { mergepass(a,r,n,len) len*=2; mergepass(r,a,n,len); len*=2; } delete [ ] r;} 6、性能分析：时间复杂度为：O(nlog2n) 空间复杂度为：O(n) (最高) 排序是稳定的。

1、当待排序的记录数较大时，排序码分布较随机， 2、当待排序的记录数较大时，内存空间允许，且要求 总结： 1、当待排序的记录数较大时，排序码分布较随机， 对稳定性不作要求时，采用快速排序为宜。 2、当待排序的记录数较大时，内存空间允许，且要求 排序稳定时，采用归并排序为宜。 3、当待排序的记录数较大时，排序码分布可能会出现 正序或逆序的情况，且对稳定性不作要求时，采用 堆排序（或归并排序）为宜。 4、当待排序记录数较小，记录或基本有序（即正序） 或分布较随机,且要求稳定时,采用直接插入排序为宜。 5、当待排序记录数较小，对稳定不作要求时，采用直 接选择排序为宜，若排序码不接近逆序，亦可采用 直接插入排序。