起因
前几天和后端联调的时候,在空闲时间闲聊,不知怎么就聊到了归并排序,然后就瞎扯了一通时间复杂度,空间复杂度什么的,最后说到了归并排序在实际的应用,就是内存有限的情况下,大文件的排序。然后我就觉得,有些东西还是挺有用挺值得牢记的,就算短时间用不到,最好也还是不要忘,虽然大学学的很多东西,好多都因为暂时没用,还给老师了呢,比如计算机组成原理,操作系统,计算机系统结构等,觉得很是惭愧,于是就趁着周末看了下箱底的书,温习了一遍以前的一些基本算法,后来觉得还是要做一个沉淀写成博客会比较好,所以我就写了这篇博客,来提醒自己不要忘记。
插入排序
算法描述:
1.从第一个元素开始,默认为该元素已经被排序。
2.取出下一个元素,在已经排序的元素序列中从后向前扫描。
3.如果该元素(已排序)大于新元素,将该元素移到下一位置。
4.重复步骤 3,直到找到已排序的元素小于或者等于新元素的位置。
5.将新元素插入到该位置后。
6.重复步骤 2~5。
|
|
这个排序的核心编程思路就是双层循环,外循环控制未排序的元素,内循环控制已排序的元素,将未排序元素设为标杆,与已排序的元素进行比较,小于则交换位置,大于则位置不动。时间复杂度O(n^2),具体代码实现如下:
|
|
选择排序
这个排序和插入排序的相似度很高,唯一不同的是,插入排序的方式是从第一个开始,然后选第二个,第三个。。。按照各元素的位置来选,而选择排序的意思就是,每次选的时候,都选择的是余下数组中最大(最小)的那个数,我还是以上面的数组来举个例子。
|
|
这个算法的时间复杂度也是O(n^2),具体代码实现见下面:
|
|
归并排序
归并排序最大的意义就是化大为小,当你的资源(内存)不能够满足你一次性将所有的数据都排序完的时候,你就需要采用归并排序。
算法描述:
1.把 n 个记录看成 n 个长度为 1 的有序子表
2.进行两两归并使记录关键字有序,得到 n/2 个长度为 2 的有序子表
3.重复第 2 步直到所有记录归并成一个长度为 n 的有序表为止。
老规矩,再以上面的数组来进行示例,7,3,1,2,9,6,8。
|
|
这个算法的时间复杂度为O(nlogn),具体代码实现如下:
|
|
冒泡排序
这个属于最基本的一个排序方法,我现在还记得教科书上是怎么写的它的概念,它的核心理念就是两两相互比较,满足条件就不断向前比,直到比完所有的数,然后再进行下一次比较。
由于这个太简单,时间复杂度为O(n^2),我就不写示例,直接上代码吧:
|
|
快速排序
这算是排序算法中,效率最高,最经典,最有名,最广泛的一个排序方法了,所以我准备好好来讲讲快排。
算法描述:
在所需的排序数组之中,选择一个元素作为”基准”(pivot),可以随机选择,也可以选第一个或最后一个。
选中了基准值后,将剩下的值分别与这个选中的基准值做比较,将剩下的值按照大于或小于等于基准值分为两部分。
比如可以将所有小于基准的元素,都移到基准的左边;所有大于基准的元素,都移到基准的右边。这个操作称为分区 (partition)操作,分区操作结束后,基准元素所处的位置就是最终排序后它的位置。
对基准左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。
快排的时间复杂度是O(nlogn),老样子,我用之前的数组来作为示例,7,3,1,2,9,6,8,5。
|
|
具体的代码实现如下:
|
|