面试前你必须知道的三个排序算法-阿里云开发者社区

开发者社区> 技术小能手> 正文

面试前你必须知道的三个排序算法

简介:
+关注继续查看

今天分享的是三种排序算法,在面试、实际编程中经常会碰到和使用到的,我会带领大家从分析排序算法技巧上以及代码实现上全面理解这一知识点的掌握。

6a552207cb14bdbf2a9a77281300afbe19f1df88

一、如何分析一个「排序算法」

1. 执行效率

① 最好、最坏、平均时间复杂度

在分析算法的好坏时,要分别说出最好、最坏、平均时间复杂度的同时,也要说出最好、最坏时间复杂度对应排序的原始数据是什么样的。

② 复杂度系数、常数、低阶

时间复杂度反应的是数据规模 n 很大的时候的一个增长趋势,它表示的时候会忽略系数、常数、低阶 ,小规模数据除外。

③ 比较次数和移动次数

基于比较的排序算法,在分析算法效率时,我们要考虑到元素的比较和元素的移动。

2. 内存消耗

算法的内存消耗可以通过空间复杂度来衡量,排序算法也不例外。我们引用一个名词叫做「原地排序」,就是指特定空间复杂度是 O(1) 的排序算法。

3. 稳定性

如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变,就叫做「稳定排序」。

二、冒泡排序

1、算法思想

每次冒泡对相邻的两个元素进行比较,看是否满足大小关系,不满足就进行互换,一次冒泡会让至少一个元素移动到它应该在的位置。有 n 个数据,需要重复 n 次。

559868f100a88f0c3d2c3974f0a26bf6c02617cf

2、算法优化

当某次冒泡过程已经没有数据交换时,说明已经达到完全有序,不用再执行后续的冒泡操作。

3、代码实现


1// 冒泡排序,a 表示数组,n 表示数组大小
2public void bubbleSort(int[] a, int n) {
3 if (n <= 1) return;
4
5 for (int i = 0; i < n; ++i) {
6 // 提前退出冒泡循环的标志位
7 boolean flag = false;
8 for (int j = 0; j < n - i - 1; ++j) {
9 if (a[j] > a[j+1]) { // 交换
10 int tmp = a[j];
11 a[j] = a[j+1];
12 a[j+1] = tmp;
13 flag = true; // 表示有数据交换
14 }
15 }
16 if (!flag) break; // 没有数据交换,提前退出
17 }
18}

4、问题思考

①是否为原地排序

冒泡的过程只涉及相邻数据的交换操作,只需要常量级的临时空间,所以它的空间复杂度为 O(1),是一个原地排序算法。

②是否为稳定排序

在冒泡排序中,只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性,当有相邻的两个元素大小相等的时候,我们不做交换,相同大小的数据在排序前后不会改变顺序,所以冒泡排序是稳定的排序算法。

③最好、最坏以及平均时间复杂度

最好的情况是数据已经排好序,我们只进行一次冒泡排序就可以了,最好时间复杂度为 O(n) 。最坏的情况是,要排序的数据刚好是倒序排列的,我们只进行 n 此冒泡操作,所以最坏的时间复杂度为 O(n²),平均时间复杂度为 O(n²)。

三、插入排序(Insertion Sort)

1、算法思想

