搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 人工智能与大数据精选 > 排序算法对比与总结(Python篇)

排序算法对比与总结(Python篇)

人工智能与大数据精选 2018-06-28

排序大的分类可以分为两种:内排序和外排序。在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序。下面讲的排序都是属于内排序。

内排序有可以分为以下几类:

  1. 插入排序:直接插入排序、二分法插入排序、希尔排序。

  2. 选择排序:直接选择排序、堆排序。

  3. 交换排序:冒泡排序、快速排序。

  4. 归并排序

  5. 基数排序

对比

冒泡排序(BubbleSort)

1.基本思想:两个数比较大小,较大的数下沉,较小的数冒起来。
2.过程:

  • 比较相邻的两个数据,如果第二个数小,就交换位置。

  • 从后向前两两比较,一直到比较最前两个数据。最终最小数被交换到起始的位置,这样第一个最小数的位置就排好了。

  • 继续重复上述过程,依次将第2.3...n-1个最小数排好位置。

排序算法对比与总结(Python篇)

3.平均时间复杂度:O(n2)
4.优化:
针对问题:
数据的顺序排好之后,冒泡算法仍然会继续进行下一轮的比较,直到arr.length-1次,后面的比较没有意义的。
方案:
设置标志位flag,如果发生了交换flag设置为true;如果没有交换就设置为false。
这样当一轮比较结束后如果flag仍为false,即:这一轮没有发生交换,说明数据的顺序已经排好,没有必要继续进行下去。

5.Python代码实现:


排序算法对比与总结(Python篇)

选择排序(SelctionSort)

1.基本思想:
在长度为N的无序数组中,第一次遍历n-1个数,找到最小的数值与第一个元素交换;
第二次遍历n-2个数,找到最小的数值与第二个元素交换;
。。。
第n-1次遍历,找到最小的数值与第n-1个元素交换,排序完成。

2.过程:

排序算法对比与总结(Python篇)


3.平均时间复杂度:O(n2)
4.python代码实现:


排序算法对比与总结(Python篇)

插入排序(Insertion Sort)

1.基本思想:
在要排序的一组数中,假定前n-1个数已经排好序,现在将第n个数插到前面的有序数列中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。

2.过程:


排序算法对比与总结(Python篇)


排序算法对比与总结(Python篇)


3.平均时间复杂度:O(n2)

4.python代码实现:


排序算法对比与总结(Python篇)

希尔排序(Shell Sort)

1.基本思想:
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

2.过程:


排序算法对比与总结(Python篇)

3.平均时间复杂度:O(n*logn)

4.python代码实现:


排序算法对比与总结(Python篇)

快速排序(Quicksort)

1.基本思想:(分治)
先从数列中取出一个数作为key值;
将比这个数小的数全部放在它的左边,大于或等于它的数全部放在它的右边;
对左右两个小数列重复第二步,直至各区间只有1个数。

2.过程

  • 初始时 i = 0; j = 9; key=72
    由于已经将a[0]中的数保存到key中,可以理解成在数组a[0]上挖了个坑,可以将其它数据填充到这来。
    从j开始向前找一个比key小的数。当j=8,符合条件,a[0] = a[8] ; i++ ; 将a[8]挖出再填到上一个坑a[0]中。
    这样一个坑a[0]就被搞定了,但又形成了一个新坑a[8],这怎么办了?简单,再找数字来填a[8]这个坑。
    这次从i开始向后找一个大于key的数,当i=3,符合条件,a[8] = a[3] ; j-- ; 将a[3]挖出再填到上一个坑中。

排序算法对比与总结(Python篇)


  • 此时 i = 3; j = 7; key=72
    再重复上面的步骤,先从后向前找,再从前向后找。
    从j开始向前找,当j=5,符合条件,将a[5]挖出填到上一个坑中,a[3] = a[5]; i++;
    从i开始向后找,当i=5时,由于i==j退出。
    此时,i = j = 5,而a[5]刚好又是上次挖的坑,因此将key填入a[5]。

排序算法对比与总结(Python篇)


  • 可以看出a[5]前面的数字都小于它,a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。

排序算法对比与总结(Python篇)

3.平均时间复杂度:O(N*logN)

4.Python代码实现:

排序算法对比与总结(Python篇)

堆排序(HeapSort)

堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。首先简单了解下堆结构。

堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。如下图:

排序算法对比与总结(Python篇)

image



