常见的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,这时只分为一组,也就是整个序列,进行最后的排序。

    推荐阅读