面试必会八大排序算法(Python)

发布于:2019-05-23   编辑:admin 浏览:

  插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据。

  冒泡排序(Bubble Sort)是一种简单的排序算法,时间复杂度为O(n^2)。

  它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。

  需要使用嵌套循环实现:外层循环控制总循环次数,内层循环负责每轮的循环比较。

  ②对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。

  ④持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

  快速排序(Quicksort)是对冒泡排序的一种改进,借用了分治的思想,由C. A. R. Hoare在1962年提出。

  首先选出一个轴值(pivot,也有叫基准的),通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

  ②重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边);

  希尔排序(Shell Sort)是插入排序的一种,也是缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法,时间复杂度为:O(1.3n)。

  ·插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率;

  ②随着增量逐渐减少,每组包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)的一个非常典型的应用。

  归并排序算法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

  ① 将序列每相邻两个数字进行归并操作,形成 floor(n/2)个序列,排序后每个序列包含两个元素;

  ② 将上述序列再次归并,形成 floor(n/4)个序列,每个序列包含四个元素;

  ① 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;

  ③ 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;

  基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m) ,其中 r 为采取的基数,而m为堆数。

  将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

  MSD(Most significant digital) 从最左侧高位开始进行排序。先按k1排序分组, 同一组中记录, 关键码k1相等,再对各组按k2排序分成子组, 之后, 对后面的关键码继续这样的排序分组, 直到按最次位关键码kd对各子组排序后. 再将各组连接起来,便得到一个有序序列。MSD方式适用于位数多的序列。

  LSD (Least significant digital)从最右侧低位开始进行排序。先从kd开始排序,再对kd-1进行排序,依次重复,直到对k1排序后便得到一个有序序列。LSD方式适用于位数少的序列。

  \u2463\u6301\u7eed\u6bcf\u6b21\u5bf9\u8d8a\u6765\u8d8a\u5c11\u7684\u5143\u7d20\u91cd\u590d\u4e0a\u9762\u7684\u6b65\u9aa4\uff0c\u76f4\u5230\u6ca1\u6709\u4efb\u4f55\u4e00\u5bf9\u6570\u5b57\u9700\u8981\u6bd4\u8f83\u3002

  \u5404\u79cd\u6392\u5e8f\u7684\u7a33\u5b9a\u6027\u3001\u65f6\u95f4\u590d\u6742\u5ea6\u3001\u7a7a\u95f4\u590d\u6742\u5ea6\u7684\u603b\u7ed3\uff1a

  点击“提交”后,我们会向您的邮箱发送一封验证邮件,请按照邮件中的提示完成操作。