数据结构与算法.优秀PPT.ppt

《数据结构与算法.优秀PPT.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法.优秀PPT.ppt（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第十章.内部排序 （Chapter 10.Internal Sorting)排序又称分类，是计算机中最重要的操作，它是将一个数据元素（或记录）的随意序列排列成一个按关键字有序的序列。若待排序列中存在两个或以上关键字相等的记录，设Ki=Kj(1i jn)，即排序前 Ri 在 Rj 前，若在排序后 Ri 仍在 Rj 前，则称排序是稳定的。稳定的排序方法（稳定的排序方法（stable sorting method)排序（排序（sorting)不稳定的排序方法（不稳定的排序方法（unstable sorting method)待排序列中存在两个或以上关键字相等的记录，设Ki=Kj(1i jn)，即排序

2、前 Ri 在 Rj 前，若在排序后 Rj 却在 Ri前，则称排序是不稳定稳定的。内部排序（内部排序（internal sorting）待排序列记录全部存放在计算机随机存储器中进行排序的过程称为内部排序。外部排序（外部排序（external sorting）待排序列记录数量太大，不能全部存放在计算机随机存储器中，排序过程中需对计算机外存进行访问，这种排序过程称为外部排序。1、比较操作：比较两个关键字值的大小的操作。排序过程中的两种基本操作：排序过程中的两种基本操作：2、移动操作：将记录从一个位置移动到另一个位置的操作。待排序列的三种存储结构：待排序列的三种存储结构：1、依次存储：存储在地址连续的

3、一组存储单元中、依次存储：存储在地址连续的一组存储单元中（以此为例）。（以此为例）。2、链式存储：存储在地址不连续的一组存储单元（链表）中。3、地址存储：记录依次存储，另设关键字和记录、地址存储：记录依次存储，另设关键字和记录地址排序。地址排序。typedef struct keytype key;.elemtype;typedef struct elemtype *elem;int length;sqlist;10.1 插入排序一、干脆插入排序：一、干脆插入排序：干脆插入排序（straight insertion sort）是一种最简洁的排序方法：将记录一个个插入到已排序好的有序表中，从而得

4、到长度增加的新的有序表。void straightinsertsort (sqlist&R)for (i=2;i=R.length;i+)if (R.elemi.key R.elemi-1.key)R.elem 0 =R.elem i ;R.elem i =R.elem i-1 ;for (j=i-2;R.elem0.key R.elemj.key;j-)R.elem j+1=R.elem j;R.elem j+1 =R.elem 0 ;排序性能分析：比较次数：最好状况 n-1 最坏状况 (n+2)(n-1)/2 平均比较次数：(n+4)(n-1)/4二、折半插入排序：二、折半插入排序：折半插

5、入排序（binary insertion sort）与干脆插入排序不同之处在于查找插入位置时不是用依次查找，而是用折半查找。可见，干脆插入排序的时间困难度为 O(n 2)。但在待排序列有序的的状况下，干脆插入排序的时间困难度下降为 O(n)。移动次数：最好状况 0 最坏状况 (n+4)(n-1)/2 平均移动次数：(n+4)(n-1)/4 折半插入排序的移动次数与干脆插入排序相同，只是比较次数少了，因此其时间困难度也为 O(n 2)。三、三、2-路插入排序：路插入排序：2-路插入排序目的是为了削减排序过程中移动记录的次数，代价是须要 n 个记录的协助空间 d：将 r1 赋值给 d1，将 d 看

6、成循环的，其它记录均与 d1 比较，比其小则在 d1 前插入，反之则在 d1 后插入。2-路插入排序的移动次数大约为 n 2/2，因此其时间困难度仍为 O(n 2)。四、表插入排序：四、表插入排序：表插入排序需附设一个指针域，通过变更指针的值来达到不移动记录而得到排序结果的目的。表插入排序是用变更指针来代替移动记录操作，因此其时间困难度还为 O(n 2)。表插入排序的结果是形成了链表，因此查找时只能用依次查找，为能运用折半查找，需对记录重新排序，但这不影响其时间困难度。五、希尔排序：五、希尔排序：希尔排序（Shells method），又称为“缩小增量排序”（diminishing incre

