博客园: 十大经典排序算法（动图演示）

• 1. 冒泡排序（Bubble Sort）
• 2. 选择排序（Selection Sort）
• 3. 插入排序（Insertion Sort）
• 4. 希尔排序（Shell Sort）
• 5. 快速排序（Quick Sort）
  • 5.1. 非就地排序
  • 5.2. 就地快速排序
  • 5.3. 随机化快速排序
  • 5.4. 复杂度计算
• 6. 归并排序（Merge Sort）
• 7. 堆排序（Heap Sort）
• 8. 计数排序（Counting Sort）
• 9. 桶排序（Bucket Sort）
• 10. 基数排序（Radix Sort）

1. 冒泡排序（Bubble Sort）

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

2. 选择排序（Selection Sort）

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

3. 插入排序（Insertion Sort）

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

4. 希尔排序（Shell Sort）

1959年Shell发明，第一个突破 O(n^2) 的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

先将整个待排序的记录序列分割成为若干子序列，分别进行直接插入排序。

5. 快速排序（Quick Sort）

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

核心

1. 找中轴
2. 左侧递归，右侧递归

所谓“分而治之”，利用递归的方式解决问题。

ps: 对于"快速排序"的动图展示，个人表示并不容易理解——如果类似归并排序，分成上下两排来展示，可能效果更好。相比而言，代码更容易理解。

def quick_sort(arr):
    """ 非就地排序，占用了更多的空间复杂度：(2^n - 1) * n + LogN
        当然，非就地排序更容易理解——不用研究那两个向中间对冲的“哨兵”
    """
    if len(arr) < 2:
        return arr

    pivot, left, right = arr[0], [], []
    for i in arr[1:]:
        if i < pivot:
            left.append(i)
        else:
            right.append(i)

    return quick_sort(left) + [pivot] + quick_sort(right)

5.1. 非就地排序

随机的选择一个pivot（一般可以选择数组首位，或者末位、中间位），然后逐一将其他元素分为“大于pivot”与“小于pivot”的两组。这个过程的目的，是让pivot这个中轴数归位。最后通过递归，重复这个过程。

分析下这个算法的空间复杂度，来自两部分：

1. 引入了辅助数组：left、right
2. 递归过程返回值占用的空间

至少第一步是可以避免的。这就是“就地快排”，但理解更有难度。

5.2. 就地快速排序

下面我们用图解的方式来演示这个排序过程：

假设下面这个数组是待排序数组：

[6, 1, 2, 7, 9, 3, 4, 5, 10, 8]

按照快速排序的思想，首先得把这组数分成相互独立的两部分，其中一部分比中的数比另一部分的数都小。如何实现这一步呢？

方法其实很简单：首先选取待排序数组的第一个数为基准数，也就是6，然后分别从初始序列“（6, 1, 2, 7, 9, 3, 4, 5, 10, 8）”两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量i和j，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边（即i=1），指向数字6。让哨兵j指向序列的最右边（即j=10），指向数字8。

首先哨兵 j 开始出动。因为此处设置的基准数是最左边的数，所以需要让哨兵 j 先出动，这一点非常重要（请自己想一想为什么）。哨兵 j 一步一步地向左挪动（即 j--），直到找到一个小于 6 的数停下来。接下来哨兵 i 再一步一步向右挪动（即 i++），直到找到一个数大于 6 的数停下来。最后哨兵 j 停在了数字 5 面前，哨兵 i 停在了数字 7 面前。

如果选取最左边的数arr[left]作为基准数，那么先从右边开始可保证i,j在相遇时，相遇数是小于基准数的，交换之后temp所在位置的左边都小于temp。但先从左边开始,相遇数是大于基准数的，无法满足temp左边的数都小于它。所以进行扫描，要从基准数的对面开始。

现在交换哨兵 i 和哨兵 j 所指向的元素的值。交换之后的序列为（6, 1, 2, 5, 9, 3, 4, 7, 10, 8）。

接下来开始哨兵 j 继续向左挪动（再友情提醒，每次必须是哨兵 j 先出发）。他发现了 4（比基准数 6 要小，满足要求）之后停了下来。哨兵 i 也继续向右挪动的，他发现了 9（比基准数 6 要大，满足要求）之后停了下来。此时再次进行交换，交换之后的序列为（6, 1, 2, 5, 4, 3, 9, 7, 10, 8）。

