wiki搬运,排序算法

稳定的排序[编辑]

  • 冒泡排序(bubble sort)— {\displaystyle O(n^{2})}wiki搬运,排序算法
  • 插入排序(insertion sort)—{\displaystyle O(n^{2})}wiki搬运,排序算法
  • 鸡尾酒排序(cocktail sort)—{\displaystyle O(n^{2})}wiki搬运,排序算法
  • 桶排序(bucket sort)—{\displaystyle O(n)}wiki搬运,排序算法;需要{\displaystyle O(k)}wiki搬运,排序算法额外空间
  • 计数排序(counting sort)—{\displaystyle O(n+k)}wiki搬运,排序算法;需要{\displaystyle O(n+k)}wiki搬运,排序算法额外空间
  • 归并排序(merge sort)—{\displaystyle O(n\log n)}wiki搬运,排序算法;需要{\displaystyle O(n)}wiki搬运,排序算法额外空间
  • 原地归并排序— {\displaystyle O(n\log ^{2}n)}wiki搬运,排序算法如果使用最佳的现在版本
  • 二叉排序树排序(binary tree sort)— {\displaystyle O(n\log n)}wiki搬运,排序算法期望时间;{\displaystyle O(n^{2})}wiki搬运,排序算法最坏时间;需要{\displaystyle O(n)}wiki搬运,排序算法额外空间
  • 鸽巢排序(pigeonhole sort)—{\displaystyle O(n+k)}wiki搬运,排序算法;需要{\displaystyle O(k)}wiki搬运,排序算法额外空间
  • 基数排序(radix sort)—{\displaystyle O(nk)}wiki搬运,排序算法;需要{\displaystyle O(n)}wiki搬运,排序算法额外空间
  • 侏儒排序(gnome sort)— {\displaystyle O(n^{2})}wiki搬运,排序算法
  • 图书馆排序(library sort)— {\displaystyle O(n\log n)}wiki搬运,排序算法期望时间;{\displaystyle O(n^{2})}wiki搬运,排序算法最坏时间;需要{\displaystyle (1+\varepsilon )n}wiki搬运,排序算法额外空间
  • 块排序(block sort)— {\displaystyle O(n\log n)}wiki搬运,排序算法

不稳定的排序[编辑]

  • 选择排序(selection sort)—{\displaystyle O(n^{2})}wiki搬运,排序算法
  • 希尔排序(shell sort)—{\displaystyle O(n\log ^{2}n)}wiki搬运,排序算法如果使用最佳的现在版本
  • 克洛弗排序(Clover sort)—{\displaystyle O(n)}wiki搬运,排序算法期望时间,{\displaystyle O(n^{2})}wiki搬运,排序算法最坏情况
  • 梳排序— {\displaystyle O(n\log n)}wiki搬运,排序算法
  • 堆排序(heap sort)—{\displaystyle O(n\log n)}wiki搬运,排序算法
  • 平滑排序(smooth sort)— {\displaystyle O(n\log n)}wiki搬运,排序算法
  • 快速排序(quick sort)—{\displaystyle O(n\log n)}wiki搬运,排序算法期望时间,{\displaystyle O(n^{2})}wiki搬运,排序算法最坏情况;对于大的、随机数列表一般相信是最快的已知排序
  • 内省排序(introsort)—{\displaystyle O(n\log n)}wiki搬运,排序算法
  • 耐心排序(patience sort)—{\displaystyle O(n\log n+k)}wiki搬运,排序算法最坏情况时间,需要额外的{\displaystyle O(n+k)}wiki搬运,排序算法空间,也需要找到最长的递增子序列(longest increasing subsequence)

不实用的排序[编辑]

  • Bogo排序— {\displaystyle O(n\times n!)}wiki搬运,排序算法,最坏的情况下期望时间为无穷。
  • Stupid排序—{\displaystyle O(n^{3})}wiki搬运,排序算法;递归版本需要{\displaystyle O(n^{2})}wiki搬运,排序算法额外存储器
  • 珠排序(bead sort)— {\displaystyle O(n)}wiki搬运,排序算法 或 {\displaystyle O({\sqrt {n}})}wiki搬运,排序算法,但需要特别的硬件
  • 煎饼排序—{\displaystyle O(n)}wiki搬运,排序算法,但需要特别的硬件
  • 臭皮匠排序(stooge sort)算法简单,但需要约{\displaystyle n^{2.7}}wiki搬运,排序算法的时间

 

