wylu

Keep It Simple, Stupid

桶排序(Bucket sort)或箱排序(Bin sort),是一个排序算法,工作的原理是将数组分到有限数量的桶里。每个桶再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。桶排序是 鸽巢排序 的一种归纳结果。

阅读全文 »

计数排序(Counting sort)是一种稳定的线性时间排序算法。该算法于1954年由 Harold H. Seward 提出。计数排序使用一个额外的数组 C ,其中第 i 个元素是待排序数组 A 中值等于 i 的元素的个数。然后根据数组 C 来将 A 中的元素排到正确的位置。

阅读全文 »

在计算机科学中,堆排序(Heapsort)是一种基于比较的排序算法。Heapsort 可以被认为是一种改进的选择排序:像该算法一样,它将输入分为排序区域和未排序区域,并通过提取最大元素并将其移动到排序区域来迭代缩小未排序区域。改进包括使用堆数据结构而不是线性时间搜索来找到最大值。

阅读全文 »

堆(Heap)是计算机科学中的一种特别的树状数据结构。若是满足以下特性,即可称为堆:“给定堆中任意节点 P 和 C,若 P 是 C 的母节点,那么 P 的值会小于等于(或大于等于) C 的值”。

堆始于 J._W._J._Williams 在 1964 年发表的堆排序(heap sort),当时他提出了二叉堆树作为此算法的数据结构。堆在 Dijkstra 等几种有效的图形算法中也非常重要。

堆是一种称为优先级队列的抽象数据类型的最有效实现,实际上优先级队列通常被称为“堆”,而不管它们如何实现。

阅读全文 »

快速排序(Quicksort),又称分区交换排序(partition-exchange sort),简称快排,是一种高效的排序算法。由英国计算机科学家 Tony Hoare 于 1959 年开发并于 1961 年发表,至今它仍然是一种常用的排序算法。事实上,如果实施得当,它可以比归并排序、堆排序快两到三倍。

阅读全文 »

归并排序(Merge sort),是创建在归并操作上的一种基于比较的排序算法。1945 年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。

阅读全文 »

希尔排序(Shellsort),是一种就地比较排序。它可以被看作是交换排序(冒泡排序)或插入排序(插入排序)的泛化。该方法首先对彼此相距很远的元素对进行排序,然后逐步缩小要比较的元素之间的差距。从距离较远的元素开始,它可以比简单的最近邻交换更快地将一些不合适的元素移动到位。1959 年,Donald Shell 出版了第一个版本。Shellsort 的运行时间严重依赖于它使用的间隙序列。对于许多实际的变体,确定它们的时间复杂度仍然是一个悬而未决的问题。

阅读全文 »

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

阅读全文 »

在计算机科学中,选择排序(Selection sort)是一种排序算法,切确的说是就地比较排序。它具有 \(O(n^2)\) 时间复杂度,使其在大型列表上效率低下,并且通常比类似的插入排序更差。选择排序因其简单性而着称,并且在某些情况下具有优于更复杂算法的性能优势,特别是在辅助存储器有限的情况下。

阅读全文 »