您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

算法入门篇:简单的排序算法

时间:2019-11-04 10:25:55  来源:  作者:
作者:dorseyCh
来源:http://www.imooc.com/article/264180

很久之前有过一次面试,被问到一个问题,能不能写一个冒泡排序?说实话,尽管在这之前曾经写过不少比这个更加复杂的处理逻辑,但很悲剧的是我当时真不知道什么是冒泡排序。。。只知道如果让我排序某段混乱序列,能很快搞定就是了,最后的结果显而易见,我被赤裸裸的鄙视了。。。(连个性能最差的冒泡排序思维都不会,要你何用= =),第二天回去,看了啥是排序,真的捶胸了半天,名字叫得那么好听,原来是这个。。。

简单的排序算法基本是下面这几种,其中的话冒泡排序,选择排序,插入排序是性能最差,实际应用基本不用但也是最简单,能提高你算法信心的几个小排序方式。

 

算法入门篇:简单的排序算法

 

 

下面的话,我们一个个来实现,假如我们要让[1, 2, 32, 23, 321, 45, 8, 90, 227, 99]从小到大排列。

既然要排列,我们第一反应肯定是比较,大的放后边小的放前边,对吧,两两进行比较。

1

冒泡排序

 

先拿第1第2个数比较,谁大谁后面,接着第2个跟第3个,还是谁大谁后面,继续第3第4,第4第5。。。这样进行了一轮之后,你是不是可以很肯定,最后的那个数一定是最大的?接下来混乱的序列就少了一位了对吧?就继续剩下的序列继续上面的一轮。而你仔细想一想这个过程,12, 23, 34,...有没有种演唱会现场一波波人浪冒出来的感觉?嗯,没有错,这就是冒泡,像一块软绵绵的地毯,里面有一颗玻璃珠在滚动,滚着滚着这个地毯就有序了。= =嗯,这就是冒泡排序。下面看看它的代码是怎样。

算法入门篇:简单的排序算法

 

 

2

选择排序

 

上面的是最简单的排序了,人的第一直觉就能产生的一种解决问题的思路。但是呢?思维肯定是不断进步的,不可能一直停滞不前的,为什么呢?人浪排序不是很好吗?额不对,冒泡排序不是还不错嘛?简单直观,但是你要知道,有些人的脑回路不一定如此直观,他们解决问题的思路是这样的:

他觉得,我每次比较后符合要求的都去交换,有些处于中间值的,不是要不断的被交换?不是很浪费时间?我能不能选出这段序列中最大的那个数,然后放到最后边?

答案是肯定的,怎么做呢?既然是序列,代码中是数组,那有一个下标,我先把第一个数据给存起来,这个数不断的从第1项比到最后一项,当谁的值比他大时,他就把他的值存起来,这样一轮过后,它拿到了最大值,这时候就把选出的这个数,仍最后。接下来那个第二大的仍这个最后的前面一项,一直到完成整个序列。这样这种通过不断选出剩余项最大值的方法叫做选择排序。

一起看看它的代码是怎样的吧:

算法入门篇:简单的排序算法

 

 

这种选择排序,虽说没有了交换的过程,但又多了赋值的过程,实际上并不比冒泡强哪去,也还是那样,理论上的性能能稍微好那么一丢丢,基本可以忽略不计。

3

插入排序

 

跟冒泡和选择同一时期的,还有一个插入排序,插入排序的方式更加的简单,你想一个问题,假如你现在手上多了一个空的数组,那你会怎样排序?是不是先把第一个放到空数组后,往后拿过来的数都跟这个新数组的各个数比较,插入到某两个数(只需注意大的在你后面,小的在你前面就OK)之间,但是呢,实际上,新创建一个数组的开销是不算小的,没理由一个简单的算法都要这样做,所以可以这样:

抽出第2个数,这样就变成了前半段(你的新数组),跟后半段(原来的大数组),这样不断的把你后半段的数,插入到前半段,前半段大的就往后挪腾位置给新数插入,对吧?是不是也可以实现你想要的?一起看看这个插入排序是怎样实现的吧。

 

算法入门篇:简单的排序算法

 

 

