开发者社区> 问答> 正文

除了经典和常用的排序算法外,还有哪些奇葩而有趣的排序算法

除了经典和常用的排序算法外,还有哪些奇葩而有趣的排序算法

展开
收起
知与谁同 2018-07-22 12:46:53 2505 0
3 条回答
写回答
取消 提交回答
  • 这个好像不多
    2019-07-17 22:49:30
    赞同 展开评论 打赏
  • 桶排序,多着呢
    2019-07-17 22:49:29
    赞同 展开评论 打赏
  • 排序算法有:
    冒泡排序(bubble sort) — O(n^2)
    鸡尾酒排序(Cocktail sort,双向的冒泡排序) — O(n^2)
    插入排序(insertion sort)— O(n^2)
    桶排序(bucket sort)— O(n); 需要 O(k) 额外空间
    计数排序(counting sort) — O(n+k); 需要 O(n+k) 额外空间
    合并排序(merge sort)— O(nlog n); 需要 O(n) 额外空间
    原地合并排序— O(n^2)
    二叉排序树排序 (Binary tree sort) — O(nlog n)期望时间; O(n^2)最坏时间; 需要 O(n) 额外空间
    鸽巢排序(Pigeonhole sort) — O(n+k); 需要 O(k) 额外空间
    基数排序(radix sort)— O(n·k); 需要 O(n) 额外空间
    Gnome 排序— O(n^2)
    图书馆排序— O(nlog n) with high probability,需要 (1+ε)n额外空间
    不稳定的
    选择排序(selection sort)— O(n^2)
    希尔排序(shell sort)— O(nlog n) 如果使用最佳的现在版本
    组合排序— O(nlog n)
    堆排序(heapsort)— O(nlog n)
    平滑排序— O(nlog n)
    快速排序(quicksort)— O(nlog n) 期望时间,O(n^2) 最坏情况; 对于大的、乱数列表一般相信是最快的已知排序
    Introsort— O(nlog n)
    Patience sorting— O(nlog n+ k) 最坏情况时间,需要 额外的 O(n+ k) 空间,也需要找到最长的递增子串行(longest increasing subsequence)
    不实用的
    Bogo排序— O(n× n!) 期望时间,无穷的最坏情况。
    Stupid sort— O(n^3); 递归版本需要 O(n^2) 额外存储器
    珠排序(Bead sort) — O(n) or O(√n),但需要特别的硬件
    Pancake sorting— O(n),但需要特别的硬件
    stooge sort——O(n^2.7)很漂亮但是很耗时
    2019-07-17 22:49:29
    赞同 1 展开评论 打赏
问答分类:
问答地址:
问答排行榜
最热
最新

相关电子书

更多
数据+算法定义新世界 立即下载
袋鼠云基于实时计算的反黄牛算法 立即下载
Alink:基于Apache Flink的算法平台 立即下载