跳舞吧排序

说起算法,离不开排序。提起算法,就有点脑壳疼……

为了不头疼,外国人还真会玩……

事件复杂度分析指标 Big O

事件复杂度分析(TCA)指标 O,英文称作 Big O。 这里不多说,我觉得如何理解算法时间复杂度的表示法,例如 O(n²)、O(n)、O(1)、O(nlogn) 等? - 司马懿的回答 - 知乎 较好理解。

这里放张表直接查阅:

图解排序

插入排序 Insert Sort

最优 O(N) 最差 O(N²)

来跳个舞:

选择排序 Selection Sort

最优 O(N²) 最差 O(N²)

来跳个舞:

归并排序 Merge Sort

稳定 O(N log N)

来跳个舞:

堆排序 Heap Sort

快速排序 Quick Sort

最优 O(N log N) 最差 O(N²) 来跳个舞:

冒泡排序 Bubble Sort

最优 O(N) 最差 O(N²) 来跳个舞:

希尔排序

最优 O(N log N) 最差 O((log n)n^2)

来跳个舞:

还有很多子类型……

最快的算法是什么

从上两个图来看快速排序无论是时间复杂度还是空间复杂度都是最优的(空间复杂度超越所有其他算法)。

实际情况是怎样的呢? 上图可见快速排序稳定且实际效率良好。 测试代码见这里

为什么要这么多排序?

既然已经知道快速排序是目前所知最好的,为什么还需要其他排序? 有人的回答是,不同的算法对于视觉特效(游戏)有不同的展示,大家来看几个例子:

(以下图片均出自https://imgur.com/gallery/voutF)

冒泡排序:

鸡尾酒排序(冒泡排序变体):

梳排序排序(改良自冒泡排序和快速排序):

参见

十大经典排序算法(动图演示)


Total views.

© 2013 - 2019. All rights reserved.

Powered by Hydejack v6.6.1