上面这3种排序,你是不是代码中要有两个for循环,而且是完全的遍历,一步步走的,对吧?一个用于每一轮的比较(这时候只是进行了某一个数的比较,或者说确定了某一个数在整个数组中它所处的位置),一个用于遍历整个数组,把每个成员都拿出来遛一遛。对吧,那就是n²,也就是时间复杂度O(n²)(个人理解,不一定非常准确,但个人认为还是比较好理解的,不至于说得很复杂)

既然有了前人的摸索,后人站 们这些的思维又是怎样的呢?

4

希尔排序

 

比如说我们在说到无论是冒泡还是插入排序,有没有注意到“一个个的往后挪”这样的字眼?为什么要一个个的挪呢?能不能一大段一大段的挪?打个比方,如果排序一个1~100的数组(原序列是100,99,98...1),这个时候100是在第1位,光排完100这个数你就得挪99次,得调用上面的swap方法99次,但比如说把这个一个个挪切换成一半一半的挪,比如第一个数100跟51比较后交换然后99跟52比较,是不是就非常大的迈了一大步?这些迈完后,再把间隔变成25,再来迈,虽说可能迈偏对吧?没事最后做一个步伐为1的修正就好了。而这,就是鼎鼎有名的希尔排序

看一下希尔排序是怎么实现的哈:

 

算法入门篇:简单的排序算法

 

5

归并排序

 

看了以前上面一个个的挪实在太费劲了,我要比较,我不挪,我直接就拿出来,分成小组,每个小组自己先弄成有序的,再汇总,这样这种分而治之思想的实际上就是归并排序。它的核心排序点在哪呢?你分治就分治嘛,怎么分?又怎么治?就是我为神马用这个排序,这个数据通过这个方法过一下就变有序了?核心就在于小组——这个小组的成员最多只有2个,比如说数组的长度是8,就分成了4个2,7就分成3个2跟1个1,多个数我们一眼排不出序来,两个总可以吧?没错,这就是分。那怎么治呢?我们看下下面比如说我现在A,B两个小组已经完成了他们内部的排序(他们的长度都是4)

A B

1568 2479

 

算法入门篇:简单的排序算法

 

 

那一起看看它是怎么实现的吧:

 

算法入门篇:简单的排序算法

 

 

6

快速排序

 

这个时候呢,也诞生了另一个思想,个人看来也是一种分类,它是怎样的呢?有点类似于体育课的时候高个子站后面矮个子站前面,教练没办法一开始就一眼看出谁高谁矮对吧?那么多人,肯定是随便逮一个,来以他为基准,排序!!!一声令下,小个的站这家伙的前边,大个的站后边,对吧?而这就是快速排序的核心思想。有点像二分法,不过这个二分法有点不同,它不是按长度,它是按类,你高就占那边,矮就站这边,把整体分成两部分,那矮的那块还能不能再分,那是当然,矮的那块再随便找一个,再分,这样就完成了一个排序的内部过程。(左边小,右边大,那当长度为3的时候不就实现有序了吗?嗯,这就是快排的核心思想)

具体的代码怎么实现呢?

这样很直观的我们就想到,嘿我弄两个数组,装高个子跟矮个子,然后再concat回来对吧?当然记得把中间那家伙给放进去,别漏了。看下下面:

 

算法入门篇:简单的排序算法

 

 

嗯,是不是很直观?呵呵,但是要知道,排序,特别是排序数据非常多的时候,最考验的就是性能,而代码中left = [], right = [];还递归,这个内存的开销是非常大的,所以我们不这样,那怎么做呢?

算法入门篇:简单的排序算法

 

 

上面的虽然没重新创建数组,但是呢?通过交换,比如说大于参考点的放左边,小于的放右边,那我直接等待一下,一个从左边开始扫描,一个从右边,当左边扫描到比参考数大的数时,结束扫描,右边也扫描,当有一个数比参考数小时,就结束扫描,这时候把这两个数交换一下,是不是就实现了小的在前面大的在后面,你说,可他们不一定在参考点两边啊?没错,这个时候继续扫描,等到i和j在某个点相遇的时候,把这个参考点的值跟那个位置的值换一下,不就实现两边一边大一边小嘛。、

嗯,有了一个了,当然得有无数次,左边那块再继续做这个事,右边的也一样,当右边跟左边再加上中间的数长度刚好为3或小于3的时候不就OK了?

 

7

堆排序

 

这时候还有一个性能也很不错的排序,用到完全二叉树的方式来的。

