十大经典排序算法

我们先对常用算法的时间复杂度做个比较:

排序算法期望时间复杂度最好情况最坏情况空间复杂度稳定性排序方式
冒泡排序$O(n^2)$$O(n)$$O(n^2)$$O(1)$StableIn-place
选择排序$O(n^2)$$O(n^2)$$O(n^2)$$O(1)$UnstableIn-place
插入排序$O(n^2)$$O(n)$$O(n^2)$$O(1)$StableIn-place
希尔排序$O(n\ \textrm{log}\ n)$$O(n\ \textrm{log}^2\ n)$$O(n\ \textrm{log}^2\ n)$$O(1)$UnstableInplace
归并排序$O(n\ \textrm{log}\ n)$$O(n\ \textrm{log}\ n)$$O(n\ \textrm{log}\ n)$$O(n)$StableOut-place
快速排序$O(n\ \textrm{log}\ n)$$O(n\ \textrm{log}\ n)$$O(n^2)$$O(\textrm{log}\ n)$UnstableIn-place
堆排序$O(n\ \textrm{log}\ n)$$O(n\ \textrm{log}\ n)$$O(n\ \textrm{log}\ n)$$O(1)$UnstableIn-place
桶排序$O(n+k)$$O(n+k)$$O(n^2)$$O(n+k)$StableOut-place
计数排序$O(n+k)$$O(n+k)$$O(n+k)$$O(k)$StableOut-place
基数排序$O(n \times k)$$O(n \times k)$$O(n \times k)$$O(n+k)$StableOut-place

PS:

  • n: 代表数据规模及数据量大小
  • k: 桶的个数
  • In-place: 不占用额外内存,只占用常数内存
  • Out-place: 占用额外内存

冒泡排序

冒泡排序是排序算法中较为简单的一种,英文称为 Bubble Sort 。它遍历所有的数据,每次对相邻元素进行比较,如果顺序和预先规定的顺序不一致,则进行交换;这样一次遍历会将最大或最小的数据上浮到顶端(像不像冒泡泡),之后再重复同样的操作,直到所有的数据有序。

代吗极其简短 (和 Floyd 可以一试高下

如果有 $n$ 个数据,那么需要 $O(n^2)$ 的比较次数,所以当数据量很大时,冒泡算法的效率并不高。 当输入的数据是反序时,花的时间最长,当输入的数据是正序时,时间最短。

平均时间复杂度:$O(n^2)$

空间复杂度:$O(1)$

动态演示:

_OI⁄ten-sort-algorithm_Bubble-Sort.gif

代码:

C++

1
2
3
4
5
6
7
template<typename T>
inline void bubble_sort(T *begin_ptr, T *end_ptr) {
    int len = end_ptr - begin_ptr;
    for (int i = 0; i < len - 1; i++)
        for (T *j = begin_ptr; j < end_ptr; j++)
            if (*j > *(j + 1)) std::swap(j, j + 1);
}

选择排序

选择排序简单直观,英文称为 Selection Sort ,先在数据中找出最大或最小的元素,放到序列的起始;然后再从余下的数据中继续寻找最大或最小的元素,依次放到排序序列中,直到所有数据样本排序完成。很显然,选择排序也是一个费时的排序算法,无论什么数据,都需要 $O(n^2)$ 的时间复杂度,不适宜大量数据的排序。

平均时间复杂度:$O(n^2)$

空间复杂度:$O(1)$

动态演示:

代码:

1

插入排序

插入排序英文称为 Insertion Sort ,它通过构建有序序列,对于未排序的数据序列,在已排序序列中从后向前扫描,找到相应的位置并插入,类似打扑克牌时的码牌。插入排序有一种优化的算法,可以进行拆半插入。

基本思路是先将待排序序列的第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列;然后从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置,直到所有数据都完成排序;如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。

平均时间复杂度:$O(n^2)$

空间复杂度:$O(1)$

动态演示:

代码:

1

未完成

updatedupdated2020-07-142020-07-14
Update Site @2020-07-14-07:07:38
加载评论