7、ment sort），是一种比较困难的插入排序。希尔排序的思想是：用确定的增量间隔将待排序列分成多个组，每组都接受简洁插入排序；排序完一遍后，缩小增量间隔，再对新的分组接受简洁插入排序；反复此过程，直至增量间隔为 1，即整个待排序列为一组时，执行一遍简洁插入排序后结束。125256 345 12 214 8 452 21 99 618 7732待排序列：125 32 256 345 12 214 8 452 21 99 618 77增量为 7：125452322125699345618127712532 256345 12 214 8 45221 99618 77增量为 5：125322563

8、4512 21484522199618 77增量为 3：1252146182187799452345321225612532256345122148452219961877增量为 1：12532256 345122148452219961877排序结果：321253221256812452618992143457712532256345122148452219961877322125699218773453221321252567799214345void Shellinsert(sqlist&L,int dk)for (i=dk+1;i=L.length;i+)if (L.elemi.key

9、 0&L.elem0.key L.elemj.key;j-=dk)L.elemj+dk=L.elemj;L.elemj+dk=L.elem0;希尔排序的时间困难度与增量序列有关，分析起来很困难，有人认为为 O(n 1.5)，也有人认为为 O(n 1.3)。在以上插入排序中，除希尔排序为不稳定排序外，其余的都是稳定的排序。void Shellsort(sqlist&L,int dlta,int t)for (k=0;k t;k+)Shellinsert(L,dltak);10.2 交换排序一、起泡排序：一、起泡排序：起泡排序（bubble sort）也是一种最简洁的排序方法：将相邻两记录一一比较

10、，将关键字较小的记录交换在前面，反复此过程，直到待排序列有序为止。void bubblesort(sqlist&r)for (i=1;i=r.length;i+)for(j=1;j r.elem j+1.key)r.elem j r.elem j+1;起泡排序也是一种稳定的排序，时间困难度为 O(n 2)。二、快速排序：二、快速排序：快速排序（quick sort）是对起泡排序的改进：将待排序列第一个元素枢轴元素（pivot）放置到序列中的某个位置，使其前面的全部元素的关键字都小于它，后面的全部元素的关键字都大于它；再分别对枢轴元素前面和后面的两段待排序列接受快速排序方法，直至每一段都只剩下一

11、个元素为止。int quickpass(sqlist&R,int low,int high)R.elem0=R.elemlow;pivotkey=R.elemlow.key;while (low high)while (low=pivotkey)high-;R.elemlow=R.elemhigh;while (low high&R.elemlow.key=pivotkey)low+;R.elemhigh=R.elemlow;R.elemlow=R.elem0;return low;void quicksort(sqlist&r,int low,int high)if (low high)pi

12、votloc=quickpass(r,low,high);quicksort(r,low,pivotloc-1);quicksort(r,pivotloc+1,high);快速排序是基于比较和交换的排序方法里最快的一种排序，其时间困难度为 O(n log n)。但快速排序的效率不太稳定，在关键字匀整分布时，效率最高；在关键字有序时，效率将退化为 O(n 2)。如何解决这个难题呢？其实，我们细致分析就可看出，效率低是因为枢轴元素的选取有问题：我们希望每次选取的枢轴元素都处于待排序列中间位置，但当待排序列有序时，枢轴元素的取值每次都是最大的或最小的。有鉴于此，我们能否考虑在枢轴元素选取时，与部分元

