Python进阶系列: 实现各种排序算法
选择排序(Selection Sort):
插入排序(Insertion Sort):
基本思想:将一个记录插入到已经排好序的有序表中,从而得到一个新的,录数增1的有序表。你可以把这种排序想象成整理扑克牌,当你拿到一个新牌要插入已排好序的一把牌中。
希尔排序(Shell Sort):
基本思想:分组插入排序,即通过将数据分成不同的组,先对每一组进行排序,然后再对所有的元素进行一次插入排序,以减少数据交换和移动的次数。
归并排序(Merge Sort):
基本思想:它的中心思想就是先递归分解数组,再合并数组,这是分治法的一个非常典型的应用。先分解要排序的序列,从1分成2,2分成4,依次分解,当分解到只有1个一组的时候,就可以排序这些分组,然后依次合并回原来的序列中,这样就可以排序所有数据。分治法是一种算法设计策略。它的思想是将原始问题划分为n个规模较小且与原问题相似的子问题,然后递归的解决子问题,再合并结果,即得到原问题的解。大体上,每一层递归都包含三个步骤:分解,解决,合并。
快速排序(Quick Sort):
基本思想:它也是分治法的一个典型应用。
步骤:
从数列中挑出一个元素作为基准数。
分区过程,将比基准数大的放到右边,小于或等于它
一个数。
堆排序(Heap Sort):
基本思想:采用堆的数据结构进行排序。在堆排序中,用到的是最大堆,即父节点的数要大于其子节点的数值,每个节点的值至多和其父节点的值一样大,堆中的最大元素存放在根节点中。
下面列出了堆排序中的一些基本过程:
构造最大堆(Build_Max_Heap):若数组下标范围为0~n,考虑到单独一个元素是最大堆,则从下标n/2开始的元素均为最大堆。于是只要从n/2-1开始,向前依次构造最大堆,这样就能保证,构造到某个节点时,它的左右子树都已经是最大堆。
堆排序(HeapSort):得到一个最大堆后,每次从根部移除一个节点,但是剩余的元素仍然要保持最大堆的特性。
最大堆调整(Max_Heapify):该方法是提供给上述两个过程调用的。目的是将堆的末端子节点作调整,使得子节点永远小于父节点。若某个节点的位置为i,那么它的左节点位置为2i,右节点的位置为2i+1。
- 点赞
- 收藏
- 关注作者
评论(0)