|
|
前言
拾级聚足，连步以上。---- 《礼记曲礼上》 这是「算法拾级」十大排序系列文章第零篇。本篇介绍十大算法的分类和基本内容，并作为总索引说明后续篇章的安排，给出总结性质的各大排序算法的平均、最好、最差时间复杂度和空间复杂度。正式进入排序算法之前，还会介绍排序算法中用于交换数组中两个元素的交换方法的三种不同的实现。
本系列所有文章链接放于文末。
排序分类及章节安排
十大排序算法
准备发布排序算法系列文章时，如何分篇推出竟是件破费踌躇的事。一开始想按照比较排序中的O(n^2)排序(冒泡/选择/插入)、非O(n^2)排序(希尔/归并/快速/堆)、非比较排序(计数/基数/桶)的分类以三篇较饱满的文章呈现，但第二篇的篇幅将会过长，对于只想查看某一具体算法的人来说容易失焦。也想过按内容多寡将O(n^2)排序(冒泡/选择/插入)写成一篇，其余单独成篇，但这种分法又缺乏逻辑。思来想去最终还是决定每个算法单独成篇，便于聚焦每一个排序算法的内容，后续若有内容扩展，也不会使单篇文章过于冗长，这么一来还有点“高内聚低耦合”的效果。
上图是十大排序的分类，也是本次系列所有文章将要介绍的内容的一个总括。十大排序中有7个基于比较，另有3个非比较排序。首先介绍比较排序中的前三个，即时间复杂度为O(n^2)的冒泡、选择、插入排序，接着介绍插入算法的一种突破了二次时间复杂度的希尔排序，然后是三种时间复杂度为O(nlogn)的排序算法，即归并、快速和堆排序，最后是计数、基数和桶排序这三种非比较排序。
每一篇介绍一种排序算法的文章都会按照如下结构呈现。“算法描述”将介绍算法的具体操作过程，并配以动图帮助理解；“算法优化”将介绍该排序的优化版本；“复杂度分析”将给出时间和空间复杂度的说明或证明，若有不同版本，一并给出；“代码实现”将给出经过验证的可用Java代码，若有不同版本，一并给出。
复杂度和稳定性总结
| 十大排序 | 平均时间 | 最好时间 | 最坏时间 | 空间 | 稳定性 | 备注 | | 冒泡(bubble) | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 | ※1 | | 选择(select) | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 | ※2 | | 插入(insert | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 | ※3 | | 希尔(shell) | O(nlogn) ~ O(n^2) O(nlog3n) ~ O(n^3/2) | O(nlogn) O(nlog3n) | O(n^2) O(n^3/2) | O(1) | 不稳定 | ※4 | | 归并(merge) | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 | ※5 | | 快速(quick) | O(nlogn) | O(nlogn) | O(n^2) | O(logn) | 不稳定 | ※6 | | 堆(heap) | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 | ※7 | | 计数(count) | O(n + k) | O(n + k) | O(n + k) | O(n + k) | 稳定 | ※8 | | 基数(radix) | O(d(n + k)) | O(d(n + k)) | O(d(n + k)) | O(n + k) | 稳定 | ※9 | | 桶(bucket) | O(n) | O(n) | O(n^2) / O(nlogn) | O(n) | 稳定 | ※10 |
※1：输入数组已排序时最好。
※2: 时间复杂度与输入数组特点无关。
※3: 输入数组已排序时最好。
※4: 复杂度取决于增量序列，上为希尔增量，下为Knuth增量。输入数组已排序时最好。
※5: 所列复杂度为自顶向下非原地版本。自顶向下/自底向上，非原地/原地的时间空间复杂度见该算法文章。
※6: 当输入数组有序，且总是选取第一个元素为主轴时时间复杂度退化为O(n^2)。空间开销为递归深度。
※7: 原地堆排序空间复杂度为O(1)，若输入数组所有数字相等，则时间复杂度为O(n)。
※8: k是计数数组大小。应用稳定性优化则稳定，否则不稳定。朴素版本空间复杂度为O(k)，稳定性优化版本空间复杂度为O(n + k)。
※9: d是最大数位数，k是计数数组大小，处理负数时k=19。采用稳定的计数排序则稳定，否则不稳定。
※10: 稳定性取决于桶内排序是否稳定。空间取决于桶使用数组还是容器，若采用数组为O(kn)，容器则为O(n)。
所有元素放入同一个桶时复杂度最大。三种交换方法
对于冒泡、选择、插入等采用比较和交换元素的排序方法，由于经常执行交换操作，通常将交换动作写为swap方法，需要交换时再调用。最常见swap写法是利用一个临时数tmp来交换arr，arr[j]。也可以通过arr和和arr[j]的加减运算避免临时数tmp的开销，但由于涉及到加减法可能导致数字越界。第三种方法利用位运算中的异或运算，能够避免tmp的开销且不会导致数字越界。
// 方法一: 利用临时数tmp
private void swapWithTmp(int[] arr, int i, int j) {
int tmp = arr;
arr = arr[j];
arr[j] = tmp;
}
// 方法二: 利用加减运算
private void swapByCal(int[] arr, int i, int j) {
arr = arr + arr[j]; // a = a + b
arr[j] = arr - arr[j]; // b = a - b
arr = arr - arr[j]; // a = a - b
}/span>
<span class="c1">// 方法三: 利用异或运算
private void swapXOR(int[] arr, int i, int j) {
arr = arr ^ arr[j]; // a = a ^ b，也可写成 arr ^= arr[j];
arr[j] = arr ^ arr[j]; // b = (a ^ b) ^ b = a ^ (b ^ b) = a ^ 0 = a， 也可写成 arr[j] ^= arr;
arr = arr ^ arr[j]; // a = (a ^ b) ^ a = (a ^ a) ^ b = 0 ^ b = b， 也可写成 arr ^= arr[j];
}
开篇到此结束，欢迎通过如下链接阅读本系列其他文章。
十大排序算法系列文章链接：
[算法拾级]十大排序(零)开篇
[算法拾级]十大排序(一)冒泡排序
[算法拾级]十大排序(二)选择排序
[算法拾级]十大排序(三)插入排序
[算法拾级]十大排序(四)希尔排序
[算法拾级]十大排序(五)归并排序
[算法拾级]十大排序(六)快速排序
[算法拾级]十大排序(七)堆排序
[算法拾级]十大排序(八)计数排序
[算法拾级]十大排序(九)基数排序
[算法拾级]十大排序(十)桶排序 |
本帖子中包含更多资源
您需要 登录 才可以下载或查看，没有账号？立即注册
×
|
窥视卡
雷达卡
发表于 2022-3-13 13:39
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
显身卡