18.第18节课第9章排序

罗泽兵 · 发表于 2024-4-15 09:20:19

好同学们，大家好，今天呢，我们来为大家介绍一下这样一个数据结构当中排序的这样一个部分。排序呢，是计算机程序设计当中一种重要的操作。在很多领域中呢，都有广泛的应用，比如说我们这样一个学生成绩的这样一个呃，按大按数据。值了这样一个来嗯，排序的这样一个部分，以及呢，我们的这样一些记录了，按照这样一个数值的大小呢来进行排这样一个顺序的这样一个表示部分。

那么，日常生活中的各类计算活动呢，都离不开排序。排序的一个主要目的呢，是便于查找。那么，有序的顺序表呢，可以采用查找效率较高的折半查找。比如说创建数表的的过程呢，本身就是一个排序的算法，那么我们接下来来看一下排序的这样一个概念。排序呢，是计算机中经常定义为经常进行的一种操作，其目的呢，是将一组无序的记录呢，

调节为有序的数据记录。你比如说像这些关键字序列。调整为另外一个关键字序列，比如说五二四九八零三六一四五八六一二三九七七五，调整了这样一个序列，那么调整了这样一个另外一个情况的这样一个序列。那么，调整为一四二三三六四九五二五八六一七五八零九七，那么这样一些顺序？那么一般情况下呢，假设含有n个记录的序列呢，为r1r2一直到rn，其相应的关键字记录呢，为k1k2一直到kn。这些关键字记录呢之间可以进行比较，

记在它们之间呢，存在这样一个关系kpk小于kp 2。一直小于kp n，那么按此固有关系呢？将上市记录的序列重新排序呢？可以排为RP 1 RP 2，一直到rpn。这样一个操作呢，我们称之为排序。那么，接下来我们再看一下排序的稳定性，当排序记录中的关键字ki I=1到二一直到n都不相同时，则任意一个记录的无序序列呢。经过排序后得到的结果为一。那么反之呢，

当待排序列中的序列啊，有存在两个或两个以上关键字记录时呢，则排序。所得的结果呢，不一定唯一。假设ki=kg，且在排序前的序列中ri领先于rg。若在排序后的序列中呢？ri仍领先于rg，则称所排序的方法呢？是稳定的，否则呢？若可能使排序后的序列中的rg领先于ri。则称所用的排序方法呢，是不稳定的。

也就是说。在所有代排记录中，只要有一组关键字的实例不满足稳定性要求，则该排序方法呢，就是不稳定的。那么，若整个排序过程呢？不需要访问外存便能完成，则称此排列排序问题呢？为内部排序。反之，若参加排序的记录数量很大，整个序列的排序过程呢，不可能在内存中完成，则称此类排序过程呢，

为外部排序。排内部排序的过程呢，是一个逐步扩大记录的有序序列长度的过程。在排序的过程中，参与排序的记录呢，存在着两个区域。一个呢是有序区，一个是无序区。是有序之中记录的数目增加一个或几个的，这个操作呢？称为一趟排序。我们的排序呢，分为了插入类，交换类，选择类，

归并类。插入类呢，是将无序子序列中的一个或几个记录呢？插入到有序序列中，从而增加记录的有序子序列的长度。交换类呢，是通过交换无序序列中的记录，从而得到其中关键字最小或最大的记录，并将它们加入到有序子序列中，并以此方法呢，增加记录的有序子序列的长度。比如说起泡排序，快速排序属于交换类型的排序。另外呢，还有选择类，

从记录的无序子序列中选择关键字最小或者最大的记录，并将它加入到有序的子序列中。以此方法呢，增加记录的有序子序列的长度，除了简单选择排序外，堆排序呢，也属于选择类型的排序。另外呢，还有归并类，通过归并两个或两个以上的记录的有序子序列，逐步增加记录的有序序列的长度，那么这是我们排序的种类。首先我们来看一下插入排序，那么直接插入排序，直接插入排序呢，

是最简单最基本的一种，插入排序方法。插入排序的思想呢，是在一个已排好序的记录的子集的基础上，每一步呢，将下一个待排序的序记录呢，有序的插入到已排好序的记子集中。直到将所有的牌代牌记录了，全部插入为止啊，比如说打扑克时呢，那么便是插入。排序的一个很好的例子，每拿到一张牌，插入到合适位置，直到拿完牌为止，

