【数据结构】排序算法

修修修也

发布于 2024-04-01 16:13:27

660

发布于 2024-04-01 16:13:27

文章被收录于专栏：修也的进阶日记修也的进阶日记

?排序的定义

排序是计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列. 排序的定义: 假设含n个记录的序列为

\left { R_1,R_2,...,R_n \right.\left. \right }

其相应的关键字序列为

\left { \left. K_1,K_2,...,K_n \right } \right.

需确定1,2,...,n的一种排列

,使其相应的关键字满足如下的非递减(或非递增)关系.

K_{p1}\leqslant K_{p2}\leqslant ...\leq K_{pn}

,即使

成为一个按关键字有序的序列

\left { R_{p1},R_{p2},...,R_{pn}\right.\left. \right }

,这样一种操作称为排序.

?排序的稳定性

?稳定性的定义

假设关键字序列为:

,其中

K_i=K_j(1\leqslant i\leqslant n,1\leqslant j\leqslant n,i\neq j)

,且在排序前的序列中

领先于

(即i<j).如果排序后

仍领先于

,则称所用的排序方法是稳定的;反之,若可能使得排序后的序列中

领先

,则称所用的排序方法是不稳定的.

?稳定性的意义

排序稳定性主要是方便我们对一个复杂结构体进行副关键字辅助主关键字进行排序. 如下,是一份模拟考试的成绩单,可以看到,单按总分排名的话,就会出现有两人总分一致,然后并列排名的情况,于是我们为了在排名上区分出二者,就设定了一项规则:如果两人总分数一致,则比较两人语文成绩,语文成绩高则排名在前.像这种有主次性排序条件的多条件排序,我们通常需要借助稳定的排序算法先将数据按照副排序条件进行一次排序,再在此基础上按照主排序条件进行一次排序,这样得到的结果,就能够满足:主排序条件一致的情况下,同样满足副排序条件的数据在前的序列了.

常见的稳定的排序算法有: 直接插入排序,冒泡排序,简单选择排序,归并排序,基数排序
常见的不稳定的排序算法有:希尔排序,快速排序,堆排序,计数排序

?内排序与外排序

根据在排序过程中待排序的记录是否全部被放置在内存中,排序分为:内排序和外排序. 内排序是在排序的整个过程中,待排序的所有记录全部被放置在内存中.外排序是由于排序的记录个数太多,不能同时放置在内存,整个排序过程需要在内外存之间多次交换数据才能进行.

?八大内排序

?冒泡排序

它的基本思想是:

重复走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

算法演示动图如下:

算法单趟排序可视化过程:

有关冒泡排序的具体代码实现: 【数据结构】八大排序之冒泡排序算法

https://blog.csdn.net/weixin_72357342/article/details/129173919?spm=1001.2014.3001.5502

?希尔排序

它的基本思想是:

先选定一个整数,把待排序文件中所有数据分成gap个组,所有距离为gap的数据分在同一组内,并对每一组内的数据进行排序.
重复上述分组和排序的工作,当达到gap=1时,所有数据在统一组内排好序.

算法动图演示如下:

算法单趟排序可视化过程(以gap/=2为例):

有关希尔排序的具体代码实现: 【数据结构】八大排序之希尔排序算法

https://blog.csdn.net/weixin_72357342/article/details/135043566

?直接插入排序

它的基本操作是:

将一个数据插入到已经排好的有序表中,从而得到一个新的,数据数增1的有序表.
直到所有的数据插入完为止,得到一个新的有序序列.

算法动图演示如下:

算法单趟排序可视化过程:

有关直接插入排序的具体代码实现: 【数据结构】八大排序之直接插入排序算法

https://blog.csdn.net/weixin_72357342/article/details/135038521?spm=1001.2014.3001.5502

?简单选择排序

它的基本操作是:

每一次通过n-i次关键字间的比较,从n-i+1个数据中选出关键字最小(大)的数据,并和第i(1≤i≤n)个数据交换
重复n-1次上述操作,直到全部待排序的数据元素排完.

算法动图演示如下:

算法单趟排序可视化过程:

有关简单选择排序的具体代码实现: 【数据结构】八大排序之简单选择排序

https://blog.csdn.net/weixin_72357342/article/details/135059302?spm=1001.2014.3001.5502

?堆排序

它的基本思想是:

将待排序的序列构造成一个大堆.(如果是降序则建小堆)
此时,整个序列的最大值就是堆顶的根结点.将它移走(其实就是我们前面堆实现中的出堆顶操作).
然后将剩余的n-1个序列重新构造成一个堆,这样就会得到n个元素中的次小值(即堆顶).
如此反复执行,就可以得到一个有序的序列了.

算法动图演示: 1.向下调整建堆 逻辑结构:

物理结构:

2.堆排序(升序)

逻辑结构:

物理结构:

算法单趟排序可视化过程:

有关堆排序的具体代码实现: 【数据结构】八大排序之堆排序算法

https://blog.csdn.net/weixin_72357342/article/details/135059322?spm=1001.2014.3001.5502

?快速排序

它的基本思想是:

通过一趟排序将待排数据分割成独立的两部分
其中一部分数据的关键字均比另一部分数据的关键字小
可分别对这两部分数据继续进行排序,以达到整个序列有序的目的.

算法动图演示:

算法单趟排序可视化过程:

有关快速排序的具体代码实现: 【数据结构】八大排序之快速排序算法

https://blog.csdn.net/weixin_72357342/article/details/135059337?spm=1001.2014.3001.5502

?归并排序

归并排序(Merging Sort)就是利用归并的思想实现的排序方法. 它的原理是: 假设初始序列含有n个记录,则可看成是n个有序的子序列,每个子序列的长度为1,然后两两归并,得到\left \lceil \frac{n}{2} \right \rceil(\left \lceil x \right \rceil表示不小于x的最小整数)个长度为2或1的有序子序列;再两两归并,......,如此重复,直至得到一个长度为n的有序序列为止,这种排序方法称为2路归并排序. 算法动图演示如下: