锐客网

  1. 首页 > 睿知 > it技术 > >

python算法必会函数 python数学计算函数( 七 )

IT技术算法


·插入排序在对几乎已经排好序的数据操作时，效率高， 即可以达到线性排序的效率；
·但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位 。
基本思想
①希尔排序是把记录按下标的一定量分组，对每组使用直接插入算法排序；
②随着增量逐渐减少，每组包1含的关键词越来越多 ， 当增量减至1时，整个文件恰被分成一组，算法被终止 。
排序演示
算法实现
五、选择排序
介绍
选择排序(Selection sort)是一种简单直观的排序算法 ， 时间复杂度为Ο(n2) 。
基本思想
选择排序的基本思想：比较 + 交换 。
第一趟，在待排序记录r1 ~ r[n]中选出最小的记录，将它与r1交换；
第二趟，在待排序记录r2 ~ r[n]中选出最小的记录 ， 将它与r2交换；
以此类推，第 i 趟，在待排序记录ri ~ r[n]中选出最小的记录，将它与r[i]交换,使有序序列不断增长直到全部排序完毕 。
排序演示
选择排序的示例动画 。红色表示当前最小值，黄色表示已排序序列 ， 蓝色表示当前位置 。
算法实现
六、堆排序
介绍
堆排序（Heapsort）是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种 。
利用数组的特点快速指定索引的元素 。
基本思想
堆分为大根堆和小根堆，是完全二叉树 。
大根堆的要求是每个节点的值不大于其父节点的值，即A[PARENT[i]] =A[i] 。
在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶 。
排序演示
算法实现
七、归并排序
介绍
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法 。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用 。
基本思想
归并排序算法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的 。然后再把有序子序列合并为整体有序序列 。
算法思想
自上而下递归法（假如序列共有n个元素）
① 将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列 ， 排序后每个序列包含两个元素；
② 将上述序列再次归并，形成 floor(n/4)个序列 ， 每个序列包含四个元素；
③ 重复步骤②，直到所有元素排序完毕 。
自下而上迭代法
① 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
② 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
③ 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
④ 重复步骤③直到某一指针达到序列尾；
⑤ 将另一序列剩下的所有元素直接复制到合并序列尾 。
排序演示
算法实现
八、基数排序
介绍
基数排序（Radix Sort）属于“分配式排序” ， 又称为“桶子法” 。
基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中 r 为采取的基数 ， 而m为堆数 。
在某些时候，基数排序法的效率高于其他的稳定性排序法 。
基本思想
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零 。然后，从最低位开始 ， 依次进行一次排序 。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列 。
基数排序按照优先从高位或低位来排序有两种实现方案：

推荐阅读


上一篇：追剧助手下载ios，追剧软件下载ios

下一篇：腾讯游戏出的飞行游戏，腾讯飞行类游戏