就会得到一个有序序列。比如说我们这样一个排序的例子，首先呢，第一步I第一趟的第一步的时候呢，第一趟的时候呢，找到一个最开始的49，然后第二趟呢，找到38。38呢，这个时候就放在我们的49前面，接下来再找到65，65呢，放在38和49这样一个排好序，排序排序的排好序的这样一个部分的。这样一个排序的部分当中，

65呢，就放在最后，最后呢，再找到九再接，接下来找到97，97呢，排放在这样一个序列当中的最后面的位置。接下来找到76，76呢，放在这样一个中间的，这样一个部分，97前面的位置，十接下来找到13，13呢，放在最前面的位置，

那么最后呢，找到27，27呢。好吧。再进行一次排序，那么最后呢？进行排序呢？就得到了我们这样一个。排序的这样一个部分。得到我们这样一个结果的部分，那么排序的结果呢？就是我们下面的这样一个。结果的这样一个部分。啊，这是我们结果的这样一个部分。

那么，直接插入排序算法的三个要点呢？是第一个从ri减一起向前进行顺序查找。既然是上位置了，设在r0。r 0=ri那么设置哨兵。for g=g- 1r0小于rg。卷减g从后呢？往前找r+1返回ri的插入位置呢？为g+1。对于在查找过程中找到的那些关键字，不小于ri的记录，并在查找的同时呢，实现记录向后移动，比如说for。

g=i- 1r0，小于rg减减grg。等于rg rg+1=rg，那么把rg呢赋给rg-g+1，那么就实现了我们进入了向后移动。那么I等于二三一直到n实现整个序列的序列排序，那么监视上有什么作用呢？备份带插入的记录，以便前面关键字较大的记录后移。第二个呢，是防止越界，那么这是监视哨的作用，那么我们来看一下void insert sort element r数组intern对记录序列ren呢？一做直接插入排序for I=2 I小于等于n加加ir 0=ri赋值为间值上。for j=i- 1。

r0小于rg。减减。gr 0 rg+1=rg进入后移。rg+1。等于r0那么插入到了。正确位置。那么，这是我们插入的这样一个方式，那么，这是对我们的记录序列r1到n做直接插入排序的这样一个方式。那么，这是我们常有的这样排序的这样一个方式，那么我们来看一下这个语句，首先呢，I=2。

I小于等于n加加I，那么最开始了。r 0=ri。那么，否g？等于i- 1。r0小于rg。减减去。那么for I rig+1=rg那么记录后一。rg+1=r零，那么插入到了正确位置，那么就是我们插入的这样一个插入的这样一个方式。那么，我们来看一下算法的这样一个分析，实现排序的基本操作呢？

有两个比较序列中两个关键词的大小和移动记录。最好的情况呢，关键字在记录序列中，顺序有序。那么比较的次数呢？是2 sigma 2等I=2的n 1=n- 1移动的次数呢？是零次。最坏的记录呢，是关键字。在记录中逆序有序，比较的次数呢，是sigma I=2到ni。二分等于二分之n加二乘以n减一移动的次数呢？是二分之n加四乘以n减一。时间复杂度呢，

为on的平方，那么接下来我们再看一下折半插入排序，因为r1到ri- 1是一个按关键字有序的序列。由此呢，可利用折半查找实现在r1到i- 1中查找ri的插入位置。由此呢，实现的插入排序呢，称之为折半插入排序，比如说。那么要插入。最开始呢，找到30那么差，找到13那么这个时候13呢，那么折半插入来了吧，放在30的前面。

那么接下来呢？找到。七十八十五三十九四十二采用折半方式的方式，那么进行插入的这样一个部分，那么最后呢？找到六的时候呢？六呢？放在折半插入呢？放在这样一个前面的这样一个部分。那么最后呢，找到20那么20呢，我们看看一下这个部分20呢，首先呢？l这no指向一个开这个排序的部分的开始的部分hi指向那个排序的结尾的部分m呢指向中间那么20呢比中间这个数小那么。h呢，

