6、快速排序
(1)基本思想:选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描,将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
(2)实例:
上图中将待排序列分成两部分,一部分比基准元素小,一部分大于基准元素,然后对这两部分重复上图的求解过程。
(这只是快速排序的一种实现方式,个人认为比较容易理解)
7、归并排序
(1)基本排序:归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
(2)实例:
8、基数排序
(1)基本思想:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。
(2)实例:
稳定性说明:排序前,2(或者更多)个相等的数在序列的前后位置顺序和排序后它们在序列中的前后位置顺序一样。
实例:
待排序数列:5,4,8,6,1,8,7,9
排序结果:1,4,5,6,7,8,8,9
稳定:1,4,5,6,7,8,8,9
不稳定:1,4,5,6,7,8,8,9
说明:对比红色的8和紫色的8,看他们排序前后的位置。排序前,红8在紫8前面,如果排序后红8仍然在紫8前面,则排序算法稳定,否则不稳定。
现在我们分析一下8种排序算法的稳定性。
(请网友结合前面的排序基本思想来理解排序的稳定性(8种排序的基本思想已经在前面说过,这里不再赘述)不然可能有些模糊)
(1)直接插入排序:一般插入排序,比较是从有序序列的最后一个元素开始,如果比它大则直接插入在其后面,否则一直往前比。如果找到一个和插入元素相等的,那么就插入到这个相等元素的后面。插入排序是稳定的。
(2)希尔排序:希尔排序是按照不同步长对元素进行插入排序,一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,稳定性就会被破坏,所以希尔排序不稳定。
(3)简单选择排序:在一趟选择,如果当前元素比一个元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了。光说可能有点模糊,来看个小实例:858410,第一遍扫描,第1个元素8会和4交换,那么原序列中2个8的相对前后顺序和原序列不一致了,所以选择排序不稳定。
(4)堆排序:堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1,
n/2-2, ...这些父节点选择元素时,有可能第n/2个父节点交换把后面一个元素交换过去了,而第n/2-1个父节点把后面一个相同的元素没有交换,所以堆排序并不稳定。
(5)冒泡排序:由前面的内容可知,冒泡排序是相邻的两个元素比较,交换也发生在这两个元素之间,如果两个元素相等,不用交换。所以冒泡排序稳定。
(6)快速排序:在中枢元素和序列中一个元素交换的时候,很有可能把前面的元素的稳定性打乱。还是看一个小实例:6
4 4 5 4 7 8 9,第一趟排序,中枢元素6和第三个4交换就会把元素4的原序列破坏,所以快速排序不稳定。
(7)归并排序:在分解的子列中,有1个或2个元素时,1个元素不会交换,2个元素如果大小相等也不会交换。在序列合并的过程中,如果两个当前元素相等时,我们把处在前面的序列的元素保存在结果序列的前面,所以,归并排序也是稳定的。
(8)基数排序:是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序,最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以是稳定的。
8种排序的分类,稳定性,时间复杂度和空间复杂度总结:
分享到:
相关推荐
此文档中不紧包括8大排序3大查找算法的基本思想,而且还附上有每种算法实现的源码,还有清楚明了的图文解析,更加易懂。对于一个程序员来讲,要编写出优秀的代码同样要扎实的基础,如果排序和查找算法学的不好,怎么...
Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找 Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找
每天都在叫嚣自己会什么技术,什么框架,可否意识到你每天都在被这些新名词、新技术所迷惑,.NET、XML等等技术固然诱人,可是如果自己的基础不...废话不多说,本文要介绍的这些排序算法就是基础中的基础,程序员必知!
Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找(同步到博客).doc
本书作者介绍了一些有用但很少被讨论的算法,它们可用于语音查找、日期和时间例程(直到公元1年)、B树和索引文件、数据压缩、任意精度的算术、校验和与数据验证,并且还最全面地介绍了查找例程、排序算法和数据结构...
本书(程序员常用算法)重点关注的是实用,立即可用的代码,并且广泛...日期和时间例程(直到公元1年)、B树和索引文件、数据压缩、任意精度的算术,校验和与数据验证,并且全面地介绍了查找例程、排序算法和数据结构。..
1.2.10 DBA与程序员 第2章 数据表的创建和管理 2.1 数据类型 2.1.1 整数类型 2.1.2 数值类型 2.1.3 字符相关类型 2.1.4 日期时间类型 2.1.5 二进制类型 2.2 通过SQL语句管理数据表 2.2.1 创建数据...
专业的程序设计人员常被称为程序员。 2.程序设计=数据结构+算法 Programming = Data Structures + Algorithm 3.程序设计:为计算机处理问题编制一组指令集。 算法:处理问题的策略。 数据结构:问题的数学模型。...
第3章 散列 3.1 散列的概念 3.2 散列函数 3.3 冲突解决方法 3.3.1 线性再散列法 3.3.2 非线性再散列法 3.3.3 外部拉链法 3.4 性能问题 3.5 资源和参考资料 第4章 查找 4.1 查找的特征 ...
1.2.10 DBA与程序员 第2章 数据表的创建和管理 2.1 数据类型 2.1.1 整数类型 2.1.2 数值类型 2.1.3 字符相关类型 2.1.4 日期时间类型 2.1.5 二进制类型 2.2 通过SQL语句管理数据表 2.2.1 创建数据...
• 第四章 查找匹配 o 4.1 有序数组的查找 o 4.2 行列递增矩阵的查找 o 4.3 出现次数超过一半的数字 • 第五章 动态规划 o 5.0 本章导读 o 5.1 最大连续乘积子串 o 5.2 字符串编辑距离 o o o 5.3 格子取数 5.4 ...
1.2.10 DBA与程序员 第2章 数据表的创建和管理 2.1 数据类型 2.1.1 整数类型 2.1.2 数值类型 2.1.3 字符相关类型 2.1.4 日期时间类型 2.1.5 二进制类型 2.2 通过SQL语句管理数据表 2.2.1 创建数据...
详细介绍了直接插入排序、希尔排序、简单选择排序、堆排序、冒泡排序、快速排序、归并排序、基数排序等
程序员面试题精选 100 题(01)-把二元查找树转变成排序的 双向链表 题目:输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点, 只调整指针的指向。 程序员面试题精选 100 题...
【作 者】(美)DonaldE.Knuth著 【内容提要】 关于算法分析的这多卷论著已经长期被公认为经典计算机科学的定义性描述。迄今已出版的完整的三卷已经组成了程序设计理论和实践...第3卷为排序和查找,分“排序”和“...
无论您是Java编程的初学者还是有经验的程序员,该资源都将为您提供有价值的指导和支持,帮助您掌握Java中实现有序矩阵查找的方法。我们相信,该资源将成为想提高算法设计技能的Java程序员的宝贵参考资料。
1.2.10 DBA与程序员 第2章 数据表的创建和管理 2.1 数据类型 2.1.1 整数类型 2.1.2 数值类型 2.1.3 字符相关类型 2.1.4 日期时间类型 2.1.5 二进制类型 2.2 通过SQL语句管理数据表 2.2.1 创建数据...
1.2.10 DBA与程序员 第2章 数据表的创建和管理 2.1 数据类型 2.1.1 整数类型 2.1.2 数值类型 2.1.3 字符相关类型 2.1.4 日期时间类型 2.1.5 二进制类型 2.2 通过SQL语句管理数据表 2.2.1 创建数据...
日期和时间例程(直到公元1年)、B树和索引文件、数据压缩、任意精度的算术,校验和与数据验证,并且全面地介绍了查找例程、排序算法和数据结构。.. 本书只要求读者具有C语言的初级知识以及基本代数的相关知识。源代码...