尚学堂笔记:Python中的几种排序方法

在Python当中,排序的方法有很多,在这些方法中,大致能分为内部排序和外部排序两种,如果在外部排序中因数据量较大,会是的这些排序记录不能够被全部容纳,可能还会调用外部存储。可以说,排序也是算法的一部分,那么下面笔者先简单介绍两种较为重要的排序方法。

首先介绍的是希尔排序(Shell's Sort)。该方法因DL.Shell于1959年提出而得名。希尔排序属于插入排序中的一种排序方法。目的在于缩小增量,是直接插入排序算法的一种更高效的改进版本。希尔排序属于非稳定排序算法,与冒泡排序有所不同。他是将无序数组分割为若干个子序列,子序列不是逐段分割的,而是相隔特定的增量的子序列,对各个子序列进行插入排序;之后在对一个更小的增量做出选择,将数组分割为多个子序列进行排序,若最终选择增量为1,即可使用直接插入排序,让数组成为有序数组。

希尔排序是将记录按下标的一定增量分组,针对各组使用直接插入排序算法进行排序;当增量逐渐减少时,每组包含的关键词越来越多,当增量减至1时,整个文件则分成一组,算法随即终止。

下面来简单介绍一下冒泡排序(Bubble Sort),和希尔排序相比较为简单,在各种排序算法中,冒泡排序属于内部排序的交换排序,其原理可以概括为:比较相邻的两个元素,将值大的元素交换到右边(降序则相反)。在待排序的一组数中,在对当前还没有排好序的范围内的数,自上而下对相邻的两个数依次做比较和调整,较大的数往下排,较小的数往上冒。算法实现可参考如下:

在以上的内容中简单讲述了希尔排序和冒泡排序,希尔排序可以被理解为插入排序的延伸,选择排序则较为直接和简单,在排序算法中通常有插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序、基数排序等八种算法。今后有时间会对其他排序算法做一一讲解。

在学各种排序算法时,也要结合具体的编程项目,尚学堂陈老师提到,在大数据、云计算条件下,排序算法的稳定性非常重要,例如购物网站按照销量、价格对商品进行排序,要对服务器中的海量数据进行操作,如果选择稳定性较差的排序算法,会影响到服务器性能和用户体验。

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

扫码关注云+社区

领取腾讯云代金券