排序算法的总结 | Zyx’s Blog

type

status

date

Last edited time

slug

summary

1 稳定排序（相等元素的相对顺序不会改变）

1.1 冒泡排序（Bubble Sort）

1.1.1 原理

冒泡排序是一种简单的排序算法，它重复地走访要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢 “浮” 到数列的顶端（就像气泡一样）。

1.1.2 时间复杂度

最优时间复杂度（数列已有序）:

平均时间复杂度:

最坏时间复杂度:

1.1.3 代码

1.2 插入排序（Insertion Sort）

1.2.1 原理

插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用 in-place 排序，因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪动腾出空间。

1.2.2 时间复杂度

最优时间复杂度（数列已有序）:

平均时间复杂度:

最坏时间复杂度:

1.2.3 代码

1.3 归并排序（Merge Sort）

1.3.1 原理

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。它的基本思路是将数组分成两部分，分别对这两部分进行排序，然后再将排好序的两部分合并起来，这个过程不断递归进行，直到整个数组都被排好序。

1.3.2 时间复杂度

最优时间复杂度（数列已有序）:

平均时间复杂度:

最坏时间复杂度:

1.3.3 代码

1.4 计数排序（Counting Sort）

1.4.1 原理

计数排序是一种非比较型排序算法，它的基本思想是对于给定的输入序列中的每一个元素，确定该元素在输出序列中的正确位置，这个位置的确定是通过统计小于等于该元素的元素个数来实现的。计数排序的前提是输入的数据必须是有确定范围的整数，它对一定范围内的整数排序速度非常快。

1.4.2 时间复杂度

💡

*范围是k

最优时间复杂度（数列已有序）:

平均时间复杂度:

最坏时间复杂度:

1.4.3 代码

1.5 桶排序（Bucket Sort）

1.5.1 原理

桶排序的基本思想是将数组划分成多个范围相同的区间，这些区间就像一个个 “桶”，然后将待排序的数据分配到对应的桶中，对每个桶内部的数据可以使用其他排序算法（比如插入排序等）进行排序，最后按顺序将各个桶中的数据取出，就得到了排序好的数组。桶排序适用于数据分布比较均匀的情况，效率较高。

1.5.2 时间复杂度

最优时间复杂度（数列已有序）:

平均时间复杂度:

最坏时间复杂度:

1.5.3 代码

2 不稳定排序（相等元素的相对顺序会改变）

2.1 选择排序（Selection Sort）

2.1.1 原理

选择排序的基本思想是首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

2.1.2 时间复杂度

最优时间复杂度（数列已有序）:

平均时间复杂度:

最坏时间复杂度:

2.1.3 代码

2.2 希尔排序（Shell Sort）

2.2.1 原理

希尔排序也称缩小增量排序，它是对插入排序的一种改进版本。它的基本思想是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录 “基本有序” 时，再对全体记录进行一次直接插入排序。分割子序列的方法不是简单地 “逐段分割”，而是将相隔某个 “增量” 的记录组成子序列。

2.2.2 时间复杂度（大约）

最优时间复杂度（数列已有序）:

平均时间复杂度:

最坏时间复杂度:

2.2.3 代码

2.3 快速排序（Quick Sort）

2.3.1 原理

快速排序同样基于分治法，它的基本思想是选择一个基准元素（pivot），通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比基准元素小，另一部分记录的关键字均比基准元素大，然后再分别对这两部分记录继续进行快速排序，以此类推，直到整个序列都被排好序。

2.3.2 时间复杂度

最优时间复杂度（数列已有序）:

平均时间复杂度:

最坏时间复杂度:

2.3.3 代码

2.4 堆排序（Heap Sort）

2.4.1 原理

堆排序是利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足父节点的值总是大于或等于（大顶堆）其子女节点的值，或者父节点的值总是小于或等于（小顶堆）其子女节点的值这一条件。堆排序的基本思路是先将数组构建成一个堆（大顶堆或小顶堆），然后每次取出堆顶元素（最大或最小元素），再重新调整堆，直到整个数组都被排序完。

2.4.2 时间复杂度

最优时间复杂度（数列已有序）:

平均时间复杂度:

最坏时间复杂度:

1 稳定排序（相等元素的相对顺序不会改变）

1.1 冒泡排序（Bubble Sort）

1.1.1 原理

1.1.2 时间复杂度

1.1.3 代码

1.2 插入排序（Insertion Sort）

1.2.1 原理

1.2.2 时间复杂度

1.2.3 代码

1.3 归并排序（Merge Sort）

1.3.1 原理

1.3.2 时间复杂度

1.3.3 代码

1.4 计数排序（Counting Sort）

1.4.1 原理

1.4.2 时间复杂度

1.4.3 代码

1.5 桶排序（Bucket Sort）

1.5.1 原理

1.5.2 时间复杂度

1.5.3 代码

2 不稳定排序（相等元素的相对顺序会改变）

2.1 选择排序（Selection Sort）

2.1.1 原理

2.1.2 时间复杂度

2.1.3 代码

2.2 希尔排序（Shell Sort）

2.2.1 原理

2.2.2 时间复杂度（大约）

2.2.3 代码

2.3 快速排序（Quick Sort）

2.3.1 原理

2.3.2 时间复杂度

2.3.3 代码

2.4 堆排序（Heap Sort）

2.4.1 原理

2.4.2 时间复杂度

2.4.3 代码