数据结构PPT 排序

第7章排序•学习要点：–理解排序的定义和各种排序方法的特点，并能加以灵活应用。

排序方法有不同的分类方法，基于关键字间的比较进行排序的方法可以按排序过程所依据的不同原则分为插入排序、交换排序、选择排序、归并排序和计数排序等五类。

–掌握各种排序方法的时间复杂度的分析方法。

能从关键字间的比较次数分析排序算法的平均情况和最坏情况的时间性能。

按平均时间复杂度划分，内部排序可分为三类：O(n2) 的简单排序方法，O(n·logn)的高效排序方法和O(d·n)的基数排序方法。

–理解排序方法稳定或不稳定的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。

•排序定义：–若给定一组记录序列r1，r2，…，rn，其排序码为s1，s2，…，sn，将r1，r2，…，rn按s1，s2，…，s n递增或递减排列的过程，称为排序。

•稳定与不稳定：–具有同一排序码的多个记录，若采用的排序方法使排序后记录的相对次序不变，则称此排序方法是稳定的，–否则称为不稳定的。

•排序的目的：便于查找。

•排序算法的好坏的衡量：–时间效率——排序速度(即排序所花费的全部比较次数)–空间效率——占内存辅助空间的大小–稳定性——若两个记录A和B的关键字值相等，但排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。

•排序码(Sort Key)：–排序依据的属性。

可以是任何一种可比的有序数据类型，–可以是记录的关键字，也可以是任何非关键字。

•有序表与无序表：–一组记录按排序码的递增或递减次序排列的结果被称之为有序表。

–把排序前的状态称为无序表。

•正序表与逆序表：–若有序表是按排序码升序排列的，称为升序表或正序表；–否则称为降序表或逆序表。

•内排序：排序过程全部在内存中进行。

•外排序：排序过程需要不断地进行内存和外存之间的数据交换。

•外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多。

(不要求)•待排序记录在内存中的存储和处理：–顺序排序——排序时直接移动记录；–链表排序——排序时只移动指针；–地址排序——排序时先移动地址，最后再移动记录。

注：地址排序中可以增设一维数组来专门存放记录的地址。

排序算法的效率•评价排序算法的效率主要有两点：–在数据量规模一定的条件下，算法执行所消耗的平均时间，对于排序操作，时间主要消耗在关键字之间的比较和数据元素的移动上，因此可以认为高效率的排序算法应该是尽可能少的比较次数和尽可能少的数据元素移动次数；–执行算法所需要的辅助存储空间，辅助存储空间是指在数据量规模一定的条件下，除了存放待排序数据元素占用的存储空间之外，执行算法所需要的其他存储空间，理想的空间效率是算法执行期间所需要的辅助空间与待排序的数据量无关。

排序的时间复杂度•排序过程主要是对记录的排序码进行比较和记录的移动过程。

排序的时间复杂度用算法执行中数据的比较次数及数据移动次数来衡量。

•当一种排序方法在排序过程中最坏或平均情况下所进行的比较和移动次数越少，认为该方法的时间复杂度好，分析一种排序方法，不仅要分析它的时间复杂性，而且要分析它的空间复杂性、稳定性和简单性等。

待排序记录序列的存储结构•待排序记录序列可以用顺序存储结构和和链式存储结构表示。

在本章的讨论中(除基数排序外)，将待排序的记录序列用顺序存储结构表示，即用一维数组实现。

其定义如下所示：#define MAX_NUM 80//待排序记录序列中的最大数据typedef struct elemtype{ //待排序的数据元素类型keytype key;//数据元素的关键字anytype otheritem;//数据元素中的其他成份}DataType[MAX_NUM+1];内部排序的算法分类排序插入排序（直插排序、二分排序、希尔排序）交换排序（冒泡排序、快速排序）选择排序（直选排序、树型排序、堆排序）归并排序（二路归并排序、多路归并排序）分配排序（多关键字排序、基数排序）插入排序•插入排序的基本思想是：–每步将一个待排序的对象，按其排序码的大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。

–简言之，边插入边排序，保证子序列中随时都是排好序的。

•插入排序有多种具体实现算法：–直接插入排序–二分插入排序–2-路插入排序–表插入排序–希尔排序小改进大改进直接插入排序•直接插入排序的基本思想：–把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素。

–排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

•新元素插入到哪里？–在已形成的有序表中线性查找，并在适当位置插入，把原来位置上的元素向后顺移。

例1：关键字序列T=（13，6，3，31，9，27，5，11），请写出直接插入排序的中间过程序列。

【13】,6,3,31,9,27,5,11【6,13】,3,31,9,27,5,11【3,6,13】,31,9,27,5,11【3,6,13，31】,9,27,5,11【3,6,9,13，31】,27,5,11【3,6,9,13，27,31】,5,11【3,5,6,9,13，27,31】,11【3, 5, 6, 9, 11，13，27, 31】1.将序列中的第一个元素作为排序后的有序序列中的第一个元素。

