常用的排序算法与Python实现

0 前言

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

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

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

1 选择排序

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

2 插入排序

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

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

3 快速排序

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

4 归并排序

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

5 总结

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

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

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20190905A0L8PA00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码关注腾讯云开发者

领取腾讯云代金券