就设置为m这个幂这个中间这个这个指向的这样一个这样一个部分呢，那么这样一个这样一个数数这样一个数的这样一个部分呢，中指向中间的这样一个。类这样一个部分呢，那么这个类型的这个部分呢，那么减一。那么，只要中间的这样一个。记录了那么减一的这部分，那么设置在前面的这样一个部分，然后m呢，再设置为中间那么m这个时候呢，指向的比20要小那么a。这个时候呢，把l呢？

那么放在。m的后面那么这个时候我们找到的呢，要插入的位置呢，那么就是插入到13和39了嘛，插入了这个中间的这样一个部分，插入到中间的这样一个位置。折半插入排序了，比直接插入排序了明显的减少了，关键字之间比较的次数，但移动的次数呢，仍然不变，因此呢，折半插入的事件复杂度呢，仍为on的平方。那么，

我们来看一下折半插入它的这样一个。语句。v的。b insert sort.element r数组in tn对记录序列r1n做折半插入排序for I=2 I小于等于ni加加。for r 0=ri。low=1，high=i- 1。while no小于等于him，等于no+hi÷2I fr 0小于rm。hi=m- 1 else，no=m+1。for g=i- 1g，大于等于hi+1减。减grg+1=rg，

rhi+1=r零。那么我们看一下这个语句。最开始的ri=2 I，小于等于ni加加。r 0=ri那么加ri呢，这样就存到r0 no=1 hi=i- 1。while no小于等于hi。m.no+hi÷2，那么将进行折半的这样一个方式m呢那么？设设为。m呢表示，high和low的中间这样一个部分I fr 0小于rm，那么如果r0呢小于我们的r小于我们中间这个数呢？那么high呢等于m- 1。

那么，如果r0呢？大于中，大于或等于中间这个数呢？no呢？等于m+1，那么当我们的no？小于等于hi的时候呢？继续这样一个循环，那么当no呢？大于hi的时候，那么停就就不再进行这样一个运行。for g=for g=i- 1。g大于等于h+1减减g。rg+1=rg那么记录进行后移。

r high+1=high 0r零那么进行一个插入的这样一个部分，那么这是我们对记录序列的那么进行折半查找。那么，这样一个方式。那么，接下来我们再看一下超入排序当中的s hear排序。shell排序呢。它的过程呢，是先取一个正整数did e小于n，然后把所有相隔de的记录呢放在一组。组内呢，进行直接插入排序，然后取d2小于d1，然后重复这样一个操作。分组和操作那么直到了di=1，

那么将所有的记录呢放在一个组中来进行排序，那么我们看一下这个例子。那么最开始呢，我们有这样一些数，那么我们取第一=5，那么我们相隔每相隔五个数，相隔五个数的这样一个数。记录了相隔五个位置的这样一个数呢，就就分为一组啊，比如说49和13，38和27。65和48，97和55，那么76和四那么分为一组，那么按照主类呢？

那么进行排序。那么一趟排序下来了，是这样一个情况方式，那么这个时候呢，我们再去I=did二=3，那么这个时候呢，每隔三个的这样一个数呢，就分为一组那么？进行一个排序，那么组内呢？进行一个排序，每隔三个数的这样一个数呢？每隔三个的这样一个数来进行一个排序组来进行排序，那么是第二场排序，最后呢？

取第三=1，然后呢？对这个数。对这个序列呢，进行一个排序，那么就说每个。就把所有的记录呢放在一个组中为止，然后对这些组组呢进行排序，那么排序最后呢？那么就得到了我们最后的这样一个排序的这样一个结果。s hear排序呢子序列的构成呢，不是简单的逐段分割，而是将相隔每个增量的记录呢，组成一个子序列。七二排序可以提高排序速度，

那么因为分子后n值减小n平方减小，那么所以呢，tn=on^2，所以tn从总体上开始减小了。关键字较小的记录了跳跃式前移，在进行最后一堂经记录为增量为一的排序插入排序时。序列已基本有序增量。序列除法那么无除一以外的公因子，最后一个增量值啊，必须为一。那么，我们来看一下share排序的语句voids how insert？element r数组in tdk对代排序列r做一趟share排插入排序for I=dk+1。inti I小，于等于n。