同时,我们对堆中的结点按层进行编号,将这种逻辑结构映射到数组中就是下面这个样子

排序算法对比与总结(Python篇)

image


该数组从逻辑上讲就是一个堆结构,我们用简单的公式来描述一下堆的定义就是:

大顶堆:arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

小顶堆:arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

堆排序基本思想及步骤

堆排序的基本思想是:将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换,此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列了

步骤一 构造初始堆。将给定无序序列构造成一个大顶堆(一般升序采用大顶堆,降序采用小顶堆)。

排序算法对比与总结(Python篇)

  1. 假设给定无序序列结构如下

  2. 此时我们从最后一个非叶子结点开始(叶结点自然不用调整,第一个非叶子结点 arr.length/2-1=5/2-1=1,也就是下面的6结点),从左至右,从下至上进行调整。


    排序算法对比与总结(Python篇)


  1. 找到第二个非叶节点4,由于[4,9,8]中9元素最大,4和9交换。

排序算法对比与总结(Python篇)


这时,交换导致了子根[4,5,6]结构混乱,继续调整,[4,5,6]中6最大,交换4和6。


排序算法对比与总结(Python篇)

步骤二 将堆顶元素与末尾元素进行交换,使末尾元素最大。然后继续调整堆,再将堆顶元素与末尾元素交换,得到第二大元素。如此反复进行交换、重建、交换。

  1. 将堆顶元素9和末尾元素4进行交换


    排序算法对比与总结(Python篇)


  1. 重新调整结构,使其继续满足堆定义

排序算法对比与总结(Python篇)

  1. 再将堆顶元素8与末尾元素5进行交换,得到第二大元素8.

排序算法对比与总结(Python篇)


后续过程,继续进行调整,交换,如此反复进行,最终使得整个序列有序

排序算法对比与总结(Python篇)

501521032602_.pi

再简单总结下堆排序的基本思路:

a.将无需序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆;

b.将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端;

c.重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个序列有序。

代码实现:


排序算法对比与总结(Python篇)

归并排序(Merge Sort)

归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。

排序算法对比与总结(Python篇)

可以看到这种结构很像一棵完全二叉树,本文的归并排序我们采用递归去实现(也可采用迭代的方式去实现)。分阶段可以理解为就是递归拆分子序列的过程,递归深度为log2n。

合并相邻有序子序列


来看看治阶段,我们需要将两个已经有序的子序列合并成一个有序序列,比如上图中的最后一次合并,要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列,合并为最终序列[1,2,3,4,5,6,7,8],来看下实现步骤。

排序算法对比与总结(Python篇)


排序算法对比与总结(Python篇)

Python代码


排序算法对比与总结(Python篇)

基数排序

不需要直接对元素进行相互比较,也不需要将元素相互交换,你需要做的就是对元素进行“分类”。这也是基数排序的魅力所在,基数排序可以理解成是建立在“计数排序”的基础之上的一种排序算法。在实际项目中,如果对效率有所要求,而不太关心空间的使用时,我会选择用计数排序(当然还有一些其他的条件),或是一些计数排序的变形。

基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。

如果我们的无序是 T = [ 2314, 5428, 373, 2222, 17 ],那么其排序的过程就如下两幅所示。


排序算法对比与总结(Python篇)


上面这幅图,或许你已经在其他的博客里见到过。这是一个很好的引导跟说明。在基数排序里,我们需要一个很大的二维数组,二维数组的大小是 (10 * n)。10 代表的是我们每个元素的每一位都有 10 种可能,也就是 10 进制数。在上图中,我们是以每个数的个位来代表这个数,于是,5428 就被填充到了第 8 个桶中了。下次再进行填充的时候,就是以十位进行填充,比如 5428 在此时,就会选择以 2 来代表它。


排序算法对比与总结(Python篇)

基数排序过程图-1


排序算法对比与总结(Python篇)


基数排序过程图-2

排序算法对比与总结(Python篇)

python代码:

(原文:https://www.jianshu.com/p/0e6145fb6e1f)


推荐阅读:





扫码关注

版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《排序算法对比与总结(Python篇)》的版权归原作者「人工智能与大数据精选」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注人工智能与大数据精选微信公众号

人工智能与大数据精选微信公众号:PythonWithAI

人工智能与大数据精选

手机扫描上方二维码即可关注人工智能与大数据精选微信公众号

人工智能与大数据精选最新文章

精品公众号随机推荐