algorithm - Bubblesort 优于其他排序算法？

Question

为什么选择冒泡排序而不是其他排序算法？

Answer 1

你不会。

杜克大学的 Owen Astrachan 曾写过一篇追溯冒泡排序历史的研究论文 (Bubble Sort: An Archaeological Algorithmic Analysis)，并引用 CS 传奇人物 Don Knuth 的话

In short, the bubble sort seems to have nothing to recommend it, except a catchy nameand the fact that it leads to some interesting theoretical problems.

本文以

结尾

In this paper we have investigated the origins of bubble sort and its enduring popularity despite warnings against its use by many experts. We confirm the warnings by analyzing its complexity both in coding and runtime.

冒泡排序比其他 O(n²) 排序慢；它大约是插入排序的四倍，是选择排序的两倍。它确实具有良好的最佳情况行为(如果您包含对无交换的检查)，但插入排序也是如此:只需遍历一个已排序的数组。

冒泡排序在几乎所有真实数据集上都慢得不切实际。快速排序、堆排序或归并排序的任何良好实现都可能大大优于它。对足够小的基本情况使用更简单的排序算法的递归排序使用插入排序，而不是冒泡排序。

此外，the President of the United States says you shouldn't use it.

相关: Why bubble sort is not efficient? 有更多详细信息。