作者 | 铁猴
责编 | 屠敏
出品 | CSDN 博客
1.简介
本文对常见排序算法进行总结。
2.排序算法
冒泡排序
该算法比较简单,几乎所有语言涉及到算法时,都会涉及到冒泡算法。
算法思路:
比较相邻的元素。如果第一个比第二个大,就交换他们两个。
对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤,除了最后一个。
持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
选择排序
每次选择一个最大(小)的,直到所有元素都被输出。
可参考:https://blog.csdn.net/sun7545526/article/details/85165618
直接插入排序
插入排序的基本方法是:每一步将一个待排序的元素,按其排序码的大小,插入到前面已经排好序的一组元素的适当位置上去,直到元素全部插入为止
算法思路:
当插入第i(i >= 1)时,前面的V[0],V[1],……,V[i-1]已经排好序。这时,用V[I]的排序码与V[i-1],V[i-2],…的排序码顺序进行比较,找到插入位置即将V[i]插入,原来位置上的元素向后顺移。
以[21,25,49,25,16,08]为例,排序过程如下所示:
在小规模数据集或是基本有序时,该算法效率较高。
希尔排序
先对数据进行预处理,使其基本有序,然后再用直接插入排序算法排序。
详细过程可参考:https://blog.csdn.net/eric_sunah/article/details/103080731
快速排序
利用“分而治之”的思想对集合进行排序
可参考:https://blog.csdn.net/sun7545526/article/details/85165742
堆排序
说堆排序前,先说下啥是堆。
堆:堆是满足下列性质的完全二叉树:
每个节点都大于或是等于其左右孩子节点的值,称为大顶堆
每个节点都小于或是等于其左右孩子节点的值,称为小顶堆
接下来说下堆是如何做排序的,思路如下(以大顶堆为例):
根节点是整个堆的最大值,将它移走。
将剩余n-1个节点重新构造成一个堆,再将根节点移走
重复执行1,2。直到没有节点可移动,就生成了有序序列。
该算法有两个需要解决问题:
如何将一个无序序列构建一个堆。
移除根节点后,如何用剩余的节点重建堆。
详细介绍参见:https://blog.csdn.net/eric_sunah/article/details/103081878
归并排序
归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。
详细介绍参见:https://blog.csdn.net/eric_sunah/article/details/103082607
3.总结
分类总结:
时间复杂度总结:
版权声明:本文为CSDN博主「铁猴」加入原力计划的原创文章。