2.将序列中下一个元素与有序子序列中最后一个元素进行比较，如果该元素小于最后一个元素，则在该有序序列中查找该元素应该插入的位置，然后将其插入到正确的位置。

如果大于该有序子序列中的最后一个元素，则直接将其作为该有序子序列中的最后一个元素。

同时将待插入的元素作为哨兵，以避免查找插入位置的过程中出现数组下标越界。

3.循环第2步，直到将序列剩余元素全部插入到有序子序列中。

void InsertSort(SqList &L){ //对顺序表L作直接插入排序for ( i = 2; i <=L.length; ++ i )//直接在原始无序表L中排序if (L.r[i].key <L.r[i-1].key) //若L.r[i]较小则插入有序子表内{ L.r[0]= L.r[i]; //先将待插入的元素放入“哨兵”位置L.r[i]= L.r[i-1]; //子表元素开始后移for ( j=i-2; L.r[0].key <L.r[j].key; --j ) L.r[j+1]= L.r[j];//只要子表元素比哨兵大就不断后移L.r[j+1]= L.r[0]; //直到子表元素小于哨兵，将哨兵值送入//当前要插入的位置（包括插入到表首）} //if例2：关键字序列T= （21，25，49，25*，16，08），请写出直接插入排序的具体实现过程。

*表示后一个25i =1254925*16080 1 2 3 4 5 6哨兵21i =2i =3i =5i =4i =625*491625*0849解：假设该序列已存入一维数组r[7]中，将r[0]作为哨兵（Temp ）。

则程序执行过程为：212549初态：164925*25211608完成!时间效率：因为在最坏情况下，所有元素的比较次数总和为（0＋1＋…＋n-1)→O(n 2)。

其他情况下也要考虑移动元素的次数。

故时间复杂度为O(n 2)空间效率：仅占用1个缓冲单元——O(1)算法的稳定性：因为25*排序后仍然在25的后面——稳定对直接插入排序做改进？在直接插入排序的基础上，从减少比较次数和移动记录次数两方面进行改进。

折半插入排序•一个想得到的改进方法：–既然子表有序且为顺序存储结构，则插入时采用折半查找一定可以加速。

•方法：确定第i个纪录所应插入的位置，采用折半查找方法。

•优点：可减少关键字的比较次数。

每插入一个元素，需要比较的次数最大为折半判定树的深度，改善了算法中的比较次数，全部元素比较次数仅为O(nlogn)。

2•时间效率：虽然比较次数大大减少，可惜移动次数并未减少，所以排序效率仍为O(n2) 。

•空间效率：仍为O(1)。

•稳定性：稳定。

折半插入排序算法的实现void BinSort (RecordType r[], int length)//对记录数组r进行折半插入排序，length为数组的长度{for ( i = 2 ; i <= length ; ++i ){r[0] = r[i];low = 1; high = i-1;while (low <= high ) //确定插入位置{mid = (low+high) / 2;if (r[0] < r[mid]) high = mid-1;else low = mid + 1;}// whilefor ( j = i -1; j >= high+1; --j ) r[j+1] = r[j]; //记录依次向后移动r[ high + 1] = r[0]; // 插入记录}// for2-路插入排序•这是对折半插入排序的一种改进，其目的是减少排序过程中的移动次数。

•代价：需要增加n个记录的辅助空间。

•思路：增开辅助数组d, 大小与r相同。

–将r[1]赋值给d[1]，将d[1]看成是在排好序的序列中处于中间位置的纪录，从第2个记录起，和d[1]比较；若r[i].key< d[1].key，则在d的前半个序列中进行折半插入排序，反之，在后半个序列中进行折半插入排序。

–计算机处理时，可把d设为循环向量，再设头尾两个指针。

例：待排序列T=(49，38，65，97, 76, 13, 27, 49*，55, 04）排序中途: d= ( 49，65，76, 97 ), ( 13, 27, 38 ）↑final↑first （参见教材P267—268例）从2-路插入排序的过程来看，与折半插入排序相比，2-路插入排序可以减少记录移动的次数，但不能避免记录的移动。

此外需要N个额外的存储空间。

并且如果L.r[1]是待排序记录中关键字最小（或最大）的记录时，2-路插入排序就没有优越性可言了。

表插入排序•基本思想：在顺序存储结构中，给每个记录增开一个指针分量，在排序过程中将指针内容逐个修改为已经整理（排序）过的后继记录地址。

•优点：在排序过程中不移动元素，只修改指针。

•该方法具有链表排序和地址排序的特点。

1例：关键字序列T=(21，25，49，25*，16，08），请写出表插入排序的具体实现过程。

解：假设该序列（结构类型)已存入一维数组r[7]中，将r[0]作为表头结点。

则算法执行过程为：i 关键字r[i].key 指针r[i].link0121225349425*516608指向第1个元素表头结点初态i=1i=2i=3i=4i=5i=603456503102MaxNum表插入排序算法分析①无需移动记录，只需修改2n次指针值。