它又是怎么想的?卧槽(没文化的我只会这一句= =),不就个排序,非得弄那么多乱七八糟的?嗯,怎么说呢,这是一种思想,先不扯远一起看看具体是怎么样的吧。

堆,有大顶堆跟小顶堆之分,这里就不扯概念了,那个官方讲得很详细嗯也很官方= =,简单理解一下就是一个金字塔,你是帮主,你下面还有左右护法四大天王八大金刚十六罗汉,嗯就这样一直下去,而所谓的大顶堆就是作为帮主的你是住塔顶的,小顶堆呢?则相反,你们帮最小最小的那个小弟就在那。大概是这样哈:

这个就是所谓的大顶堆,生活中是不是太常见了?(理解为主,请忽略图= =)

 

算法入门篇:简单的排序算法

 

 

那它又是怎么做到排序的?

 

算法入门篇:简单的排序算法

 

 

还记得选择排序是怎么排序的?就是选择一个最大数不断的插入到最后的对吧?但是选择最大数的那个过程是通过不断的比较,一个个位置挪动去得到的,那能不能跳着走?跳着扫描。实际上,分成堆只是让我们更好理解。

一起看看代码是怎么样实现的吧:

 

算法入门篇:简单的排序算法

 

 

 

下面是做的一个简单的性能测试

 

① 普通插入排序与快速排序的速度对比(数据量20万):

 

算法入门篇:简单的排序算法

 

 

 

可以看到在20万随机数(0-10000)的排序中,快排所花的时间不足100个时间单位,而插入排序要超过50000个。普通的O(n²)的性能与最好情况O(nlogn)的快排是完全没法比(数据量越庞大结果越明显)。

② 希尔排序与快速排序对比(数据量2000万):

 

算法入门篇:简单的排序算法

 

 

由于这两个排序都是极不稳定的,但是从测试的几次结果看,希尔排序的性能会略微优于快排(语言:JAVAscript)

③归并排序与希尔排序

算法入门篇:简单的排序算法

 

 

归并排序相对于希尔,快排的不稳定来说,归并排序最好跟最坏的情况均是nlogn,是稳定且快捷的排序算法。利用的正是完全二叉树的思维模式。

④堆排序与归并排序

 

算法入门篇:简单的排序算法

 

 

也是2000万1-10000的随机数排序。



