锐客网

  1. 首页 > it技术 > >

常见的7种排序算法

【常见的7种排序算法】1.冒泡排序
算法思想
冒泡排序，是对序列进行遍历，遍历过程中如果发现相邻两个元素，满足比较条件，则进行交换，一次遍历之后最大的元素被移动到队尾，然后进行第二次遍历，直到序列有序。
2.选择排序
算法思想
选择排序，是先找到起始序列中最小的元素，将它交换到i=0；然后寻找剩下元素中最小的元素，将它交换到i=1的位置…… ，直到找到第二大的元素，将它交换到n-2的位置。这时，整个序列的排序完成。
3.快速排序
算法思想
快速排序，是任意设置一个基准元素，一般是第一个或者最后一个，将序列以该基准元素为基准，分割成比他小的一部分和比他大的一部分，此时，该基准元素所在的位置就是排序终了之后的准确位置，再对左右两边的序列继续执行同样的操作，直到整个序列有序。
4.插入排序
算法思想
插入排序，是将序列的第一个元素当做已经排序好的序列，然后从后面的第二个元素开始，逐个元素进行插入，直到整个序列有序为止。
5.堆排序
算法思想
堆，是一种数据结构，是用数组表示的完全二叉树。堆分为大根堆和小根堆。堆排序，是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。
大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。
排序思想：以正排为例，
1）将堆排列成大根堆，这时，根就是数组中的最大值；
2）将根(最大值)与末位(堆的最后一个节点，也是数组的最后一个元素)，这时最大值就放在了最后；
3）将堆排除掉一个节点(也就是数组的最后一个元素)，继续1），2）步操作，这样就会将数组中第二大的元素放到倒数第二位；
4）如此循环，直到排序完成。
6.归并排序
算法思想
归并排序，是对序列进行拆分再拆分，直到不能再拆分，然后分别对最小粒度的子序列进行合并，然后再合并稍微大一点的序列，直到最终合成一个最大的序列。
分两个函数完成，一个负责拆分，一个负责排序合并。
7.希尔排序
算法思想
希尔排序，是将序列按照下标增量分组进行排序，增量值从 len(list)//2 到 1
举例说明，假定有一个长度为10的序列 l，进行希尔排序。
第一轮：增量为5，将l[0]与l[5]，l[1]与l[6]，…，l[4]与l[9]进行分组，每组分别进行排序；
第二轮：增量为4，将l[0]与l[4]与l[8]，l[1]与l[5]与l[9]，…，l[3]与l[7]进行分组，每组分别进行排序；
……
直到增量为1，这时只分为一组，也就是整个序列，进行最后的排序。

    推荐阅读


    上一篇：centos之上|docker从安装到简单使用（初级）

    下一篇：智能运维|嘉为蓝鲸助力某通信集团实现多类型应用发布自动化