13、素比较一下，选取它们中处于中间大小的元素与枢轴元素交换，作为新的枢轴元素，通常是将处于待排序列头部、尾部和中间的三个元素比较，从而得到新的枢轴元素，这种方法叫“三者取中法”，它能很有效的防止快速排序效率的退化。在空间困难度上，除静态数据外，由于递归的缘由，栈的最大深度在最好的状况下为 O(log n)，在最坏的状况下为 n。在非递归算法中，每次都先对较短的子序列先进行排序能降低栈的深度。快速排序是不稳定排序。void quicksort(sqlist&r,int low,int high)INITSTACK(S);while (low n2&n1 1)PUSH(S,(low,pivotloc-

14、1);low=pivotloc+1;else if (n1 1)PUSH(S,(pivotloc+1,high);high=pivotloc-1;if (low=high&!EMPTY(S)(low,high)=POP(S);快速排序的非递归算法如下：作作 业业29.试证明：当待排序列已呈现出有试证明：当待排序列已呈现出有序状态时，快速排序的时间困难度为序状态时，快速排序的时间困难度为 O(n 2)。30.试以单链表为存储结构实现简洁试以单链表为存储结构实现简洁插入排序。插入排序。第第 六六 次次 上上 机机 作作 业业 输入若干组长度各异的待排序列，输入若干组长度各异的待排序列，分别用快速排

15、序算法和改进的枢轴元分别用快速排序算法和改进的枢轴元素三者取中算法对待排序列进行排序，素三者取中算法对待排序列进行排序，当待排子序列长度已小于当待排子序列长度已小于 20时，改用时，改用干脆插入排序，利用时间函数验证三干脆插入排序，利用时间函数验证三者取中算法在效率上的提高。（提示：者取中算法在效率上的提高。（提示：待排序列的长度一般应为待排序列的长度一般应为 5000 以上）以上）10.3 选择排序一、简洁选择排序：一、简洁选择排序：简洁选择排序（simple selection sort）同样也是一种最简洁的排序方法：每次从待排序列中选出关键字最小记录作为有序序列中最终一个记录，直至最终一

16、个记录为止。void simpleselectionsort(sqlist&R)for (i=1;i R.length;i+)for (k=i,j=i+1;jR.length;j+)if (R.elemj.keyR.elemk.key)k=j;if (k!=i)R.elem i R.elem k;二、树形选择排序：二、树形选择排序：借鉴体育竞赛中淘汰赛的做法，将两两竞赛过的优胜者推举出去与其它组的优胜者竞赛，反复此过程，直到决出冠军为止；若能记住每次竞赛的结果，则亚军的产生不必再经过此过程，只需将与冠军赛过的每一个运动员逐级进行竞赛，即可得到亚军，这就是树形选择排序的思路。树形选择排序（tre

17、e selection sort），又称为锦标赛排序（tournament sort），是一种按锦标赛思 由于有不相邻元素交换，所以简洁选择排序是不稳定的排序，其时间困难度为 O(n 2)。树形选择排序除第一次外，每次都走了树的一条分支，故其时间困难度为 O(n log n)。想进行的排序：将相邻记录两两分为一组进行比较，将关键字较小的记录送往上一层，参与与其它组关键字较小记录的比较，两两比较后再送往上层关键字较小记录，反复此过程，直到只剩下一个记录即为关键字最小记录；将待排序列中该最小记录处置为无穷大，则与其比较过的全部记录按层次逐级比较，直至找到下一个最小记录为止；反复此过程直至序列有序。

18、三、堆排序：三、堆排序：堆的定义：堆的定义：堆排序的思路：将待排序列建成堆（初始堆生成）后，堆排序的思路：将待排序列建成堆（初始堆生成）后，则序列的第一个元素（堆顶元素）就确定是序列中的则序列的第一个元素（堆顶元素）就确定是序列中的最大元素；将其与序列的最终一个元素交换，将序列最大元素；将其与序列的最终一个元素交换，将序列长度减一；再将序列建成堆（堆调整）后，堆顶元素长度减一；再将序列建成堆（堆调整）后，堆顶元素 树形排序须要 2n-1 个协助空间，1964 年J.Willioms 提出另外一种选择排序堆排序（heap sort）。kik2i 或 kik2i i=1,2,n/2 kik2i+1

19、 ki k2i+1 n 个元素的序列 k1,k2,kn当且仅当满足下列关系时，称之为堆：仍是序列中的最大元素，再次将其与序列最终一个元素交换并缩短序列长度；反复此过程，直至序列长度为一，所得序列即为排序后结果。有一组待排记录的关键字为32，12，91，26，74，58，63，85，试对其进行堆排序：例：例：85 26 74 58 63 91 12 32 26 85 85 26 63 91 63 91 12 85 12 85 26 12 12 26 32 91 32 91 63 32 32 63 12 91 12 85 85 12 12 74 74 12 85 32 74 32 32 74 74

20、 58 58 63 63 58 63 12 58 12 12 58 58 26 32 26 26 32 32 12 12 26 26 12 26 12 堆排序的结果为：12，26，32，58，63，74，85，91。那么，应如何建立初始堆？又如何进行堆调整呢？其实，由此例可以看出，建立初始堆就是多次进行堆调整的过程。void heapadjust(sqlist&R;int k;int m)j=2*k;x=R.elem k.key;finished=0;t=R.elem k;while (j=m&!finished)if (j R.elem j+1.key)j+;if (x 0;i-)heapa

21、djust(R,i,R.length);for (i=R.length;i 1;i-)R.elem 1 R.elem i;heapadjust(R,1,i-1);堆排序只需一个协助空间用于交换，其时间困难度为 O(nlog n)，堆排序是不稳定排序。10.4 归并排序 归并排序（merging sort）的思想是每次将两个或两个以上的有序表合并成一个较长的有序表，反复此过程，直到最终只剩下一个有序表为止；单个记录即是最初的有序表。void merge(sqlist&R,sqlist&T,int s1,int s2,int t2)q=s1;t1=s2-1;while (s1=t1&s2=t2)i

22、f (R.elem s1 =R.elem s2 )T.elemq+=R.elem s1+;else T.elemq+=R.elem s2+;while (s1=t1)T.elemq+=R.elem s1+;while (s2=t2)T.elemq+=R.elem s2+;void mergesort(sqlist&R)for (len=1,TR=1;len R.length;len*=2)s1 =1;while (s1+len R.length)t2=R.length;if(TR)merge(R,T,s1,s2,t2);else merge(T,R,s1,s2,t2);s1=t2+1;TR=!

23、TR;if (!TR)for (i=1;i s1;i+)R.elem i =T.elem i;以上给出的是二路归并排序的非递归算法，其实归并排序可以很便利的用递归程序实现。归并排序是一种稳定的排序方法，其时间困难度为 O(n log n)，协助空间为 n。作作 业业31.假设有假设有 n 个值不同的元素存于数组个值不同的元素存于数组 A(1:n)中，另设一数组中，另设一数组 C(1:n)，对对每个元素每个元素 A i，C i 存放存放 A 中值小中值小于于A i 的元素的个数，则的元素的个数，则 C i=0的元的元素即为最小元素；素即为最小元素；然后依据然后依据 C 的值大的值大小将小将 A

24、中的元素重新排列。中的元素重新排列。这种方法这种方法称为计数排序，试编程实现之。称为计数排序，试编程实现之。10.5 基数排序 基数排序（radix sort）是和前面所介绍的排序方法（基于比较的排序方法）完全不同的一种排序方法，它是一种安排排序。多关键字排序：多关键字排序：如 52 张扑克牌按以下规则排成有序：可以看出：牌点是确定大小的主要因数（34 10J QKA2），花色则是确定大小的次要因数（DiamondClub HeartSpade），只有在牌点相同时，它才起作用。因此我们称牌点为高位关键字，花色为 D3C3H3S3D4C4HASAD2C2H2S2 一般的，设有 n 个记录序列（R

25、1,R2,Rn），每个记录 Ri 均含有 d 个关键字（Ki1,Ki2,Kid），则称此序列对关键字（K1,K2,Kd）有序，是指序列中随意两个记录 Ri 和 Rj（1 i j n）都满足有序关系：（Ki1,Ki2,Kid）（Kj1,Kj2,Kjd），其中 K1 称为最高位关键字，Kd 称为最低位关键字。那么应如何实现序列的多关键字排序呢？低位关键字，确定元素的大小主要看高位关键字，低位关键字只有在高位关键字相等时才发挥作用。LSD法法 将待排序列依次按 Kd,Kd-1,K1 进行排序得到有序序列，这种排序方法称为最低位优先法（Least Significant Digit first）。MS

26、D法法 将序列先按将序列先按 K1 进行排序，则序列将分进行排序，则序列将分成若干子序列，每个子序列中的记录均具有相同的成若干子序列，每个子序列中的记录均具有相同的 K1 值；然后再分别对各子序列按值；然后再分别对各子序列按 K2 进行排序，则进行排序，则序列将分成更多的子序列；反复此过程，直到全部序列将分成更多的子序列；反复此过程，直到全部子序列分别按子序列分别按 Kd 进行了排序后，再将全部子序列依进行了排序后，再将全部子序列依次联接成一个有序序列，这种排序方法称为最高位次联接成一个有序序列，这种排序方法称为最高位优先法优先法（Most Significant Digit first）。）

27、。MSD 与 LSD 各有什么特点呢？MSD 在排序时间上要比 LSD 快些，且每次对排序方法是否稳定没有要求，但操作起来相对困难，因为序列将被分成若干个子序列；而 LSD 每次均对全部记录进行排序，但除按低位关键字排序对稳定性没有要求外，其后的全部排序方法均需是稳定的。LSD 比较简洁用多次安排和收集来实现。链式基数排序：链式基数排序：基数排序是将关键字看成 d 个关键字复合而成，即按其基数 rd 所处位置的权值大小分成高、低位关键字，再应用多次安排、收集方法将待排序列排成有序序列。该方法又称为桶排序（bucket sort），待排序列用静态链表存储，是用 2 rd 个指针来作为 rd 个桶

28、的底和盖指针，每次安排即将 n 个记录按其 Ki 安排到各个桶中，收集时则按各桶依次从上到下依次收集。待排序列：（22，12，91，26，74，53，51，85）分配：0 1 2 3 4 5 6 7 8 9|2212912674535185收集：（91，51，22，12，53，74，85，26）分配：0 1 2 3 4 5 6 7 8 9|收集：（12，22，26，51，53，74，85，91）9122125374852651 有一组待排记录的关键字为22，12，91，26，74，53，51，85，试对其进行基数排序：例：例：10.6 前面介绍的各种内部排序方法的比较 一次安排的时间为 O(n

29、)，一次收集的时间为 O(rd)，故基数排序的时间困难度为 O(d(n+rd)。基于比较的排序方法，最好的时间困难度是 O(n log n)，下面介绍一种公式分组排序方法，其时间困难度为 O(n)：有 n 个关键字的待排序列（R1,R2,Rn），其关键字最小值和最大值分别为 min 和 max，则可利用下面公式将待排序列分组到 n+1 个子序列，再对各子序列接受此方法接着分组，直至每个子序列只要一个记录为止：Ci=ak，1 i n，可取，可取 a=1，k=n。max-minRi.key-min该排序方法最适合关键字匀整分布的待排序列。作作 业业32.假设有假设有 n 个值不同的元素存于依个值不同的元素存于依次结构中，要求不经排序选出自大至次结构中，要求不经排序选出自大至小的前小的前k(kn)个元素，问哪些方法个元素，问哪些方法可用，哪些方法比较次数最少？可用，哪些方法比较次数最少？33.设有设有 n 个值不同的元素存于依次个值不同的元素存于依次结构中，问能否用比结构中，问能否用比 2n-3 次少的比较次少的比较次数找出该序列的最大值和最小值？次数找出该序列的最大值和最小值？若能，应如何实现，最坏状况如何？若能，应如何实现，最坏状况如何？