张拓的博客

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到{\displaystyle O(1)}的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。 记载最早拥有排序概念的机器出现在1901至1904年间由赫尔曼·何乐礼发明出使用基数排序法的分类机，此机器系统包括打孔，制表等功能，1908年分类机第一次应用于人口普查，并且在两年内完成了所有的普查数据和归档。 赫尔曼·何乐礼在1896年创立的分类机公司的前身，为电脑制表记录公司（CTR）。他在电脑制表记录公司曾担任顾问工程师，直到1921年退休，而电脑制表记录公司在1924年正式改名为IBM。 概述Insertion Sort 和打扑克牌时，从牌桌上逐一拿起扑克牌，在手上排序的过程相同。 举例： 输入： {5 2 4 6 1 3}。 首先拿起第一张牌, 手上有 {5}。 拿起第二张牌 2, 把 2 insert 到手上 ...

桶排序（Bucket sort）或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（{\displaystyle \Theta (n)}）。但桶排序并不是比较排序，他不受到{\displaystyle O(n\log n)}下限的影响。 桶排序以下列程序进行： 1.设置一个定量的数组当作空桶子。 2.寻访序列，并且把项目一个一个放到对应的桶子去。 3.对每个不是空的桶子进行排序。 4.从不是空的桶子里把项目再放回原来的序列中。 伪代码1234567function bucket-sort(array, n) is buckets ← new array of n empty lists for i = 0 to (length(array)-1) do insert array[i] into buckets[msbits(array[i], k)] for i = 0 to n ...

