`
dcj3sjt126com
  • 浏览: 1896495 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

排序算法图文视频讲解

阅读更多

排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。

本文将依次介绍上述八大排序算法。

算法一:插入排序

 

插入排序示意图

插入排序是一种最简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

算法步骤

1)将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。

2)从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)

算法二:希尔排序

希尔排序示意图

 

希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的:

  • 插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率
  • 但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位

希尔排序的基本思想是:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。

算法步骤

1)选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;

2)按增量序列个数k,对序列进行k 趟排序;

3)每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。

 

算法三:选择排序

选择排序示意图

选择排序(Selection sort)也是一种简单直观的排序算法。

算法步骤

1)首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置

2)再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。

3)重复第二步,直到所有元素均排序完毕。

 

算法四:冒泡排序

冒泡排序示意图

 冒泡排序Bubble Sort)也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

算法步骤

1)比较相邻的元素。如果第一个比第二个大,就交换他们两个。

2)对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。

3)针对所有的元素重复以上的步骤,除了最后一个。

4)持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

 

算法五:归并排序

归并排序示意图

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

算法步骤:

1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列

2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置

3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置

4. 重复步骤3直到某一指针达到序列尾

5. 将另一序列剩下的所有元素直接复制到合并序列尾

详细介绍:归并排序

算法六:快速排序

快速排序示意图

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。

算法步骤:

1 从数列中挑出一个元素,称为 “基准”(pivot),

2 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。

3 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

详细介绍:快速排序

算法七:堆排序

堆排序示意图

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

堆排序的平均时间复杂度为Ο(nlogn) 。

算法步骤:

1)创建一个堆H[0..n-1]

2)把堆首(最大值)和堆尾互换

3)把堆的尺寸缩小1,并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置

4) 重复步骤2,直到堆的尺寸为1

详细介绍:堆排序

算法八:基数排序

基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。

说基数排序之前,我们简单介绍桶排序:

算法思想:是将阵列分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是 比较排序,他不受到 O(n log n) 下限的影响。
简单来说,就是把数据分组,放在一个个的桶中,然后对每个桶里面的在进行排序。

例如要对大小为[1..1000]范围内的n个整数A[1..n]排序

首先,可以把桶设为大小为10的范围,具体而言,设集合B[1]存储[1..10]的整数,集合B[2]存储   (10..20]的整数,……集合B[i]存储(   (i-1)*10,   i*10]的整数,i   =   1,2,..100。总共有  100个桶。

然后,对A[1..n]从头到尾扫描一遍,把每个A[i]放入对应的桶B[j]中。  再对这100个桶中每个桶里的数字排序,这时可用冒泡,选择,乃至快排,一般来说任  何排序法都可以。

最后,依次输出每个桶里面的数字,且每个桶中的数字从小到大输出,这  样就得到所有数字排好序的一个序列了。

假设有n个数字,有m个桶,如果数字是平均分布的,则每个桶里面平均有n/m个数字。如果

对每个桶中的数字采用快速排序,那么整个算法的复杂度是

O(n   +   m   *   n/m*log(n/m))   =   O(n   +   nlogn   –   nlogm)

从上式看出,当m接近n的时候,桶排序复杂度接近O(n)

当然,以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的  ,实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中,那就退化成一般的排序了。

前面说的几大排序算法 ,大部分时间复杂度都是O(n2),也有部分排序算法时间复杂度是O(nlogn)。而桶式排序却能实现O(n)的时间复杂度。但桶排序的缺点是:

1)首先是空间复杂度比较高,需要的额外开销大。排序有两个数组的空间开销,一个存放待排序数组,一个就是所谓的桶,比如待排序值是从0到m-1,那就需要m个桶,这个桶数组就要至少m个空间。

2)其次待排序的元素都要在一定的范围内等等。

 

 总结

各种排序的稳定性,时间复杂度、空间复杂度、稳定性总结如下图:

 

关于时间复杂度:

(1)平方阶(O(n2))排序
各类简单排序:直接插入、直接选择和冒泡排序;

(2)线性对数阶(O(nlog2n))排序
  快速排序、堆排序和归并排序;
(3)O(n1+§))排序,§是介于0和1之间的常数。

       希尔排序
(4)线性阶(O(n))排序
基数排序,此外还有桶、箱排序。

 

关于稳定性:

稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序

不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序

 

转自: http://www.cricode.com/3212.html

 

视频: 在6分钟内形象地演示15种排序算法

 

 

舞动的排序算法

分享到:
评论

相关推荐

    排序算法 - 直接插入排序(图文超详细)

    直接插入排序是一种基础且常用的排序算法,它的工作原理可以直观地理解为手动整理扑克牌的过程。在本篇文章中,我们将深入探讨...通过本文的图文详细讲解,希望能帮助读者更好地理解直接插入排序的工作机制和应用场景。

    c语言函数和算法图文PPT课件.pptx

    1. **排序算法**:如冒泡排序、选择排序、插入排序、快速排序和归并排序。它们各自有不同的性能特性和适用场景。 2. **搜索算法**:包括线性搜索和二分搜索。线性搜索适用于未排序的数组,而二分搜索则适用于已排序...

    图文讲解Java中实现quickSort快速排序算法的方法

    快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法,通过选取一个基准元素,将待排序序列分为两部分,一部分的所有元素都小于基准,另一部分的所有元素都大于基准,...

    数据机构与算法系列代码及讲解集合

    7. **图的遍历与排序**:详细讲解了深度优先搜索(DFS)和广度优先搜索(BFS),以及拓扑排序算法的实现。这些算法是处理图和网络分析中的核心算法。 8. **图算法**:包括Kruskal、Prim算法和Dijkstra算法等。这些...

    图文讲解选择排序算法的原理及在Python中的实现

    ### 选择排序算法详解 #### 一、选择排序的基本概念 选择排序(Selection Sort)是一种简单直观的比较排序算法。其工作原理是首先在未排序序列中找到最小(或最大)元素,存放到排序序列的起始位置,然后,再从...

    c语言函数和算法图文PPT学习教案.pptx

    本教程将详细讲解C语言中的函数和算法,这两个概念是理解和掌握C语言编程的关键。 **函数在C语言中的角色** 函数是C语言中组织代码的基本单元,它封装了一段特定功能的代码,可以被程序的其他部分多次调用。函数的...

    算法设计与分析电子教案

    排序算法如冒泡排序、插入排序、快速排序、归并排序以及查找算法如顺序查找、二分查找等,都是基础且实用的算法,我们将深入学习其原理和应用。 十、数据结构与算法的结合 本章将讨论如何根据问题特性选择合适的...

    多元宇宙算法MVO优化随机森林分类预测建模工具(Matlab版)图文详解及效果展示,多元宇宙算法MVO优化随机森林做二分类和多分类预测建模 程序内注释详细直接替数据就可以使用 程序语言为matla

    多元宇宙算法MVO优化随机森林分类预测建模工具(Matlab版)图文详解及效果展示,多元宇宙算法MVO优化随机森林做二分类和多分类预测建模。 程序内注释详细直接替数据就可以使用。 程序语言为matlab。 程序直接运行可以...

    电信设备-信息技术课的冒泡算法演示装置.zip

    冒泡排序算法是一种基础且经典的排序算法,常用于教学和理解排序原理。在信息技术课程中,它是学生们初次接触算法时的常见示例。这个“电信设备-信息技术课的冒泡算法演示装置.zip”文件,很显然,包含了关于冒泡...

    数据结构C++版(图文精华版)

    8. **排序算法**:包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等,它们是数据结构中重要的一部分,影响着数据处理的效率。 9. **查找算法**:如二分查找、线性查找、哈希查找等,用于在数据结构...

    完整图文版教程 优质的Python基础入门教程 讲解清晰 PPT课件 06、Python内置数据结构2 (共50页).pptx

    Python提供了各种算法实现的基础,如排序、搜索等,理解算法对于高效编程至关重要。 10. **文件操作**:Python提供了简单的方法读写文件,包括打开、读取、写入、关闭文件,以及处理文件异常。 11. **模块**:模块...

    C++知识图谱(xmind原生文件+全1408主题+图文代码内嵌)

    内容概要:本C++知识图谱为原生xmind文件,可二创,包含13个主题:C++基础、类和对象、内存管理、模板、IO流、继承、多态、C++11、异常、智能指针、特殊类设计、C++类型转换、STL、数据结构与算法。 适合人群:C++...

    大学计算机应用基础PPT模板.pptx

    6.2基本算法介绍,可能会涉及排序、搜索等常见算法的实现。 ### 第七章:计算机信息安全 7.1信息安全相关知识,讲解信息安全的重要性,介绍常见的威胁和防护措施。7.2计算机安全防护,会探讨防病毒、防火墙、加密...

    数据结构教程(第5版)李春葆等

    5. **排序与查找**:快速排序、归并排序、堆排序、冒泡排序、插入排序等都是常见的排序算法,它们各有优缺点,适用于不同的场景。查找算法有顺序查找、二分查找、哈希查找等,哈希表提供近乎即时的查找速度。 6. **...

    数据结构完美教程(含近百个演示动画)

    例如,你可以看到动态演示栈的“后进先出”(LIFO)特性,队列的“先进先出”(FIFO)行为,以及排序算法如冒泡排序、快速排序的过程。这些动画对于理解和记忆数据结构的运作规律非常有帮助。 此外,树形数据结构的...

    计算机大纲

    第十一章 数据结构:涵盖了数据的表示和操作,线性表、顺序存储结构和链式存储结构,栈和队列,数组,树和二叉树,图,排序算法和查找方法。 第十二章 软件工程基础:这部分内容讲解了软件工程的基本概念,软件生命...

    微机课件微机课件微机课件

    微机课件通常包括图文教程、视频讲解、实验指导、习题解答等内容,形式多样,便于学习者根据自身需求选择适合的学习方式。 1. **计算机硬件**:微机课件首先会介绍计算机的基本组成部分,如中央处理器(CPU)、内存...

    《计算机导论》作者祁亨年—PPT.rar

    5. **算法与数据结构**:基础算法如排序和搜索,数据结构如数组、链表、栈、队列和树的介绍。 6. **网络通信**:TCP/IP协议栈,包括物理层、数据链路层、网络层、传输层和应用层的功能;IP地址、MAC地址和域名系统...

Global site tag (gtag.js) - Google Analytics