名称 数据对象 稳定性 时间复杂度 额外空间复杂度 描述
平均 最坏
冒泡排序 数组 wiki搬运,排序算法 {\displaystyle O(n^{2})}wiki搬运,排序算法 {\displaystyle O(1)}wiki搬运,排序算法 (无序区,有序区)。
从无序区透过交换找出最大元素放到有序区前端。
选择排序 数组 wiki搬运,排序算法 {\displaystyle O(n^{2})}wiki搬运,排序算法 {\displaystyle O(1)}wiki搬运,排序算法 (有序区,无序区)。
在无序区里找一个最小的元素跟在有序区的后面。对数组:比较得多,换得少。
链表 wiki搬运,排序算法
插入排序 数组、链表 wiki搬运,排序算法 {\displaystyle O(n^{2})}wiki搬运,排序算法 {\displaystyle O(1)}wiki搬运,排序算法 (有序区,无序区)。
把无序区的第一个元素插入到有序区的合适的位置。对数组:比较得少,换得多。
堆排序 数组 wiki搬运,排序算法 {\displaystyle O(n\log n)}wiki搬运,排序算法 {\displaystyle O(1)}wiki搬运,排序算法 (最大堆,有序区)。
从堆顶把根卸出来放在有序区之前,再恢复堆。
归并排序 数组 wiki搬运,排序算法 {\displaystyle O(n\log ^{2}n)}wiki搬运,排序算法 {\displaystyle O(1)}wiki搬运,排序算法 把数据分为两段,从两段中逐个选最小的元素移入新数据段的末尾。
可从上到下或从下到上进行。
{\displaystyle O(n\log n)}wiki搬运,排序算法 {\displaystyle O(n)+O(\log n)}wiki搬运,排序算法
如果不是从下到上
链表 {\displaystyle O(1)}wiki搬运,排序算法
快速排序 数组 wiki搬运,排序算法 {\displaystyle O(n\log n)}wiki搬运,排序算法 {\displaystyle O(n^{2})}wiki搬运,排序算法 {\displaystyle O(\log n)}wiki搬运,排序算法 (小数,基准元素,大数)。 
在区间中随机挑选一个元素作基准,将小于基准的元素放在基准之前,大于基准的元素放在基准之后,再分别对小数区与大数区进行排序。
希尔排序 数组 wiki搬运,排序算法 {\displaystyle O(n\log ^{2}n)}wiki搬运,排序算法 {\displaystyle O(n^{2})}wiki搬运,排序算法 {\displaystyle O(1)}wiki搬运,排序算法 每一轮按照事先决定的间隔进行插入排序,间隔会依次缩小,最后一次一定要是1。
 
计数排序 数组、链表 wiki搬运,排序算法 {\displaystyle O(n+m)}wiki搬运,排序算法 {\displaystyle O(n+m)}wiki搬运,排序算法 统计小于等于该元素值的元素的个数i,于是该元素就放在目标数组的索引i位(i≥0)。
桶排序 数组、链表 wiki搬运,排序算法 {\displaystyle O(n)}wiki搬运,排序算法 {\displaystyle O(m)}wiki搬运,排序算法 将值为i的元素放入i号桶,最后依次把桶里的元素倒出来。
基数排序 数组、链表 wiki搬运,排序算法 {\displaystyle O(k\times n)}wiki搬运,排序算法 {\displaystyle O(n^{2})}wiki搬运,排序算法   一种多关键字的排序算法,可用桶排序实现。
    • 均按从小到大排列
    • k代表数值中的"数字"个数
    • n代表数据规模
    • m代表数据的最大值减最小值
上一篇:python:Socket编程(三):tcp三次握手四次挥手(简单举例编程:服务器、客户端)


下一篇:浙大版《C语言程序设计(第3版)》题目集 习题3-5 三角形判断 (15 分)