19.第19节课第9章排序

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

w的bubble sort。element r数组in tni nti=n。while I大于1 last exchange index=1 for。g=1 g小于ig加加if。rg+1小于rg，那么swap rg rg+1。last exchange index=g。I=nux in change index。那么，这就是我们排序的这样一个排序的这样一个方式。那么这样呢，就是我们最开始的。这样一个排序的使用的这样一个方式。好，我们看一下这个语句inti=n。

I大于一=1=1=1g小于ig加加。那么g从一开始呢，进行比较向后进行比较if呢g+1大于小于grg。swap rg rg+1，然后呢？last exchange index=g那么g呢？赋给这样一个last exchanged。最后呢，把exchange index呢赋给I。那么，再来进行这样一个循再来进行这样一个循环循环的这样一个部分。那么，这个我们来看一下这样一个算法的，这样一个分析，那么时间复杂度呢？

那么。是我们的on的平方，那么最好的情况呢？比较n- 1次移动次数是零。最坏的情况是例数比较次数呢，是二分之n平方减n移动次数呢，是二分之一n平方减n，那么这是我们。实现复算法，复算法的这样一个情况，接下来我们看一下快速排序。快速排序呢，它是通过一趟排序将代排序呢，分割成两独立的两部分，其中一部分关键字的记录呢，

均比另一部分关键字的记录。小那么这个分别呢？对这两部分记录呢？进行排序，以达到整个序列有序，那么具体实现呢？是选定一个中间数作为参考。所有元素的与之比较小的调到左边，大的调到右边，那么中间数呢？可以是第一个数，最后一个数，中间一个数，任何一个数的，那么我们看一下。

那么最开始呢，我们这里的。low指向49 low到开始的位置，还有呢，是我们最后面的这个位置，然后呢？我们这样一个二选的，这样一个二十二十七的，这样一个部分。那么27啊。那么，最开始等于49。49了，那么和27进行这样一个。交换的这样一个部分，

那么最开始呢，是我们选的二四四九，那么49呢，那么我们进行排序。那么这个时候了呃呃，这个时候了49了。那么27呢？那么就二和49这样一个变换，这这样一个运用的这样一个部分，然后呢？是我们的。65来的进行变换。然后是13，接下来是97，那么最后呢？

49放在这个位置。那么就完成一趟排序了，那么小的呢，就放在左边，大的呢，就放在右边，那么再进行排序，快速排序，那么我选择27那么小小的放在左边，大的放在右边。然后选择76小的放在左边，大的放在右边，那么快速排序结束了，那么就是我们这样一个排序的，这样一个结果。

我们快速排序了主体算法时间运算量呢，用为on o log 2n划分子区函划分子区函数运算量呢，用为on。所以总的时间复杂度呢，为n×log 2n，那么它比冒号排序呢，要好好的好的，这样一个情况，好的好的，这样一些部分。那么。当原文件关键字有序的时候呢，快速排序的时间复杂出了on的平方，这种情况下呢，快速排序了并不快。

那么，接下来我们看一下简单选择排序，简单选择排序呢？是在代排的数据中选出最大的元素，放在其最终的位置。那么，首先呢，通过n- 1次关键字的比较，从n个记录中选出关键字最小的记录，将它与第一个记录交换。再通过n- 2次比较，与从剩余的n- 1的记录中选出关键字四小的记录。将它与第二个记录进行交换。那么重复这样的操作，共进行n- 1套后呢？

排序结束，那么我们看一个例子，最先呢？那么最下来，我们是49，48呢？38呢？我们选择38是最小是小的这样一个部分，那么49呢？那么最表示这样一个记录的这样一个运动情况。那么是这样一个。选择了。用注。记录的这样一个。记录的这样一个数值，

那么就是说我们最开始呢？我们选的是49，那么49呢？是这样一个记录的。去记标记了这样一个数字的这样一个记录部分，然后是呢，选择38，38呢，那么接下来选择65那么来看呢，97那么76。那么13那么13呢？就和我们的找到我们的13，那么最后最后看到我们的27。那么13呢？是最小的一个数，