Tags:排序算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除,谢谢。
▌相关推荐
人生有涯,学海无涯今天跟大家分享一个常用的排序算法——快速排序。我想大家在日常的工作或者面试的时候肯定经常会遇到很多排序算法,而且快速排序算法往往是这里面...【详细内容】
2021-03-04  Tags: 排序算法  点击:(80)  评论:(0)  加入收藏
1. 冒泡排序算法实现(javascript)//冒泡排序算法(javascript)//author:Hengda//arr数组//mode false 升序 ture 降序function bubbleSort( arr, mode ){ var i, j, temp, l...【详细内容】
2021-02-07  Tags: 排序算法  点击:(94)  评论:(0)  加入收藏
用希尔排序法对一组数据由小到大进行排序,数据分别为 69、56、12、136、3、55、46、 99、88、25。例子:(1)自定义函数 shsort(),实现希尔排序。(2) main() 函数作为程序的入口...【详细内容】
2021-01-25  Tags: 排序算法  点击:(96)  评论:(0)  加入收藏
选择排序 选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续...【详细内容】
2020-11-19  Tags: 排序算法  点击:(89)  评论:(0)  加入收藏
今天我们就来讨论面试官最喜欢问到的排序算法吧,从冒泡排序、选择排序、插入排序等十大排序算法的排序步骤、代码实现两个方面入手,彻底搞清实现原理,保证面试道路一路畅通。0...【详细内容】
2020-07-26  Tags: 排序算法  点击:(31)  评论:(0)  加入收藏
今天我们就来讨论面试官最喜欢问到的排序算法吧,从冒泡排序、选择排序、插入排序等十大排序算法的排序步骤、代码实现两个方面入手,彻底搞清实现原理,保证面试道路一路畅通。01...【详细内容】
2020-07-25  Tags: 排序算法  点击:(33)  评论:(0)  加入收藏
1 插入排序算法定义插入排序,一般也被称为直接插入排序。对于少量元素的排序,它是一个有效的算法 。插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好...【详细内容】
2020-06-30  Tags: 排序算法  点击:(27)  评论:(0)  加入收藏
本文来用图文的方式详细讲解了Python十大经典排序算法 —— 插入排序、选择排序、快速排序、冒泡排序、归并排序、希尔排序、插入排序、桶排序、基数排序、计数排...【详细内容】
2020-06-21  Tags: 排序算法  点击:(26)  评论:(0)  加入收藏
常见的内排序算法所谓的内排序是指所有的数据已经读入内存,在内存中进行排序的算法。排序过程中不需要对磁盘进行读写。同时,内排序也一般假定所有用到的辅助空间也可以直接存...【详细内容】
2020-06-15  Tags: 排序算法  点击:(34)  评论:(0)  加入收藏
一、概述:本文给出常见的几种排序算法的原理以及 Java 实现,包括常见的简单排序和高级排序算法,以及其他常用的算法知识。 简单排序:冒泡排序、选择排序、插入排序 高级排序:快速...【详细内容】
2020-05-15  Tags: 排序算法  点击:(36)  评论:(0)  加入收藏
▌简易百科推荐
架构头条 作者 | theinsaneapp.com译者 | 张健欣策划 | 万佳今天,我们会讨论一些不同的东西,例如 Spotify、YouTube、Signal Messenger、Amazon 等科技巨头的推荐算法,以及像 U...【详细内容】
2021-07-15  技术联盟总坛    Tags:推荐算法   点击:(2)  评论:(0)  加入收藏
说起区块链,似乎大家都懂一点,再往细里一问,似乎又都不懂了。比如,你问一个人:为什么要挖矿,挖的到底是啥。怕是没几个明白人。本文就是要给你讲明白!前言人们一说起区块链,就常常说...【详细内容】
2021-07-13  暖男在奋斗的路上    Tags:加密算法   点击:(6)  评论:(0)  加入收藏
2021年5月26日,极狐阿尔法S 华为HI版正式下线,标志着华为进军自动驾驶迈出关键一步,实现了量产。...【详细内容】
2021-07-08  佐思汽车研究    Tags:自动驾驶算法   点击:(9)  评论:(0)  加入收藏
今天讲的是最有深度的抖音算法机制的剖析,解密平台核心算法机制。主要深度讲下抖音是算法机制到底是怎么工作的,我们的帐号标签原型到底是怎么建立起来的,字节跳动的人工智能AI...【详细内容】
2021-07-05  国阜电商    Tags:抖音平台算法   点击:(11)  评论:(0)  加入收藏
RSA非对称加密RSA是一种常用的非对称加密算法,加密和加密使用不同的密钥,常用于要求安全性较高的加密场景,比如接口的验签和接口数据的加密与解密。与非对称加密算法对比,其安全...【详细内容】
2021-07-04  Java架构学习指南  简书  Tags:接口   点击:(12)  评论:(0)  加入收藏
导读:用户标签是个性化推荐、计算广告、金融征信等众多大数据业务应用的基础,它是原始的用户行为数据和大数据应用之间的桥梁,本文会介绍用户标签的构建方法,也就是用户画像技术...【详细内容】
2021-07-02  华章科技    Tags:用户画像   点击:(16)  评论:(0)  加入收藏
随机红包算法,每个人都有自己的实现思路。package com.jmmq.load.jim.algorithm;import java.math.BigDecimal;import java.util.Arrays;import java.util.List;import java....【详细内容】
2021-07-02  非鸽传书  今日头条  Tags:算法   点击:(10)  评论:(0)  加入收藏
在程序员的实际开发中,哈希算法常常能用得到,本文以哈希算法的原理和应用为核心,和大家详细讲解一下哈希算法的概念、常见算法以及原理、在信息安全的应用等等。 一、概念哈希...【详细内容】
2021-06-25  C语言编程    Tags:哈希算法   点击:(26)  评论:(0)  加入收藏
1. 红黑树1.1 红黑树概述红黑树和我们以前学过的AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。不过自从红黑树出来后,AVL...【详细内容】
2021-06-24  Linux天神    Tags:红黑树   点击:(19)  评论:(0)  加入收藏
1. 线性表线性表是一类最简单、最常用的数据结构。简单来说,一个线性表是n个元素的有限序列,其中n≥0,通常表示为(a1,a2,...,an)。其特点是,在非空的数据元素集合中:(1)存在唯一的一个...【详细内容】
2021-06-09  数据人plus  今日头条  Tags:数据结构   点击:(37)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条