当前位置:首页 » 操作系统 » 八种算法全套

八种算法全套

发布时间: 2024-12-08 17:15:55

㈠ 八大经典排序算法原理及实现

该系列文章主要是记录下自己暑假这段时间的学习笔记,暑期也在实习,抽空学了很多,每个方面的知识我都会另起一篇博客去记录,每篇头部主要是另起博客的链接。

冒泡排序算法应该是大家第一个接触的算法,其原理都应该懂,但我还是想以自己的语言来叙述下其步奏:

按照计算时间复杂度的规则,去掉常数、去掉最高项系数,其复杂度为O(N^2)
冒泡排序及其复杂度分析

空间复杂度就是在交换元素时那个临时变量所占的内存

给定一个整数序列{6,1,2,3,4},每完成一次外层循环的结果为:

我们发现第一次外层循环之后就排序成功了,但是还是会继续循环下去,造成了不必要的时间复杂度,怎么优化?

冒泡排序都是相邻元素的比较,当相邻元素相等时并不会交换,因此冒泡排序算法是稳定性算法

插入排序是对冒泡排序的一种改进

插入排序的思想是数组是部分有序的,再将无序的部分插入有序的部分中去,如图:
(图片来自 这里 )

空间复杂度就是在交换元素时那个临时变量所占的内存

插入排序的优化,有两种方案:

文章后面会给出这两种排序算法

由于插入排序也是相邻元素的比较,遇到相等的相邻元素时不会发生交换,也不会造成相等元素之间的相对位置发生变化

其原理是从未排序的元素中选出最小值(最大值)放在已排序元素的后面

空间复杂度就是在交换元素时那个临时变量所占的内存

选择排序是不稳定的,比如 3 6 3 2 4,第一次外层循环中就会交换第一个元素3和第四个元素2,那么就会导致原序列的两个3的相对位置发生变化

希尔排序算是改良版的插入排序算法,所以也称为希尔插入排序算法

其原理是将序列分割成若干子序列(由相隔某个 增量 的元素组成的),分别进行直接插入排序;接着依次缩小增量继续进行排序,待整个序列基本有序时,再对全体元素进行插入排序,我们知道当序列基本有序时使用直接插入排序的效率很高。
上述描述只是其原理,真正的实现可以按下述步奏来:

希尔排序的效率取决于 增量值gap 的选取,这涉及到数学上尚未解决的难题,但是某些序列中复杂度可以为O(N 1.3),当然最好肯定是O(N),最坏是O(N 2)

空间复杂度就是在交换元素时那个临时变量所占的内存

希尔排序并不只是相邻元素的比较,有许多跳跃式的比较,难免会出现相同元素之间的相对位置发生变化,所以希尔排序是不稳定的

理解堆排序,就必须得先知道什么是堆?

二叉树的特点:

当父节点的值总是大于子结点时为 最大堆 ;反之为 最小堆 ,下图就为一个二叉堆

一般用数组来表示堆,下标为 i 的结点的父结点下标为(i-1)/2;其左右子结点分别为 (2 i + 1)、(2 i + 2)

怎么将给定的数组序列按照堆的性质,调整为堆?

这里以建立最小堆为示例,

很明显对于其叶子结点来说,已经是一个合法的子堆,所以做堆调整时,子节点没有必要进行,这里只需从结点为A[4] = 50的结点开始做堆调整,即从(n/2 - 1)位置处向上开始做堆调整:

由于每次重新恢复堆的时间复杂度为O(logN),共N - 1次重新恢复堆操作,再加上前面建立堆时N / 2次向下调整,每次调整时间复杂度也为O(logN),二次操作时间相加还是O(N logN)。故堆排序的时间复杂度为O(N * logN)。

空间复杂度就是在交换元素时那个临时变量所占的内存

由于堆排序也是跨越式的交换数据,会导致相同元素之间的相对位置发生变化,则算法不稳定。比如 5 5 5 ,堆化数组后将堆顶元素5与堆尾元素5交换,使得第一个5和第三个5的相对位置发生变化

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

快速排序在应该是大家经常看到、听到的算法,但是真正默写出来是有难度的。希望大家看了下面 挖坑填数 方法后,能快速写出、快速排序。

其原理就这么几句话,但是现实起来并不是这么简单,我们采取流行的一种方式 挖坑填数分治法

对于序列: 72 6 57 88 60 42 83 73 48 85

数组变为: 48 6 57 88 60 42 83 73 88 85
再重复上面的步骤,先从后向前找,再从前向后找:

数组变为: 48 6 57 42 60 72 83 73 88 85
可以看出a[5]前面的数字都小于它,a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了

空间复杂度,主要是递归造成的栈空间的使用:

快速排序的优化主要在于基准数的选取

快速排序也是跨越式比较及交换数据,易导致相同元素之间的相对位置发生变化,所以快速排序不稳定

前面也说了二分查找排序是改进的插入排序,不同之处在于,在有序区间查找新元素插入位置时,为了减少比较次数提高效率,采用二分查找算法进行插入位置的确定
具体步骤,设数组为a[0…n]:

二分查找插入位置,因为不是查找相等值,而是基于比较查插入合适的位置,所以必须查到最后一个元素才知道插入位置。
二分查找最坏时间复杂度:当2^X>=n时,查询结束,所以查询的次数就为x,而x等于log2n(以2为底,n的对数)。即O(log2n)
所以,二分查找排序比较次数为:x=log2n
二分查找插入排序耗时的操作有:比较 + 后移赋值。时间复杂度如下:

二分查找排序在交换数据时时进行移动,当遇到有相等值插入时也只会插入其后面,不会影响其相等元素之间的相对位置,所以是稳定的

白话经典算法排序
冒泡排序选择排序
快速排序复杂度分析
优化的插入排序

㈡ 几种排序算法的比较

一、八大排序算法的总体比较

4.3、堆的插入:

每次插入都是将新数据放在数组最后。可以发现从这个新数据的父结点到根结点必然为一个有序的数列,然后将这个新数据插入到这个有序数据中

(1)用大根堆排序的基本思想

先将初始数组建成一个大根堆,此对为初始的无序区;

再将最大的元素和无序区的最后一个记录交换,由此得到新的无序区和有序区,且满足<=的值;

由于交换后新的根可能违反堆性质,故将当前无序区调整为堆。然后再次将其中最大的元素和该区间的最后一个记录交换,由此得到新的无序区和有序区,且仍满足关系的值<=的值,同样要将其调整为堆;

..........

直到无序区只有一个元素为止;

4.4:应用

寻找M个数中的前K个最小的数并保持有序;

时间复杂度:O(K)[创建K个元素最大堆的时间复杂度] +(M-K)*log(K)[对剩余M-K个数据进行比较并每次对最大堆进行从新最大堆化]

5.希尔排序

(1)基本思想

先将整个待排序元素序列分割成若干子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序(因为直接插入排序在元素基本有序的情况下,效率很高);

(2)适用场景

比较在希尔排序中是最主要的操作,而不是交换。用已知最好的步长序列的希尔排序比直接插入排序要快,甚至在小数组中比快速排序和堆排序还快,但在涉及大量数据时希尔排序还是不如快排;

6.归并排序

(1)基本思想

首先将初始序列的n个记录看成是n个有序的子序列,每个子序列的长度为1,然后两两归并,得到n/2个长度为2的有序子序列,在此基础上,再对长度为2的有序子序列进行两两归并,得到若干个长度为4的有序子序列,以此类推,直到得到一个长度为n的有序序列为止;

(2)适用场景

若n较大,并且要求排序稳定,则可以选择归并排序;

7.简单选择排序

(1)基本思想

第一趟:从第一个记录开始,将后面n-1个记录进行比较,找到其中最小的记录和第一个记录进行交换;

第二趟:从第二个记录开始,将后面n-2个记录进行比较,找到其中最小的记录和第2个记录进行交换;

...........

第i趟:从第i个记录开始,将后面n-i个记录进行比较,找到其中最小的记录和第i个记录进行交换;

以此类推,经过n-1趟比较,将n-1个记录排到位,剩下一个最大记录直接排在最后;

热点内容
安卓上哪里下大型游戏 发布:2024-12-23 15:10:58 浏览:186
明日之后目前适用于什么配置 发布:2024-12-23 14:56:09 浏览:51
php全角半角 发布:2024-12-23 14:55:17 浏览:826
手机上传助手 发布:2024-12-23 14:55:14 浏览:730
什么样的主机配置吃鸡开全效 发布:2024-12-23 14:55:13 浏览:828
安卓我的世界114版本有什么 发布:2024-12-23 14:42:17 浏览:708
vbox源码 发布:2024-12-23 14:41:32 浏览:275
诗经是怎么存储 发布:2024-12-23 14:41:29 浏览:657
屏蔽视频广告脚本 发布:2024-12-23 14:41:24 浏览:417
php解析pdf 发布:2024-12-23 14:40:01 浏览:816