将它放在我们的。最左边，然后49呢，与它进行交换，那么这是第一趟排序的结果，那么第二趟呢，我们再找38。语语当中呢，最小这样一个数，那么我们找到的呢是27那么放在。这个最左边的旁右边的这样一个部分，那么第三趟呢，我们再找38那么第四趟呢，找了49那么最后找65最后找76那么最后找97那么最后呢，那么完成了这样一个排序。

好吧，我们来看一下它的算法的，这样一个分析。那么，它的时间复杂度呢？是on的平方最好的情况呢？移动零次最坏的情况呢？移动n- 1次，它的比较次数呢？是sigma I=1到n- 1 n-i。二，它等于二分之n平方减n。最后呢，我们看一下堆排序。我们看一下。

什么是堆堆排堆排序的这样一个部分堆的定义呢？若n个元素的序列ia 1a2 an满足AI小于a2I。AI小于等于2I2a2 I+1或者AI大于等于a2I或者并且AI大于等于a2 I+1。主要分别称，该序列是a1a2 an。为小根堆和。大更注意。那么，从堆的定义可以看出来，堆实质上是满足这些性质的完全二叉树。那么就是说，二叉树中任意几非叶子节点呢？均小于。或者大于。他的这样一个孩子。

学点。那么，我们来看一下这两个堆呢？左边的这这边呢，是一个大根堆，那么这边呢，是一个小根堆。那么，若在输出堆顶的最小值或者最大值后，使得剩余的n- 1个元素的序列呢？又重。建成了一个堆，那么得到n个元素的次小值次大值，那么这样反复进行呢，便能得到一个有序序列，

那么这个序列呢，称为堆排序。好吧，我们看一下堆的调整如何在输出堆顶元素后调整剩余元素，为一个新的堆呢小根堆呢是在输出堆顶元素后以堆中最后一个元素代替。然后将根结点值呢，与左右指数的根结点值进行比较，并将其中用小值来进行交换，那么重复这样一个操作，直到叶子节点，那么得到新的堆，那么称这个。从堆到叶子节点的调整过程呢，称为筛选，那么我们看一下。

我们输出最后一个元素，并代替那么。那么，输出这样一个输出根的，并以最后一个元素代替了吗？输出13，那么我们以97来代替，那么与它的左右孩子进行比较，与较小者进行交换，那么与38约27呢进行交换。那么这个时候呢？97呢？再与较小者四四九呢进行交换。那么，进行这样一个交换的部分，

那么这是一个小根堆，那么接下来我们看一下怎么建堆的这样一个方式，那么由于堆呢？实际上是一个线性表，那么我们可以呢？顺序存储一个堆。比如说我们以这样一个实例来介绍，介绍介绍一个建小分队的过程，那么有关键字49，38，65，97，七六一三。二七四九的一组记录将其按关键词来调整一个小跟堆。那么，

我们首先看一下。那么，首先呢，从调整二分之n个元素开始，将该元素呢为根的二叉树要调整为堆。然后呢，将序号为二分之n减一的根结点呢，为根的二叉树呢，调整为堆。那么，再以序号为二分之n减二的根节点呢？的节点为根的二叉树来调整为堆。那么，再以。现在将以序号为二分之n减三的节点为根的二叉树要调整为对。

那么，这是我们调整堆的这样一个方式。那么最后呢？我们看一下堆排序，那么若对一个无序序列建堆，然后输出根重复该过程呢？就可以实现一个有无序序列输出的有限序列？实际上呢，堆排序就是利用完全二叉树的副结点与。这几点之间的内在联系来进行排序的，然后我们来看一下堆排序的算法whip sort element 2数组。I for I等于二分之ni，大于等于一。I减减。for I=ni大于一加减减swap ir er I hit just re ri- 1，

那么我们看一下这个语句，首先呢，是I=inter I。for I等于二分之ni，大于等于一I减减，那么rin那么建初始堆for I等于ni大于一I减减进行n减一趟排序。re ri跟你最后一个元素交换，然后呢？just ri ei- 1对r1到ri- 1呢？重新进行建堆。堆排序的时间呢，主要耗费在建初始堆和调整新建堆的时候的这样一个反复筛选上。堆排序在最坏的情况下呢，其实时间复杂度呢，也为on log 2n，

这是堆排序的优点，另外呢，堆排序仅是一个记录大小。记录大小共交换用的辅助存储空间。比如说含八个元素的无序序列，那么我们进行这样一个排序的，这样一个排序的，这样一个情况，那么进行这样一个交换的，这样一个变换的，这样一个情况。那么，这样一个排序了，这样一个。这样一个。

这个排序的这样一个运用的这样一个。变换的这样一个运用情况，这样一个方式。那么，接下来我们看一下归并排序，归并呢，是将两个或两个以上的有序表呢，组成一个新的有序表。那么比如说。有没有二路规并排序排序过程呢？是设置初始序列，还有n个记录就可以看成n个有序的子序列。设每个子序列长度为一两两，合并得到二分之n，向下取整的长度或或为二或一的有序子序列。

再两两合并如此重复了得到一个长度为n的有序序列为止。那么，我们来看一下规并排序，首先呢，两两组，两两组，两两呢。两两合并。那么，再进行排序。那么这样。每两个呢进行合并，那么进行排序，那么排序之后呢，再进行合并，

再进行排序，最后呢，再进行一次合并，那么再排序。那么这样呢，最后就得到了，我们顺这样一个排排序的，这样一个最后的，这样一个排列，这样一个顺序的，这样一个情况，我们来看一下归并排序它的语句v的verge。elements r数组element加数组interi interm intern for g=m+1 k=ik小于m，并且呢，kg小于等于n。

加加k。I if sri点k小于等于srg点ktrk=sri加加。else trk=srg加加if I，小于等于mtr kn。等于s RIM。if g小于等于NTR kn=sr。jn那么我们看一下这个语句，而我们这个语句呢，是将有序的s RIM和srm+1。到n归并为有序的trin。我们首先呢，for ij=m+1 k=I for I=I等于小于等于m，并且呢g小于等于n加加k。将s中的记录了由小到大的并入加if sri点k小于。srg点k。

CK呢等于sri加加。else.trk=srg加加，那么if I小于等于mtr kn等于。s RIM就是将剩余的srm赋值到tri fg小于n。tr kn=s rgn将剩余的s rgn呢复制到tr，这是我们这样一个排序的，这样一个归并排序的，这样一个方式。接下来我们看一下基数排序，基数排序呢，那么是我们关关，我们看一下这样一个多关键字排序。多观建设排序方法呢，是我们有没有最高位排序优先法，

那么先对最高位数字。关键字k1排序将序列呢分成若干子序列，每个子序列呢都有相同的k1值，然后让每个子序列呢对次关键字k2进行排序。若分成若干较小的子序列，依次重复，那么直到了对每个子序列的最低位关键字kd排序。最后呢，将所有子序列呢，依次连在一起，成为一个有序序列。好吧，我们看一下最低位优先法，从低位低最低位关键字kd进行排序。然后呢，

再对高一位的关键字排序依次重复，只是对最高位的关键字k1排序后便成为一个有序序列，那么这是我们最高位优先法以及第最低位优先法的方式。最高位优先法呢和最低位优先法呢，它有不同的这样一个地方，按照msd排序呢，必须将程序逐层分割成为若干子序列，然后对各子序列的分别排序。按照lsd排序了，不必分成为子序列，所以每个关键字呢都是整个序列参加排序，并可不通过关键字比较，而通过若干次分配收集与实现实现排序。我们再看一下链式基数，排序基数排序呢，