梳排序（Comb sort）是一种由Wlodzimierz Dobosiewicz于1980年所发明的不稳定排序算法，并由Stephen Lacey和Richard Box于1991年四月号的Byte杂志中推广。梳排序是改良自冒泡排序和快速排序，其要旨在于消除乌龟，亦即在数组尾部的小数值，这些数值是造成冒泡排序缓慢的主因。相对地，兔子，亦即在数组前端的大数值，不影响冒泡排序的性能。 在冒泡排序中，只比较数组中相邻的二项，即比较的二项的间距（Gap）是1，梳排序提出此间距其实可大于1，改自插入排序的希尔排序同样提出相同观点。梳排序中，开始时的间距设置为数组长度，并在循环中以固定比率递减，通常递减率设置为1.3。在一次循环中，梳排序如同冒泡排序一样把数组从首到尾扫描一次，比较及交换两项，不同的是两项的间距不固定于1。如果间距递减至1，梳排序假定输入数组大致排序好，并以冒泡排序作最后检查及修正。 递减率递减率的设置影响着梳排序的效率，原作者以随机数作实验，得到最有效递减率为1.3的。如果此比率太小，则导致一循环中有过多的比较，如果比率太大，则未能有效消除数组中的乌龟。 亦有人提议用{\dis ...

鸡尾酒排序，也就是定向冒泡排序，鸡尾酒搅拌排序，搅拌排序（也可以视作选择排序的一种变形），涟漪排序，来回排序或快乐小时排序，是冒泡排序的一种变形。此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。 伪代码将一个序列由小到大进行排序：12345678910111213141516171819202122232425262728293031function cocktail_sort(list, list_length){ // the first element of list has index 0 bottom = 0; top = list_length - 1; swapped = true; while(swapped == true) // if no elements have been swapped, then the list is sorted { swapped = false; for(i = bottom; i < top; i = i + 1) & ...

快速排序（英语：Quicksort），又称分区交换排序（partition-exchange sort），简称快排，一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序{\displaystyle n}个项目要{\displaystyle \ O(n\log n)}（大O符号）次比较。在最坏状况下则需要{\displaystyle O(n^{2})}次比较，但这种状况并不常见。事实上，快速排序{\displaystyle \Theta (n\log n)}通常明显比其他算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地达成。 算法快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。 步骤为： 1.挑选基准值：从数列中挑出一个元素，称为“基准”（pivot）， 2.分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成， 3.递归排序子序列：递归地将小于基 ...

冒泡排序（英语：Bubble Sort）又称为泡式排序，是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 冒泡排序对{\displaystyle n}个项目需要O({\displaystyle n^{2}})的比较次数，且可以原地排序。尽管这个算法是最简单了解和实现的排序算法之一，但它对于包含大量的元素的数列排序是很没有效率的。 冒泡排序是与插入排序拥有相等的渐近时间复杂度，但是两种算法在需要的交换次数却很大地不同。在最坏的情况，冒泡排序需要{\displaystyle O(n^{2})}次交换，而插入排序只要最多{\displaystyle O(n)}交换。冒泡排序的实现（类似下面）通常会对已经排序好的数列拙劣地执行（{\displaystyle O(n^{2})}），而插入排序在这个例子只需要{\displaystyle O(n)}个运算。因此很多现代的算法教科书避免使用冒泡排序，而用插 ...

内省排序（英语：Introsort）是由David Musser在1997年设计的排序算法。这个排序算法首先从快速排序开始，当递归深度超过一定深度（深度为排序元素数量的对数值）后转为堆排序。采用这个方法，内省排序既能在常规数据集上实现快速排序的高性能，又能在最坏情况下仍保持{\displaystyle O(n\log n)}的时间复杂度。由于这两种算法都属于比较排序算法，所以内省排序也是一个比较排序算法。 在快速排序算法中，一个关键操作就是选择基准点（Pivot）：元素将被此基准点分开成两部分。最简单的基准点击择算法是使用第一个或者最后一个元素，但这在排列已部分有序的序列上性能很糟。Niklaus Wirth为此设计了一个快速排序的变体，使用处于中间的元素来防止在某些特测序列上性能退化为{\displaystyle O(n^{2})}的状况。这个3基准中位数选择算法从序列的第一，中间和最后一个元素获取中位数来作为基准，虽然这个算法在现实世界的数据上性能表现良好，但经过精心设计的“破解序列”仍能大幅降低此变体算法的性能。这样就有攻击者精心设计序列发送到因特网服务器以进行拒绝服务（DoS） ...

在计算机科学里，偏排序是排序算法的一个放宽的变种。全排序返回的列表中，每个元素都按一定顺序出现，而偏排序返回的列表中，仅有 k 个最小(或 k 个最大)的元素是有序的。其他元素(第 k 个最小之外) 也可能被就地排序后存储，也可能被舍弃。这常见于流式偏排序中。偏排序最普遍的实例是计算某个列表的 “Top 100”。 就索引而言，偏排序后的列表中，对每一个从 1 到 k 的索引 i ，都有第 i 个元素与全排列后列表保持相同位置：偏排序后列表的第 i 个元素包含了输入列表中的第 i 个顺序统计量。 离线问题基于堆的解决方案当 k 固定时，堆允许一个简单的单次偏排序：向一个最大堆中插入输入中的前 k 个元素，然后遍历剩余的元素，依次加到堆中，并删除最大的那个。每个插入操作耗时 O(log k) ，总耗时达 O(n log k)。该算法适合求解第 k 小的值与配置在线算法. 另一个选择是为所有值构建一个最小堆(构建过程耗费 O(n)) 并将堆头移除，重复 K 次, 每次移除操作耗费 O(log n). 在该情况下，总的算法复杂度为 O(n+klog n)。 划分选择的解决方案进一步的放宽要求 ...

侏儒排序（英语：Gnome Sort）或愚人排序（英语：Stupid Sort）是一种排序算法，最初在2000年由伊朗计算机工程师Hamid Sarbazi-Azad（谢里夫理工大学计算机工程教授）提出，他称之为“愚人排序”。此后Dick Grune也描述了这一算法，称其为“侏儒排序”。此算法类似于插入排序，但是移动元素到它该去的位置是通过一系列类似冒泡排序的移动实现的。从概念上讲侏儒排序非常简单，甚至不需要嵌套循环。它的平均运行时间是O(n2)，如果列表已经排序好则只需O(n)的运行时间。 解释下面是侏儒排序的伪代码，其中使用的数组是下标从零开始的：12345678procedure gnomeSort(a[]): pos := 0 while pos < length(a): if (pos == 0 or a[pos] >= a[pos-1]): pos := pos + 1 else: swap a[pos] and a[pos-1] pos := pos - ...

Timsort 是一种混合稳定的排序算法，源自合并排序和插入排序，旨在较好地处理真实世界中各种各样的数据。它使用了 Peter Mcllroy 的”乐观排序和信息理论上复杂性”中的技术，参见 第四届年度ACM-SIAM离散算法研讨会论文集，第467-474页，1993年。 它由 Tim Peters 在2002年实现，并应用于 Python编程语言。该算法通过查找已经排好序的数据子序列，在此基础上对剩余部分更有效地排序。 该算法通过不断地将特定子序列（称为一个 run ）与现有的 run 合并，直到满足某些条件为止来达成的更有效的排序。 从 2.3 版本起，Timsort 一直是 Python 的标准排序算法。 它还被 Java SE7 Android platform, GNU Octave, 谷歌浏览器, 和 Swift 用于对非原始类型的数组排序。 原文地址：https://zh.wikipedia.org/wiki/Timsort 在知识共享 署名-相同方式共享 3.0协议之条款下提供