哨兵 j 继续向左挪动，他发现了 3（比基准数 6 要小，满足要求）之后又停了下来。哨兵 i 继续向右移动，糟啦！此时哨兵 i 和哨兵 j 相遇了，哨兵 i 和哨兵 j 都走到 3 面前。说明此时 “探测” 结束。3 比 6 小所以我们将基准数 6 和 3 进行交换。交换之后的序列为（3, 1, 2, 5, 4, 6, 9, 7, 10, 8）。

此时第一趟排序结束，我们已经把待排序数组分成了以 6 为基准，左边一列序列，右边一序列，左边序列的数比右边序列的数都小。不过此时左右两部分中的数各自的排序仍然是混乱的，还有继续排序。

快速排序的排序过程已经通过上面的图解讲解清楚了，接下来左右两部分的数据继续按照快速排序的方式来排序。

其中左边的序列是（3, 1, 2, 5, 4），按照上面的排序图解哨兵 j 停下来的时候在 2 上面，哨兵 i 停下来的时候在 5 的上面，但此时哨兵 i 已经跑过哨兵 j 到他前面去了，所以此时不应该在把两个哨兵所对应的数交换，而应该把我们的基准数 3 和 2 交换，所以此时左侧的序列经过一次快速排序后变成了这样（2, 1, 3, 5, 4）。

右侧的序列经过一次快速排序后变成了这样（8, 7, 9, 10）。

合并基准数 6 以及左右两侧的序列：

[ 2, 1 || 3 || 5, 4  ||| 6 |||  8, 7 || 9 || 10 ]

对于排序仍然混乱的部分继续以快速排序进行排序，最终的排序应该是这样的

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

细心的同学可能已经发现，快速排序的每一轮处理其实就是将这一轮的基准数归位，直到所有的数都归位为止，排序就结束了。下面上个霸气的图来描述下整个算法的处理过程。

快速排序之所比较快，因为相比冒泡排序，每次交换都是折半进行的。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是 O(N^2) ，它的平均时间复杂度为 O(N*logN) 。

5.3. 随机化快速排序

快排在选取主元的时候，每次都选取最右边的元素。当序列为有序时，会发现划分出来的两个子序列一个里面没有元素，而另一个则只比原来少一个元素。为了避免这种情况，引入一个随机化量来破坏这种有序状态。

实际上，这个过程很容易实现。pivot, left, right = arr[0], [], [] 前面增加一行乱序的代码：

pivot_idx = random.randint(1, len(arr))
arr[pivot_idx], arr[0] = arr[0], arr[pivot_idx]

5.4. 复杂度计算

快速排序的期望复杂度是O(nlogn)，但最坏情况下可能就会变成O(n^2)，最坏情况就是每次将一组数据划分为两组的时候，分界线都选在了边界上，使得划分了和没划分一样，最后就变成了普通的选择排序了。

快速排序的空间复杂度可以理解为递归的深度，而递归的实现依靠栈，平均需要递归logN次，所以平均空间复杂度为O(logN)。

6. 归并排序（Merge Sort）

归并排序也是一种非常高效的排序方式，其也用了分治的思想，具体的代码可以写成递归的形式。

我们首先将整个序列两两分开，然后每组中的两个元素排好序。接着就是组与组和合并，这个只需将两组所有的元素遍历一遍，即可按顺序合并。以此类推，最终所有组合并为一组时，整个数列就已经排好序了。

def merge_sort(arr):
    def merge(arr1, arr2):
        result = []
        while arr1 and arr2:
            arr = arr1 if arr1[0] < arr2[0] else arr2
            result.append(arr.pop(0))
        arr = arr1 if arr1 else arr2
        return result + arr

    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    return merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))

空间复杂度：虽然同样是通过递归实现的排序，然而与快速排序不同，每一层递归，result临时数组占用的空间总和为 O(1) ，经过 (logN)^2 层后，空间复杂度为 O(n) 。

7. 堆排序（Heap Sort）

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

8. 计数排序（Counting Sort）

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

9. 桶排序（Bucket Sort）

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

10. 基数排序（Radix Sort）

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。