我们将元素分为两个区间,未排序区间和已排序区间。我们要做的就是在未排序区间取出元素与已排序区间元素进行比较插入到适当位置,以此类推,直到未排序区间元素为空为止(顺序为从后向前比较

073d2fe3bee59e8aba3726e4babaf66c09c5c6a2

2、代码实现


1// 插入排序,a 表示数组,n 表示数组大小(从小到大进行排序)
2public void insertionSort(int[] a, int n) {
3 //如果数组大小为 1 直接返回
4 if (n <= 1) return;
5 //否则进行插入排序
6 for (int i = 1; i < n; ++i) {
7 int value = a[i];
8 int j = i - 1;
9 // 查找插入的位置
10 for (; j >= 0; --j) {
11 if (a[j] > value) {
12 a[j+1] = a[j]; // 数据移动
13 } else {
14 break;
15 }
16 }
17 a[j+1] = value; // 插入数据
18 }
19}

3、问题思考

① 是否为原地排序?

答:插入排序的运算并不需要额外的存储空间,所以空间复杂度是 O(1),是一个原地排序算法。

② 是否为稳定排序?

答:在插入排序中,对于值相同的元素,我们会将后边出现的元素插入到前边出现的元素的后边,所以插入排序是稳定排序。

③ 最好、最坏、平均时间复杂度?

答:

最好的情况就是数据元素已经排好序,最好的时间复杂度为 O(1) ,

如果数组是倒序的,每次插入都相当于在数组的第一个位置插入新的数据,需要移动大量的数据,最坏的时间复杂度是 O(n²)。

我们在数组中插入数据的平均时间复杂度为 O(n),对于插入排序来说我们每次就相当于数组插入一个新的数据,循环执行n次插入数据,所以平均时间复杂度为 O(n²)。

四、选择排序

1、算法思想

和插入排序有点相似,将在未排序期间寻找到最小的数据,并将其放到已排好区间的元素的尾部。

2、问题思考

① 是否为原地排序

因为,数组中的两个元素需要相互交换,需要用一个变量来存储交换值,选择排序的空间复杂度为O(1),所以,是一种原地排序算法。

② 是否为稳定排序

选择排序每次都要找到剩余未排序元素的最小值,并和前边的元素交换位置,这样破坏了稳定性。所以说,选择排序是一种不稳定的排序算法。

③ 最好、最坏以及平均时间复杂度

选择排序的最好情况就是已经是一组有序数据,最好的时间复杂度为 O(1),最坏的情况就是 O(n²)。平均时间复杂度就是 O(n²)。

3、代码实现


1// 选择排序,a表示数组,n表示数组大小
2 public static void selectionSort(int[] a, int n) {
3 if (n <= 1) return;
4 for (int i = 0; i < n; ++i) {
5 // 查找最小值
6 int minIndex = i;
7 int minValue = a[i];
8 for (int j = i; j < n; ++j) {
9 if (a[j] < minValue) {
10 minValue = a[j];
11 for (int i = 0; i < n - 1; ++i) {
12 // 查找最小值
13 int minIndex = i;
14 for (int j = i + 1; j < n; ++j) {
15 if (a[j] < a[minIndex]) {
16 minIndex = j;
17 }
18 }
19 if (minIndex == i)
20 continue;
21 // 交换
22 int tmp = a[i];
23 a[i] = a[minIndex];
24 a[minIndex] = tmp;
25 }
26 }

五、实际应用中为什么插入排序应用最为广泛

冒泡排序不管怎么优化,元素交换的次数是一个固定值,是原始数据的逆序度。插入排序是同样的,不管怎么优化,元素移动的次数也等于原始数据的逆序度。

从代码实现上来看,冒泡排序的数据交换要比插入排序的数据移动要复杂,冒泡排序需要 3 个赋值操作,而插入排序只需要 1 个。


1冒泡排序中数据的交换操作:
2if (a[j] > a[j+1]) { // 交换
3 int tmp = a[j];
4 a[j] = a[j+1];
5 a[j+1] = tmp;
6 flag = true;
7}
8
9插入排序中数据的移动操作:
10if (a[j] > value) {
11 a[j+1] = a[j]; // 数据移动
12} else {
13 break;
14}

有兴趣的小伙伴可以编几个数据自己测试一下。

虽然冒泡排序和插入排序在在时间复杂度上是一样的,都是 O(n²),我们希望把性能优化做到极致,首选插入排序。

六、重点掌握

今天重点掌握的内容是三种排序的「分析方法」,不必要死记硬背。另一个方面就是实际应用中用到最多就是「插入排序」。


原文发布时间为:2018-11-14

本文作者:不甘平凡的码农

本文来自云栖社区合作伙伴“Web项目聚集地”,了解相关信息可以关注“Web项目聚集地”。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
10003 0
RSA与AES混合加密算法的实现
RSA与AES加密算法所产生的密钥数不一样,它们是如何进行加密的呢? 接收方生成RSA密钥对,将其中的RSA公钥传递给发送方(接收方与发送方建立连接是需要认证的,SSL/TLS协议可以确保RSA公钥的安全完整),然后用RSA公钥对AES密钥进行加密,加密后的结果传递给接收方,接收方用RSA私钥解密后,得到AES密钥,最后使用AES密钥解密,从而达到安全互通数据的目的。(如下图所示)
1569 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
10880 0
RANSAC算法在图像拼接上的应用的实现
关于算法原理请参考《基于SURF特征的图像与视频拼接技术的研究》。一、问题提出         RANSAC的算法原理并不复杂,比较复杂的地方在于“建立模型”和“评价模型”。我们经常看到的是采用“直线”或者“圆”作为基本模型进行“建立”,而采用所有点到该“直线”或“圆”的欧拉距离作为标准来“评价”(当然是越小越好)。
2290 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
13798 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
11879 0
Silverlight中非对称加密及数字签名RSA算法的实现
RSA算法是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作,也很流行。它的安全性是基于大整数素因子分解的困难性,而大整数因子分解问题是数学上的著名难题,至今没有有效的方法予以解决,因此可以确保RSA算法的安全性。
669 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
7327 0
+关注
技术小能手
云栖运营小编~
7208
文章
9
问答
文章排行榜
最热
最新
相关电子书
更多
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载
《2021云上架构与运维峰会演讲合集》
立即下载