数据结构第10章-排序讲解.ppt

数据结构;概述 插入排序 快速排序 选择排序 归并排序 基数排序 各种内部排序方法的比较讨论 ;一、排序的定义;假设： (1) 在待排序序列中存在两个(以上)关键字相等的记录Ri和Rj，即：Ki=Kj (1≤i,j≤n ，i≠j ) (2) 在排序前的序列中Ri领先于Rj (即：ij ) 那么： 若排序后Ri仍领先于Rj ，则称所用的排序方法是稳定的； 否则，称所用的排序方法是不稳定的 【对不稳定的排序方法，只需举出一组关键字实例说明其不稳定性即可】; 按排序过程中涉及存储器的不同，可将排序方法分为两大类：;按排序过程中依据的不同原则大致可分为：;(1) 比较：比较两个关键字的大小 大多数排序都需要 (2) 移动：将记录从一个位置移到另一个位置 可通过改变记录的存储方式避免;排序时必须移动记录;待排记录的数据类型： #define MAXSIZE 20 // 顺序表的最大长度 typedef int KeyType; // 关键字类型 typedef struct { KeyType key; // 关键字 InfoType otherinfo; // 其它数据项 }RedType; // 记录类型 typedef struct { RedType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元 int length; // 顺序表长度 }SqList; // 顺序表类型;概述 插入排序 快速排序 选择排序 归并排序 基数排序 各种内部排序方法的比较讨论 ;一、直接插入排序;49，38，65，97，76，13，27;;二、其它插入排序; (1) 折半插入排序;;(2) 希尔排序;增量序列为：5，3，1;/* 对顺序表L作一趟希尔插入排序。本算法对算法10.1作了以下修改： 1. 前后记录位置的增量是dk，而不是1； 2. r[0]只是暂存单元，不是哨兵。当j=0时，插入位置已找到 */ void ShellInsert(SqList L, int dk) { // 算法10.4 for (i=dk+1; i=L.length; ++i) // 需将L.r[i]插入有序增量子表 if (LT(L.r[i].key, L.r[i-dk].key)) { L.r[0] = L.r[i]; // 暂存在L.r[0] for (j=i-dk; j0 LT(L.r[0].key, L.r[j].key); j-=dk) L.r[j+dk] = L.r[j]; // 记录后移，查找插入位置 L.r[j+dk] = L.r[0]; // 插入 } } // ShellInsert;概述 插入排序 快速排序 选择排序 归并排序 基数排序 各种内部排序方法的比较讨论 ;快速???序是一种借助“交换”进行排序的方法;void BubbleSort(SqList L) { for(i=1;in; i++) {change=FALSE; for(j=1; jn-i+1; j++) if(L.r[j].keyL.r[j+1].key) {change=TRUE; L.r[j]??L.r[j+1]; } if(!change) return; } };快速排序是对起泡排序的一种改进 基本思想：;假设待排序序列为{ L.r[s]，L.r[s+1]，…，L.r[t] };49 38 65 97 76 13 27 49;具体实现： low=s; high=t; pivotkey=L.r[low].key; (1)从high开始往前找第一个关键字小于pivotkey的记录，与枢轴记录交换 (2)从low开始往后找第一个关键字大于pivotkey的记录，与枢轴记录交换 (3)重复（1）（2）直到low= =high为止 此时枢轴记录所在的位置i=low=high;/* 算法10.6(a) 交换顺序表L中子表L.r[low..high]的记录，使枢轴记录到位，并返回其所在位置，此时在它之前(后)的记录均不大(小)于它 */;;// 对顺序表L作快速排序;;概述 插入排序 快速排序 选择排序 归并排序 基数排序 各种内部排序方法的比较讨论 ;;;// 对顺序