常用的排序算法与Python实现

0 前言

排序算法，可以说是编程中使用最多的算法之一了，而我们了解最多的排序算法，恐怕是冒泡排序了，这个算法比较好理解，稳定，不过时间也复杂度也是O(n^2)了效果也不是很好。也有很多效果比这个好的算法，或者排序比较巧妙的算法，例如：选择排序，插入排序，快速排序，归并排序，桶排序，堆排序等等。排序算法那么多，真的突然让我去介绍一个排序算法，我还不能够立即说出来，下面就记录几个常用的排序算法。

对于Java，Python都会有已经写好的排序算法，例如Python中的sort和sorted方法，为什么我们还要去学习这些，其实在解决一些问题的时候对数组进行排序可以解决其他问题，这就是我们要学习其思想的原因。

注：以下排序都是默认升序的。

1 选择排序

选择排序，你可以这样理解，我们先把一个数组从前往后分为两部分，第一部分就是空，第二部分就是整个数组，我们可以依次从第二个部分中拿出最小的数插到第一部分中，依此类推直至把第二部分中的元素取完。其实，这个排序方式的算法复杂度也是O(n^2)，代码实现如下：

2 插入排序

插入排序的核心思想就是将一个列表分为两个部分，一部分是排序的，一部分没有排序，我们逐次将没有排序的元素，在已排序序列中从后往前扫描找到对应位置并插入。换句话说，就是将无序的部分插入到有序的部分中。默认数组中第一个值就是有序的，然后就剩下的部分。最好的情况就是全部有序，那么算法的时间复杂度就是O(n)了，并且该算法是稳定的。

另外：这里可以使用二分查找的方式提速。

3 快速排序

快速排序就是通过一趟排序将需要排序的数据分割为独立的两部分，首先任意选取一个数据（通常选用列表的第一个数）作为基准数据，然后将所有比它小的数都放在它左边，比它大的数放在右边，到只有两个元素的时候，就自动排好序了，递归回去时就就把上一层的数据排好序了，不过算法不稳定。

4 归并排序

归并排序也是使用递归的方法，需要辅助数组，辅助数组中存放是，当前需要合并的结果，合并的方式是：使用两个指针p1,p2，分别指向两个需要比较数组数组的开始的第一个值，然后比较这个指针指向的值，将较小的数放到辅助数组中，然后移动对应的指针进行下一次的比较，算法复杂度O(nlogn)，稳定的。

5 总结

排序算法较多，思想也比较独特，理解清楚这些算法后，对解决其他问题有很大的好处。

它，不仅仅是一个码，更是一个了解算法、数学、编程、技巧等等一些神器的一道门！