7种经典排序算法及实现

昨天面试被问到了快排，这里正好将 排序 系统过一遍。

简介

排序是入门技术面试一个永恒的主题，记得去年问某大牛想招什么样的技术人员时，笑眯眯答曰“如果一个人连个sort都写不出来，那我也不会想是吧。” 囧…

网上介绍排序的文章非常多，本文的目的是提供一个最快速且全面的入门教程，仅仅阅读本文，你就可以串联起主要 排序算法 中需要把握的点和具体的代码实现（基于Python）。

动机

排序是所有算法的基础，根据《算法》[1] 中的描述 — “we often use sorting algorithms as a starting point to solve other problems.” ，虽然已经有不少sort接口可以直接调用，但排序作为一个完整的故事，是我们充分理解算法比较的一个最佳实践，同时从面试的角度来说，也是经常提及的问题，这是每个 程序员 应该把握的基本功。

经典排序算法介绍

请先看完如下可视化视频，可以初步理解各个排序在做什么（2倍速绝对酸爽，减压必备良方）。

下面逐一介绍：

1.冒泡排序（Bubble Sort）

冒泡排序的思想是两两比较相邻记录的值，如果反序即交换，这样最小的记录犹如气泡一般浮”水面“，故称为冒泡排序。时间复杂度而言，在最好情况下，即正序有序，只需要比较n次。故，为O(n) ，最坏情况下，即逆序有序，需要比较(n-1)+(n-2)+… …+1，故，为O(n²)。

2.选择排序（Selection Sort）

选择排序每次都从序列中找到最小的元素，置于数组起始位置，以此类推，直到所有元素排序完毕。其运行时间和输入无关，同时数据移动是最少的，时间复杂度为O(n²)。

3.插入排序（Insertion Sort）

插入排序重复执行插入操作，类似扑克牌整理，排序过程中将每一张牌插入到其他已经有序的牌中的适当位置，该排序对于“部分有序”的数组十分高效，其时间复杂度为O(n²)。

4.希尔排序 (Shell Sort)

希尔排序是插入排序的改进版，首先使数组中任意间隔以h的元素都是有序的，之后递减步长，直至整个序列有序。希尔排序权衡了子数组的规模和有效性，其效率很大程度上取决于步长的选取，根据[1]的描述 — “Shell sort is the only sorting method we consider whose performance on randomly ordered arrays has not been precisely characterized.”

5.归并排序 (Merge Sort)

归并排序采用分治思想，其思想是将序列（递归地）分成两半分别排序，之后将结果归并起来，属于分治法（Divide and Conquer）的应用，其时间复杂度是 O(nlogn)。

6.快速排序 (Quicksort)

快速排序可能是被问得最多的排序了，其也是一种分治算法，原理是先选定“标兵”（pivot），然后将序列中比标兵大的数排右测，比标兵小的数排左侧，此步骤称为分割（partition），递归调用，直至排序完成。其平均情况下的时间复杂度是 O(nlogn)。

7.堆排序 (Heapsort)

堆排序通过构造堆来进行排序过程，其排序过程分为：1）堆的构造 和 2）下沉排序 两步，其时间复杂度是 O(nlogn)，由于要构造堆，因此不适用于序列个数较少的情况。

上述7种排序的代码实现如下（基于Python）：

https://github.com/KrisCheng/HackerProblem/blob/master/Python/12_Sort/Sort.ipynb

参考及扩展

[1] 算法（第四版）

[2] 九种排序算法的可视化及比较

[3] 各大排序算法的Wiki页面

3 total views, 3 views today