==冒泡排序(Bubble Sort)==也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。
比较相邻的元素。如果第一个比第二个大,就交换他们两个。
对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
针对所有的元素重复以上的步骤,除了最后一个。
持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
冒泡排序还有一种优化算法,就是立一个 flag,当在一趟序列遍历中元素没有发生交换,则证明该序列已经有序
直接返回就好
-
冒泡排序是一种非常容易理解的排序
-
时间复杂度:O(N^2)
-
空间复杂度:O(1)
-
稳定性:稳定
-
什么时候最快
当输入的数据已经是正序时(都已经是正序了,我还要你冒泡排序有何用啊)。 -
什么时候最慢
当输入的数据是反序时(写一个 for 循环反序输出数据不就行了,干嘛要用你冒泡排序呢,我是闲的吗)。
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止
📌思路一(Hoare版)
步骤为:
-
选取基准值
-
从数组右->左找到比基准值小于或等于的值的下标
-
从数组右->左找到比基准值大于或等于的值的下标
-
交换这两下标的值
-
继续执行二操作,直到操作2与操作3相遇
-
将基准值放在相遇位置
如下图所示:
📌思路二(挖坑法)
步骤为:
-
选取基准值后,记录下基准值,假设该下标为空,相当于是个“坑”
-
从右->左找小于或等于基准值的值,就将该数放入坑中,然后该下标变为新的坑
-
从左->右找小于或等于基准值的值,就将该数放入坑中,然后该下标变为新的坑
-
回到步骤2继续执行,直到操作2与操作3所找数相同
-
将记录下的基准值放回坑里
📌思路三(前后指针)
📌规模较小时的优化
每次递归的时候,数据都是再慢慢变成有序的
当数据量少且趋于有序的时候,我们可以直接使用插入排序进行优化
📌三数取中法
如果在选取基数时我们发现如果基数一边总是没有数,代码的执行次数会增加很多
所以我们的解决方法为:
选取数组第一个数、中间的数、和最后一个数,进行比较
三数中间的数作为每次的基数
寻找中间数代码如下:
使用如下:
实现思路:
-
建立一个栈
-
先让一组数据的起点入栈
-
再让一组数据的终点出栈
-
然后两次出栈,分别作为该数据的起点与终点
-
然后经过我们上面所写的方法进行排序后
-
再将两组数据进行入栈
-
以此循环直到栈为空
🚩代码实现:
-
快速排序整体的综合性能和使用场景都是比较好的,所以才敢叫快速排序
-
空间复杂度:O(logN)
-
稳定性:不稳定
-
申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;
-
设定两个指针,最初位置分别为两个已经排序序列的起始位置;
-
比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;
-
重复步骤 3 直到某一指针达到序列尾;
-
将另一序列剩下的所有元素直接复制到合并序列尾。
-
归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问题。
-
时间复杂度:O(N*logN)
-
空间复杂度:O(N)
-
稳定性:稳定
外部排序:排序过程需要在磁盘等外部存储进行的排序
前提:内存只有 1G,需要排序的数据有 100G
因为内存中因为无法把所有数据全部放下,所以需要外部排序,而归并排序是最常用的外部排序
-
先把文件切分成 200 份,每个 512 M
-
分别对 512 M 排序,因为内存已经可以放的下,所以任意排序方式都可以
-
进行 2路归并,同时对 200 份有序文件做归并过程,最终结果就有序了