合并排序(Merge Sort)算法,稳定、快速的排序算法
合并排序(Merge Sort)算法是非常通用的排序算法,是稳定排序,即便在最差的情况下也还有 O(nlogn) 的时间复杂度。
MagicLen · https://magiclen.org
本站也提供繁體中文版。切換到繁體中文版
分类
算法的原理解说与程序实作,包含排序、搜索、图形走访与动态规划等类型,说明算法的运作方式与性能,并附上多种编程语言的范例程序。
共 33 篇文章
合并排序(Merge Sort)算法是非常通用的排序算法,是稳定排序,即便在最差的情况下也还有 O(nlogn) 的时间复杂度。
希尔排序(Shell Sort)算法是插入排序(Insertion Sort)算法的改良版。它解决了插入排序法一次只能把元素移动一个索引距离的问题,加入间距(gap)的概念来分批并分组完成插入排序法,有效提升原本插入排序法的速度。
鸡尾酒排序(Cocktail Sort)算法又称为摇晃排序(Shaker Sort)算法、双向冒泡排序(Bidirectional Bubble Sort)算法,顾名思义,它是冒泡排序(Bubble Sort)算法的变体,将原本单向走访的冒泡排序改为双向,用以解决使用冒泡排序法时,串行中未排序的一端其实已经大致排序好,却又不能尽快把它完成的情形。
插入排序(Insertion Sort)算法,是基本的排序算法,是学习编程语言最先需要学会的排序算法之一。插入排序法的用途广泛,除了可以用来将新元素添加到已存在且已排序好的串行并维持其排序外,还可以用来排序尚未排序的串行。而且其排序结果是稳定的。
冒泡排序(Bubble Sort)算法又称为泡沫排序算法,是基本的排序算法,是学习编程语言最先需要学会的排序算法之一。顾名思义,就是它的排序方式如同气泡一般,不断将最大的元素挤出(移动)到串行最尾端,当所有元素都被挤出后,排序就完成了!而且排序结果是稳定的。
选择排序(Selection Sort)算法是最基本的排序算法,是学习编程语言最先需要学会的排序算法之一。它可以按照元素值的大小序次,一一将最小值、第二小值等等的元素排入串行中的正确索引位置内。
快速排序(Quick Sort)算法又称为划分交换排序(Partition-Exchange Sort)算法,是实用性很高的排序算法,它可以在 O(nlogn) 的时间复杂度完成排序,虽然是不稳定排序,但它的速度完全可以弥补这个缺点。
Bogo 排序(Bogo Sort)算法又称为猴子排序(Monkey Sort)算法,顾名思义,是非常愚蠢的排序算法,就像是请猴子帮忙排序一样。
计数排序(Counting Sort)算法是不需进行比较的排序算法,顾名思义,它会去数元素的数量来进行排序。这种排序法只需要线性时间和空间的复杂度就可以完成排序,比时间复杂度为 O(nlogn) 的算法还快,而且作法也不会太难。虽然如此,计数排序法并不算是常见的排序算法,因为它只能用来排序已知数值范围的串行(由于要直接对应串行的索引值,所以这组数值通常会是一组整数)。举例来说,已知串行中的每个元素...
快速选择(Quickselect)算法是利用快速排序(Quick Sort)算法,在排序串行的同时,选择出串行中第 K 小或是第 K 大的元素。若我们只想要从串行中找出一个第 K 小或是第 K 大元素,使用快速选择法会比使用快速排序法来得快很多,因为前者不需要把串行的排序完整做完,平均只需线性时间即可找到结果。