借助分配和收集对单独及关键资料进行排序的一种方式，链式基数排序呢，用链表作为存储结构的基础排序。我们来看一下链式技术排序的排序步骤，我们设置十个队列fi和ri，分别为第I个队列的头指针和尾指针。第一趟分配了对最低位关键词进行排序，改变记录的指针值，将链表的记录呢分配到十个链队列中，每个队列记录的关键词各位相同。第一趟收集的是改变所有飞空队列的队尾的指针域，并且指向下一个飞空队列的对头记录，重新将十个队列呢连成一个链表。那么重复这样一个步骤呢？进行第二趟，

第三趟分配和收集分别呢？对十位和百位进行最后呢？得到。这样一个有序序列，那么这是我们面试基数的这样一个排序的，这样一个方式，那么接下来呢？我们来比较一下各种排序方法的这样一个情况。我们按时间性能来看一下，按平均的时间性能来分呢，有三类排序方法，时间复杂度呢，为on log n的方法呢，有快速排序规定排序和。堆排序，

其中呢，快速排序了，最好时间复杂度为on的平方呢，有直接插入排序，其他排序和简单排序。其中呢，以直接插入最好，那么特别呢是对那些关键字近似有序的序列呢，因为那么比较比较适适当。时间复杂度呢，为on的排序方法呢，有基数排序，当代排记录，按关键字相对有序的时候呢，直接插入排序和启发排序呢，

能达到on的时间复杂度。而对于快速排序的而言，那么这是不好的情况，此时的时间复杂性能呢？退化为on的平方。简单选择排序，堆排序和规定排序的时间性能呢？不随记录序列中关键词的分组而改变。那么，我们来看一下它的空间性能，那么空间性能呢？那么指的是排序过程中所需的辅助空间的大小。所有简单排序方法的和堆排序的空间复杂度呢？都为o1快速排序，为on log nno log n。

为债所需的辅助空间归并排序所需的辅助空间最多，那么其空间复杂多了为on。面试技术排序呢，需负责队列首尾指针，其工作复杂度呢，为or d接下来我们看一下排序方程的防缺方法的稳定性。那么，排序方法呢？稳定呢？是是指两个关键字相等的记录，它们在序列中的相对位置，在排序前和经过排序后呢？没有改变。那么，我们来看一下哪些？

排序方法呢，是稳定的哪些哪哪些排序方法呢？不是稳定的排序方法，那么我们排稳定的排序方法呢，有直接插入排序。折半插入排序。冒泡排序。简单选择排序规定，排序和基础排序，那么这些呢，都是稳定的排序方法。而我们不稳定的排序方法呢？由我们的希尔排序。快速排序堆排序，那么这些呢？

都是不稳定的排序方法，那么对于不稳定的排序方法呢？只要能举出一个实例来说明呢？那么它是不稳定的，那么就就可就可以了，就可以这种情况就可以。好同学们，今天呢，我们为大家介绍了排序这一部分的内容，那么接下来呢，我们再进行一些总结。那么，我们来看一下，那么对于我们排序来说。一般情况呢。

如果排序过程中的比较是在两个相邻关键字之间进行的，则排序方法呢是稳定的，那么稳定性呢是由方法本身决定的。不稳定的排序方法而言，不管其描述形式如何，那么我们呢？可以。那么我们可以呢？看是否能举出一个不稳定的这样一个例子来，这一步举出一个例子，那么对大多数情况下呢，排序是按记录的主关键字进行的。那么，对排序的方法呢？是否稳定？

那么，不去看这样一个实现的使用情况？那么，若排序的关键字呢？是按次关键字进行的，那么则必须用稳定的排序方法。那么，这是呢？我们今天呢？那么所讲的内容那么同学们呢？下来的时候呢？那么再看一下这些部分，那么进行一个了解和掌握。好，我们今天的课呢，

就讲到这里好，谢谢大家。

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