基于比较的7种排序算法
冒泡排序BubbleSort
介绍
冒泡排序的原理比较简单,主要是两两比较,每次把比较大的数据放在后面,这样一次下来,最大的数就放在数组最后了。然后依次类推。
主要特性如下:
排序算法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
---|---|---|---|---|---|
冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
步骤
- 从索引为0的位置开始,往后依次两两比较,把大的数放在后面,小的数放在前面,这样一次下来最大的数就在数组末尾了(n);
- 最后一个数完成排序,退出排序工作,也就是令n–;
- 重复第一步,直到n=0;
源码
|
|
优化方案
- 每次排序,如果没有发生任何一次交换位置,说明已经是有序的了。因此可以用一个标识位记录是否交换了位置,如果没有则直接结束排序工作。
选择排序SelectionSort
介绍
选择排序每次用一个记录最小值的下标,然后把下标和前面未排序的序列中的第一个数据交换位置。依次类推。
主要特性如下:
排序算法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
---|---|---|---|---|---|
选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 稳定 |
步骤
- 在未排序序列中找到最小元素,存放到排序序列的起始位置。
- 再从剩余未排序元素中继续寻找最小元素,然后放到已排序序列的末尾
- 重复上面2个步骤,直到所有元素均排序完毕。
源码
|
|
插入排序InsertionSort
介绍
插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。
—摘自维基百科
主要特性如下:
排序算法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
---|---|---|---|---|---|
插入排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
步骤
- 从第一个元素开始,认为是有序的;
- 取出下一个元素继续,往前面比较,如果遇到比新元素小的,则把该元素往后移动一位;
- 重复步骤2,直到找到已排序中小于或等于新元素的位置;
- 把新元素插入到该位置中;
- 重复步骤2-5;
源码
|
|
希尔排序ShellSort
介绍
希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的:
- 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率
- 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位
—摘自维基百科
主要特性如下:
排序算法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
---|---|---|---|---|---|
希尔排序 | O(nlogn)~O(n^2) | O(n^1.3) | O(n^2) | O(1) | 不稳定 |
步骤
- 假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ],如果我们以步长为5开始进行排序,我们可以通过将这列表放在有5列的表中来更好地描述算法,这样他们就应该看起来是这样:
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
- 然后我们对每列进行排序:
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
- 将上述四行数字,依序接在一起时我们得到:[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了,然后再以3为步长进行排序:
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
- 排序之后变为:
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
- 最后以1步长进行排序(此时就是简单的插入排序了)。
源码
|
|
归并排序MergeSort
介绍
归并排序(英语:Merge sort,或mergesort),是创建在归并操作上的一种有效的排序算法,效率为O(nlogn)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。
— 摘自维基百科
主要特性如下:
归并算法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
---|---|---|---|---|---|
归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
步骤
- 先考虑合并2个有序数组:基本思路是比较2个数组中最前面的数,谁小就取谁并填到合并数组中,取后其数组索引往后移动一位。然后再重新比较,直到其中的一个数组为空,最后把另一个数组的多出来的元素直接复制到合并数组中。
- 再考虑递归分解:基本思路是把数组分解为左右2个数组,然后再对这2个数组递归分解,直到分解出来的数组只有1个元素,此时可认为这个数组是有序的,然后执行上面的合并步骤即可。
源码
|
|
堆排序HeapSort
介绍
堆排序在top问题中使用比较频繁。堆排序是使用二叉树来实现的,不过实质上还是二维数组。二叉树是一个近似完全二叉树。
堆中二叉树特性(序号从0开始):
- 父节点的键值总是>=(<=)任何一个子节点的键值;
- 每个节点的左右子树都是一个二叉堆(都是最大堆或最小堆);
- 树里面每个节点的子女和双亲节点都可以根据当前节点的序号求出:
- parent(i) = (i-1)/2;
- left(i) = 2*i + 1;
- right = 2*i + 2;
- 非叶子节点 = n / 2 -1;
堆排序主要特性如下:
排序算法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
---|---|---|---|---|---|
堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
步骤
- 构造最大堆:若数组长度为size,因为单个元素(也就是叶子节点)可以看成是最大堆,则从size/2开始的元素是最大堆。于是从size/2-1开始,向前依次构造最大堆,这样就能保证,构造到某一个点,它的左右子树都是最大堆。
- 堆中排序:由于堆是用数组模拟的。得到一个大根堆后,数组内部并不是有序的。因此需要将堆化数组有序化。思想是移除根节点,并做最大堆调整的递归运算。第一次将heap[0]与heap[n-1]交换,再对heap[0…n-2]做最大堆调整。第二次将heap[0]与heap[n-2]交换,再对heap[0…n-3]做最大堆调整。重复该操作直至heap[0]和heap[1]交换。由于每次都是将最大的数并入到后面的有序区间,故操作完后整个数组就是有序的了。
- 最大堆调整(Max_Heapify):该方法是提供给上述两个过程调用的。目的是将堆的末端子节点作调整,使得子节点永远小于父节点 。
源码
|
|
快速排序QuickSort
介绍
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n^2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n)算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。
—摘自维基百科
快排通常明显比其他nlog(n)的算法更快,所以被广泛引用。在笔试的过程中更是可以说是必考。可见掌握快排的重要性。快排主要特性如下:
排序算法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
---|---|---|---|---|---|
快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(logn)~O(n) | 不稳定 |
步骤
- 选定基准数:从数组中选出一个元素作为基准数;
- 分区过程:将比基准数大的放在右边,小于或等于基准数的放在左边;
- 再对左右区间递归执行第二步,直至各个区间都只有一个元素;
源码(Java)
|
|
总结
排序算法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
---|---|---|---|---|---|
冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 稳定 |
插入排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
希尔排序 | O(nlogn)~O(n^2) | O(n^1.3) | O(n^2) | O(1) | 不稳定 |
归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(logn)~log(n) | 不稳定 |