加加I。I fr I小于ri-dk。那么将。ri的插入有序增量子表。r 0=ri那么暂存在r0中for g=i-dkg大于零。并且呢，r0小于rgg=g-dk。rg+dk呢等于rg那么记录后移查入查找插入位置。rg+dk=r零那么进行一个插入。那么，这是share排序的部分，那么我们再看一下share sort，那么对按增量。序列d0到t- 1对序列对顺序表l做希尔排序的这样一个方式。fork=0 k小于t，

加加t shell insert rd k一套增量呢，为dk的插入排序，那么就是我们shell排序的这样一个方式。呃，接下来我们看一下起泡排序，起泡排序呢，是将第一个记录的关键字与第二个记录的关键字比较，若为逆序r1大于r2，那么则交换，然后比较第二个记录与第三个记录依次类推。直到第n- 1个记录和第n个记录比较为止，那么就是离第一趟起跑排序，结果关键字最大的记录呢，被安置在最后一个记录上。那么，

对前n- 1的记录呢？进行第二趟起发排序，那么结果呢？是关键字。四大的记录呢，被安排在第n- 1个记录位置上，那么就是什么意思呢？也就是说我们起泡排序呢？那么就是说我们首先呢，将第一个关键字与第第二个第一个记录的关键字呢？与第二个关键词比较，如果。第一个关键字记录的关键字呢？比第二个记录的关键字大，那么就交换这两个记录，

然后如果呢？再来比较第二个和第三个关键字，那么依次啊，比较第三个和第四个，第四个和第五个关键字。那么，依次的进行进行这样一个。排序的这样一个部分。依次进行排序的这样一个部分，那么这样呢？我们依次呢？进行这样一个排序，那么这样一个最大的这样一个呢就？排到了就会就会。那么就会。

排到。那么就变到了，我就会移动到最右边的这样一个位置，那么变到在右最右边的这个位置好，接下来呢，再来进行一次。比较那么又再进行比较，那么取找到一个次大的，这样一个值呢，将它放在我们。最后一个位置的前一个，最后一个记录的前一个位置，位置前位位置部分，那么接下来呢，再进行一次比较，

那么再找出一个叫。较大的这样一个数，那么进行一个排序，那么这样呢我们？进行这样一个排序了，最后呢，就能对这样一个记录呢，进行一个按顺序来进行排序，那么说重复这样一个过程呢，在一趟如果直到在一趟排序过程中没有进行交换过的。记录的操作为止。比如说我们再看看这样一个位置，那么这是我们初始的这样一个情况，那么48与49与38相比较，49大于38，

那么48呢？就与38变到38的这样一个位置。49呢，与65进行比较，那么49小于65呢，我们就不改变65呢，小于97，那么也不改变那么97和76比较那么97，大于76，那么再进行一次加。交换那么97呢？变到76的这样一个位置，那么97和13进行比较呢？又要进行一次改变，那么97再和27比较再进行改变，

那么97和30进行比较呢？97再移动到30这样一个位置。那么，接着进行第二次排序，38和49进行比较。那么，49和65进行比较，65和76进行比较，76和13进行比较，那么，76移动到13这个位置，那么，76再和27比较，那么，76再移动到27这个位置。

然后76呢，再和30比较那么76呢，移动到30这样一个位置，那么接下来呢，我们再进行一次排序，那么38与49比较，49与65比较，65与13比较，那么65大于13，那么进行一个交换。那么，65再用27比较，那么移动到27这个位置，那么接下来呢？我们再进行这样一个。

变换38与四四十九比较，49与13比较，那么进行一个交换，49再与27比较，那么进行一个交换，49与30比较了，再进行一个交换。那么，接下来再进行比较，13与38进行交换，进行聚焦38移动到13这个位置，然后38呢移动到27这个位置，再移动到了30这样一个位置。那么，再进行比较，

13，27，38，那么这样呢？不进行？不进行这样一个。变换的改变的这样一个情况，那么这样呢？就完成了这样一个排序的这样一个。顺序的这样一个部分，排序的部分。

		自动登录	找回密码
密码			立即注册