深圳做生鲜食材的网站叫什么,wordpress 清理,国外网站建站,产品工艺设计文章目录0.算法概述0.1 算法分类0.2 算法复杂度0.3 相关概念1. 冒泡排序#xff08;Bubble Sort#xff09;1.1 算法描述#xff1a;1.2 图解演示1.3 代码实现1.4 优化过程1.5 性能分析2. 选择排序#xff08;Selection Sort#xff09;2.1 算法描述#xff1a;2.2 图解演…
文章目录0.算法概述0.1 算法分类0.2 算法复杂度0.3 相关概念1. 冒泡排序Bubble Sort1.1 算法描述1.2 图解演示1.3 代码实现1.4 优化过程1.5 性能分析2. 选择排序Selection Sort2.1 算法描述2.2 图解演示2.3 代码实现2.4 优化过程2.5 性能分析2.6 拓展3. 插入排序Insertion Sort3.1 算法描述3.2 图解演示3.3 代码演示3.4 优化过程3.5 性能分析3.6 应用分析4.快速排序Quick Sort4.1算法描述4.2 图解演示4.3 代码实现①快速排序递归框架②退出递归的边界条件③基数的选择④分区算法实现⑤最简单的分区算法⑥双指针分区算法4.4 性能分析4.5快速排序的优化思路5.希尔排序Shell Sort5.1 算法描述5.2 图解演示5.3 代码实现5.4 优化过程5.5增量序列5.6 性能分析5.7 希尔排序与 O(n^2)级排序算法的本质区别6.归并排序Merge Sort6.1算法描述6.2 算法图解6.3 代码实现6.4 性能分析6.5 应用分析7.堆排序Heap Sort7.1算法描述7.2图解演示7.3 代码实现7.4 性能分析8.计数排序Counting Sort8.1算法描述8.2 图解演示8.3代码实现8.4 性能分析8.5 拓展9.基数排序Radix Sort9.1 算法描述9.2 图解演示9.3 代码实现9.4 对包含负数的数组进行基数排序9.5 LSD VS MSD9.6 性能分析10.桶排序Bucket Sort10.1 算法描述10.2 图解演示10.3 代码实现10.4 性能分析10.5 拓展11.非比较类排序算法总结0.算法概述
0.1 算法分类
1、时间复杂度O(n^2)级排序算法
选择排序插入排序冒泡排序
2、时间复杂度O(nlogn)级排序算法
快速排序希尔排序归并排序堆排序
3、时间复杂度O(n)级排序算法
桶排序基数排序计数排序
4、比较类排序
交换排序 冒泡排序 Bubble Sort快速排序 Quick Sort 插入排序 简单插入排序 Insertion Sort希尔排序 Shell Sort 选择排序 简单选择排序 Selection Sort堆排序 Heap Sort 归并排序 二路归并排序 Merge Sort多路归并排序 Merge Sort 非比较排序 计数排序 Counting Sort基数排序 Radix Sort桶排序 Bucket Sort
0.2 算法复杂度 0.3 相关概念
时空复杂度
时间复杂度时间随着问题数据规模的扩大而如何变化的一般讲时间复杂度都是讲”最坏“的
不考虑必须要做的操作循环、赋初值、程序初始化-----O(1)不考虑常数项2n ----- n不考虑低次项n^2n----- n^2
空间复杂度算法需要用到的额外空间不包括该问题必须分配的空间
分类 非线性时间比较类排序通过比较来决定元素间的相对次序由于其时间复杂度不能突破O(nlogn)因此称为非线性时间比较类排序 线性时间非比较类排序不通过比较来决定元素间的相对次序它可以突破基于比较排序的时间下界以线性时间运行因此称为线性时间非比较类排序 内排序所有排序操作都在内存中完成 外排序由于数据太大因此把数据放在磁盘中而排序通过磁盘和内存的数据传输才能进行
稳定性
假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i] r[j]且 r[i] 在 r[j] 之前而在排序后的序列中r[i] 仍在 r[j] 之前则称这种排序算法是稳定的否则称为不稳定的。
推荐的标准来源于面试笔试的考察情况
冒泡排序 ■■□□□ 快速排序 ■■■■■ 插入排序 ■■■□□ 希尔排序 ■□□□□ 归并排序 ■■■■■ 选择排序 ■■□□□ 堆排序 ■■■■□ 计数排序 ■■□□□ 基数排序 ■□□□□ 桶排序 ■□□□□ 根据上面的情况相信你会有所侧重地学习排序算法。
1. 冒泡排序Bubble Sort 依次比较两个相邻的元素如果顺序如从大到小、首字母从Z到A错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换也就是说该元素列已经排序完成。 1.1 算法描述
比较相邻的元素。如果第一个比第二个大就交换他们两个对每一对相邻元素做同样的工作从开始第一对到结尾的最后一对。在这一点最后的元素应该会是最大的数针对所有的元素重复以上的步骤除了最后一个持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较
1.2 图解演示 1.3 代码实现
冒泡排序第一种写法
代码如下
public static void bubbleSort(int[] arr) {for (int i 0; i arr.length - 1; i) {for (int j 0; j arr.length - 1 - i; j) {if (arr[j] arr[j 1]) {// 如果左边的数大于右边的数则交换保证右边的数字最大swap(arr, j, j 1);}}}
}
// 交换元素
private static void swap(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;
}1.4 优化过程 一边比较一边向后两两交换将最大值 / 最小值冒泡到最后一位 经过优化的写法使用一个变量记录当前轮次的比较是否发生过交换如果没有发生交换表示已经有序不再继续排序 进一步优化的写法除了使用变量记录当前轮次是否发生交换外再使用一个变量记录上次发生交换的位置下一轮排序时到达上次交换的位置就停止比较 最外层的 for 循环每经过一轮剩余数字中的最大值就会被移动到当前轮次的最后一位中途也会有一些相邻的数字经过交换变得有序。总共比较次数是 (n-1)(n-2)(n-3)…1(n−1)(n−2)(n−3)…1。
冒泡排序第二种写法
第二种写法是在第一种写法的改良基础下而来代码如下
public static void bubbleSort(int[] arr) {// 初始时 swapped 为 true否则排序过程无法启动boolean swapped true;for (int i 0; i arr.length - 1; i) {// 如果没有发生过交换说明剩余部分已经有序排序完成if (!swapped) break;// 设置 swapped 为 false如果发生交换则将其置为 trueswapped false;for (int j 0; j arr.length - 1 - i; j) {if (arr[j] arr[j 1]) {// 如果左边的数大于右边的数则交换保证右边的数字最大swap(arr, j, j 1);// 表示发生了交换swapped true;}}}
}最外层的 for 循环每经过一轮剩余数字中的最大值仍然是被移动到当前轮次的最后一位。这种写法相对于第一种写法的优点是如果一轮比较中没有发生过交换则立即停止排序因为此时剩余数字一定已经有序了。
看下动图演示 图中可以看出
第一轮排序将数字 66 移动到最右边 第二轮排序将数字 55 移动到最右边同时中途将 11 和 22 排了序 第三轮排序时没有发生交换表明排序已经完成不再继续比较。
冒泡排序的第三种写法
第三种写法比较少见它是在第二种写法的基础上进一步优化
经过再一次的优化代码看起来就稍微有点复杂了。最外层的 while 循环每经过一轮剩余数字中的最大值仍然是被移动到当前轮次的最后一位。
在下一轮比较时只需比较到上一轮比较中最后一次发生交换的位置即可。因为后面的所有元素都没有发生过交换必然已经有序了。
最好情况在数组已经有序的情况下只需遍历一次由于没有发生交换排序结束。 最差情况数组顺序为逆序每次比较都会发生交换。 代码如下
public static void bubbleSort(int[] arr) {boolean swapped true;// 最后一个没有经过排序的元素的下标int indexOfLastUnsortedElement arr.length - 1;// 上次发生交换的位置int swappedIndex -1;while (swapped) {swapped false;for (int i 0; i indexOfLastUnsortedElement; i) {if (arr[i] arr[i 1]) {// 如果左边的数大于右边的数则交换保证右边的数字最大swap(arr, i, i 1);// 表示发生了交换swapped true;// 更新交换的位置swappedIndex i;}}// 最后一个没有经过排序的元素的下标就是最后一次发生交换的位置indexOfLastUnsortedElement swappedIndex;}
}1.5 性能分析
时间复杂度、空间复杂度 第一种写法的比较次数为 (n-1)(n-2)(n-3)…1总比较次数为 (n^2)/2所以时间复杂度为 O(n^2)使用空间只有 i、j 两个变量所以空间复杂度为 O(1); 第二种写法在数组已经有序的情况下比较次数为 n-1只需比较一轮即可完成排序此时时间复杂度为 O(n)最坏的情况和第一种写法一样平均时间复杂度仍是 O(n^2)使用的空间最多 i、j、swapped、temp 四个变量最好的情况下只有 i、j、swapped 三个变量所以空间复杂度为 O(1); 第三种写法时间复杂度和第二种写法一样平均时间复杂度是 O(n^2)只是实际运行效率比第二种写法好一些使用的空间最多 swapped、indexOfLastUnsortedElement、swappedIndex、i、temp 五个变量最好的情况下没有 temp 变量所以空间复杂度为 O(1)。
稳定性
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较交换也发生在这两个元素之间。所以如果两个元素相等是不会再交换的如果两个相等的元素没有相邻那么即使通过前面的两两交换把两个相邻起来这时候也不会交换所以相同元素的前后顺序并没有改变所以冒泡排序是一种稳定排序算法。
2. 选择排序Selection Sort 选择排序Selectionsort是一种简单直观的排序算法。它的工作原理是第一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置然后再从剩余的未排序元素中寻找到最小大元素然后放到已排序的序列的末尾。以此类推直到全部待排序的数据元素的个数为零。 2.1 算法描述
n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下
初始状态无序区为N[1…n]有序区为空第i趟排序(i1,2,3…n-1)开始时当前有序区和无序区分别为N[1…i-1]和N(i…n。该趟排序从当前无序区中选出关键字最小的记录 N[m]将它与无序区的第1个记录N交换使N[1…i]和N[i1…n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区n-1趟结束数组有序化了。
2.2 图解演示 2.3 代码实现
public static void selectionSort(int[] arr) {int minIndex;for (int i 0; i arr.length - 1; i) {minIndex i;for (int j i 1; j arr.length; j) {if (arr[minIndex] arr[j]) {// 记录最小值的下标minIndex j;}}// 将最小元素交换至首位int temp arr[i];arr[i] arr[minIndex];arr[minIndex] temp;}
}2.4 优化过程
二元选择排序
选择排序算法也是可以优化的既然每轮遍历时找出了最小值何不把最大值也顺便找出来呢这就是二元选择排序的思想。
使用二元选择排序每轮选择时记录最小值和最大值可以把数组需要遍历的范围缩小一倍。
public static void selectionSort2(int[] arr) {int minIndex, maxIndex;// i 只需要遍历一半for (int i 0; i arr.length / 2; i) {minIndex i;maxIndex i;for (int j i 1; j arr.length - i; j) {if (arr[minIndex] arr[j]) {// 记录最小值的下标minIndex j;}if (arr[maxIndex] arr[j]) {// 记录最大值的下标maxIndex j;}}
// 如果 minIndex 和 maxIndex 都相等那么他们必定都等于 i且后面的所有数字都与 arr[i] 相等此时已经排序完成if (minIndex maxIndex) break;// 将最小元素交换至首位int temp arr[i];arr[i] arr[minIndex];arr[minIndex] temp;
// 如果最大值的下标刚好是 i由于 arr[i] 和 arr[minIndex] 已经交换了所以这里要更新 maxIndex 的值。if (maxIndex i) maxIndex minIndex;// 将最大元素交换至末尾int lastIndex arr.length - 1 - i;temp arr[lastIndex];arr[lastIndex] arr[maxIndex];arr[maxIndex] temp;}
}我们使用 minIndex 记录最小值的下标maxIndex 记录最大值的下标。每次遍历后将最小值交换到首位最大值交换到末尾就完成了排序。
由于每一轮遍历可以排好两个数字所以最外层的遍历只需遍历一半即可。
二元选择排序中有一句很重要的代码它位于交换最小值和交换最大值的代码中间
if (maxIndex i) maxIndex minIndex;
这行代码的作用处理了一种特殊情况如果最大值的下标等于 i也就是说 arr[i] 就是最大值由于 arr[i] 是当前遍历轮次的首位它已经和 arr[minIndex] 交换了所以最大值的下标需要跟踪到 arr[i] 最新的下标 minIndex。
二元选择排序的效率 在二元选择排序算法中数组需要遍历的范围缩小了一倍。那么这样可以使选择排序的效率提升一倍吗
从代码可以看出虽然二元选择排序最外层的遍历范围缩小了但 for 循环内做的事情翻了一倍。也就是说二元选择排序无法将选择排序的效率提升一倍。但实测会发现二元选择排序的速度确实比选择排序的速度快一点点它的速度提升主要是因为两点
在选择排序的外层 for 循环中i 需要加到 arr.length - 1 二元选择排序中 i 只需要加到 arr.length / 2在选择排序的内层 for 循环中j 需要加到 arr.length 二元选择排序中 j 只需要加到 arr.length - i
二元选择排序虽然比选择排序要快但治标不治本二元选择排序中做的优化无法改变其时间复杂度二元选择排序的时间复杂度仍然是 O(n^2)只使用有限个变量空间复杂度 O(1)。
2.5 性能分析
时间复杂度
择排序的交换操作介于 0 和 (n - 1)次之间。选择排序的比较操作为 n (n - 1 / 2 次之间。选择排序的赋值操作介于 0 和 3 (n - 1 次之间。比较次数O(n^2
比较次数与关键字的初始状态无关总的比较次数N(n-1(n-2…1n*(n-1/2。交换次数O(n最好情况是已经有序交换0次最坏情况交换n-1次逆序交换n/2次由于选择排序在进行排序时无论数组是非有序都需要进行相同次数的寻找和比较所以最好和最差情况下的时间复杂度都是O(n^2)
空间复杂度
分配变量时不考虑临时变量分配完在一次for循环后就消失没有用到额外的空间所以空间复杂度为O(1)。
稳定性
选择排序是给每个位置选择当前元素最小的比如给第一个位置选择最小的在剩余元素里面给第二个元素选择第二小的依次类推直到第n-1个元素第n个元素不用选择了因为只剩下它一个最大的元素了。那么在一趟选择如果一个元素比当前元素小而该小的元素又出现在一个和当前元素相等的元素后面那么交换后稳定性就被破坏了。举个例子序列{5,8,5,2,9}我们知道第一遍选择第1个元素5会和2交换那么原序列中两个5的相对前后顺序就被破坏了所以选择排序是一个不稳定的排序算法。
2.6 拓展
现在让我们思考一下冒泡排序和选择排序有什么异同
相同点 都是两层循环时间复杂度都为 O(n^2)都只使用有限个变量空间复杂度 O(1)。 不同点 冒泡排序在比较过程中就不断交换而选择排序增加了一个变量保存最小值 / 最大值的下标遍历完成后才交换减少了交换次数。 事实上还有一个非常重要的不同点那就是 冒泡排序法是稳定的选择排序法是不稳定的。
那么排序算法的稳定性有什么意义呢
其实它只在一种情况下有意义当要排序的内容是一个对象的多个属性且其原本的顺序存在意义时如果我们需要在二次排序后保持原有排序的意义就需要使用到稳定性的算法。排序算法的稳定性与效率、可靠性都无关。
举个例子如果我们要对一组商品排序商品存在两个属性价格和销量。当我们按照价格从高到低排序后要再按照销量对其排序这时如果要保证销量相同的商品仍保持价格从高到低的顺序就必须使用稳定性算法。
当然算法的稳定性与具体的实现有关。在修改比较的条件后稳定性排序算法可能会变成不稳定的。如冒泡算法中如果将「左边的数大于右边的数则交换」这个条件修改为「左边的数大于或等于右边的数则交换」冒泡算法就变得不稳定了。同样地不稳定排序算法也可以经过修改达到稳定的效果。
思考一下选择排序算法如何实现稳定排序呢
实现的方式有很多种这里给出一种最简单的思路新开一个数组将每轮找出的最小值依次添加到新数组中选择排序算法就变成稳定的了。
但如果将寻找最小值的比较条件由arr[minIndex] arr[j]修改为arr[minIndex] arr[j]即使新开一个数组选择排序算法依旧是不稳定的。所以分析算法的稳定性时需要结合具体的实现逻辑才能得出结论我们通常所说的算法稳定性是基于一般实现而言的。
3. 插入排序Insertion Sort
插入排序的思想非常简单生活中有一个很常见的场景在打扑克牌时我们一边抓牌一边给扑克牌排序每次摸一张牌就将它插入手上已有的牌中合适的位置逐渐完成整个排序。
3.1 算法描述
插入排序有两种写法 交换法在新数字插入过程中不断与前面的数字交换直到找到自己合适的位置。 移动法在新数字插入过程中与前面的数字不断比较前面的数字不断向后挪出位置当新数字找到自己的位置后插入一次即可。 具体算法描述如下 从第一个元素开始该元素可以认为已经被排序 取出下一个元素在已经排序的元素序列中从后向前扫描 如果该元素已排序大于新元素将该元素移到下一位置 重复步骤3直到找到已排序的元素小于或者等于新元素的位置 将新元素插入到该位置后 重复步骤2~5。
3.2 图解演示 3.3 代码演示
public static void insertSort(int[] arr) {// 从第二个数开始往前插入数字for (int i 1; i arr.length; i) {// j 记录当前数字下标int j i;// 当前数字比前一个数字小则将当前数字与前一个数字交换while (j 1 arr[j] arr[j - 1]) {swap(arr, j, j - 1);// 更新当前数字下标j--;}}
}
private static void swap(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;
}
3.4 优化过程
移动法插入排序
我们发现在交换法插入排序中每次交换数字时swap 函数都会进行三次赋值操作。但实际 上新插入的这个数字并不一定适合与它交换的数字所在的位置。也就是说它刚换到新的位置上不久下一次比较后如果又需要交换它马上又会被换到前一个数字的位置。
我们可以想到一种优化方案让新插入的数字先进行比较前面比它大的数字不断向后移动直到找到适合这个新数字的位置后新数字只做一次插入操作即可。整个过程就像是已经有一些数字坐成了一排这时一个新的数字要加入所以这一排数字不断地向后腾出位置当新的数字找到自己合适的位置后就可以直接坐下了。重复此过程直到排序结束。
动图演示 这种方案我们需要把新插入的数字暂存起来代码如下
public static void insertSort(int[] arr) {// 从第二个数开始往前插入数字for (int i 1; i arr.length; i) {int currentNumber arr[i];int j i - 1;// 寻找插入位置的过程中不断地将比 currentNumber 大的数字向后挪while (j 0 currentNumber arr[j]) {arr[j 1] arr[j];j--;}// 两种情况会跳出循环1. 遇到一个小于或等于 currentNumber 的数字跳出循环currentNumber 就坐到它后面。// 2. 已经走到数列头部仍然没有遇到小于或等于 currentNumber 的数字也会跳出循环此时 j 等于 -1currentNumber 就坐到数列头部。arr[j 1] currentNumber;}
}3.5 性能分析
时间复杂度
在插入排序中当待排序数组是有序时是最优的情况只需当前数跟前一个数比较一下就可以了这时一共需要比较N- 1次时间复杂度为O(n)。
最坏的情况是待排序数组是逆序的此时需要比较次数最多总次数记为123…N-1所以插入排序最坏情况下的时间复杂度为O(n^2)。
平均来说A[1…j-1]中的一半元素小于A[j]一半元素大于A[j]插入排序在平均情况运行时间与最坏情况运行时间一样是输入规模的二次函数时间复杂度为O(n^2) 。
空间复杂度
由于插入排序是就地排序的没有用到单独的空间插入排序的空间复杂度为常数阶O(1)。
稳定性
如果待排序的序列中存在两个或两个以上具有相同关键词的数据排序后这些数据的相对次序保持不变即它们的位置保持不变通俗地讲就是两个相同的数的相对顺序不会发生改变则该算法是稳定的如果排序后数据的相对次序发生了变化则该算法是不稳定的。关键词相同的数据元素将保持原有位置不变所以该算法是稳定的 。
3.6 应用分析
插入排序适用于已经有部分数据已经排好并且排好的部分越大越好。一般在输入规模大于1000的场合下不建议使用插入排序。比冒泡排序的效率高冒泡排序需要两两比较两两交换时间基本快一倍。比选择排序快一点因为如果前面的数组基本有序平均上比较一半就找到位置选择排序总要从头到尾找一遍。
4.快速排序Quick Sort
它的时间复杂度也是 O(nlogn)O(nlogn)但它在时间复杂度为 O(nlogn)O(nlogn) 级的几种排序算法中大多数情况下效率更高所以快速排序的应用非常广泛。再加上快速排序所采用的分治思想非常实用使得快速排序深受面试官的青睐所以掌握快速排序的思想尤为重要。
4.1算法描述
快速排序算法的基本思想是
从数组中取出一个数称之为基数pivot遍历数组将比基数大的数字放到它的右边比基数小的数字放到它的左边。遍历完成后数组被分成了左右两个区域将左右两个区域视为两个数组重复前两个步骤直到排序完成
4.2 图解演示 4.3 代码实现
①快速排序递归框架
根据我们分析出的思路先搭出快速排序的架子
public static void quickSort(int[] arr) {quickSort(arr, 0, arr.length - 1);
}
public static void quickSort(int[] arr, int start, int end) {// 将数组分区并获得中间值的下标int middle partition(arr, start, end);// 对左边区域快速排序quickSort(arr, start, middle - 1);// 对右边区域快速排序quickSort(arr, middle 1, end);
}
public static int partition(int[] arr, int start, int end) {// TODO: 将 arr 从 start 到 end 分区左边区域比基数小右边区域比基数大然后返回中间值的下标
} partition 意为“划分”我们期望 partition 函数做的事情是将 arr 从 start 到 end 这一区间的值分成两个区域左边区域的每个数都比基数小右边区域的每个数都比基数大然后返回中间值的下标。
只要有了这个函数我们就能写出快速排序的递归函数框架。首先调用 partition 函数得到中间值的下标 middle然后对左边区域执行快速排序也就是递归调用 quickSort(arr, start, middle - 1)再对右边区域执行快速排序也就是递归调用 quickSort(arr, middle 1, end)。
现在还有一个问题何时退出这个递归函数呢
②退出递归的边界条件
很容易想到当某个区域只剩下一个数字的时候自然不需要排序了此时退出递归函数。实际上还有一种情况就是某个区域只剩下 0 个数字时也需要退出递归函数。当 middle 等于 start 或者 end 时就会出现某个区域剩余数字为 0。
在递归之前先判断此区域剩余数字是否为 0 个或者 1 个当数字至少为 2 个时才执行这个区域的快速排序。因为我们知道 middle start middle end 必然成立所以判断剩余区域的数字为 0 个或者 1 个也就是指 start 或 end 与 middle 相等或相差 1。
我们来分析一下这四个判断条件 当 start middle 时相当于 quickSort(arr, start, middle - 1) 中的 start end 1 当 start middle - 1 时相当于 quickSort(arr, start, middle - 1) 中的 start end 当 middle end 时相当于 quickSort(arr, middle 1, end) 中的 start end 1 当 middle end -1 时相当于 quickSort(arr, middle 1, end) 中的 start end 由上文所说的 middle start middle end 可以推出除了start end || start end 1这两个条件之外其他的情况下 start 都小于 end。我们需要知道这里的 start end 实际上只有两种情况 start end: 表明区域内只有一个数字 start end 1: 表明区域内一个数字也没有 不会存在 start 比 end 大 2 或者大 3 之类的。
所以最终我们可以得出判断条件为
public static void quickSort(int[] arr, int start, int end) {// 如果区域内的数字少于 2 个退出递归if (start end) return;// 将数组分区并获得中间值的下标int middle partition(arr, start, end);// 对左边区域快速排序quickSort(arr, start, middle - 1);// 对右边区域快速排序quickSort(arr, middle 1, end);
}③基数的选择
基数的选择没有固定标准随意选择区间内任何一个数字做基数都可以。通常来讲有三种选择方式
选择第一个元素作为基数选择最后一个元素作为基数选择区间内一个随机元素作为基数
选择的基数不同算法的实现也不同。实际上第三种选择方式的平均时间复杂度是最优的。
为什么说随机选择剩余数组中的一个元素作为基数的方案平均复杂度是最优的呢要理清这个问题我们先来看一下什么情况下快速排序算法的时间复杂度最高一共有两种情况数组为正序、数组为逆序理想中的快速排序在第 k 轮遍历中可以排好 2^{k-1}个基数。当数组原本为正序或逆序时我们将第一个数作为基数的话每轮分区后都有一个区域是空的也就是说数组中剩下的数字都被分到了同一个区域这就导致了每一轮遍历只能排好一个基数。所以总的比较次数为 (n - 1) (n - 2) (n - 3) … 1 次由等差数列求和公式可以计算出总的比较次数为 n(n - 1)/2 次此时快速排序的时间复杂度达到了 O(n^2)级。
选择第一个元素作为基数
// 将 arr 从 start 到 end 分区左边区域比基数小右边区域比基数大然后返回中间值的下标
public static int partition(int[] arr, int start, int end) {// 取第一个数为基数int pivot arr[start];// 从第二个数开始分区int left start 1;// 右边界int right end;
}④分区算法实现
快速排序中最重要的便是分区算法也就是 partition 函数。partition 函数需要做的事情就是将 arr 从 start 到 end 分区左边区域比基数小右边区域比基数大然后返回中间值的下标。那么首先我们要做的事情就是选择一个基数基数我们一般称之为 pivot意为“轴”。整个数组就像围绕这个轴进行旋转小于轴的数字旋转到左边大于轴的数字旋转到右边。
⑤最简单的分区算法
分区的方式也有很多种最简单的思路是从 left 开始遇到比基数大的数就交换到数组最后并将 right 减一直到 left 和 right 相遇此时数组就被分成了左右两个区域。再将基数和中间的数交换返回中间值的下标即可。
public static void quickSort(int[] arr) {quickSort(arr, 0, arr.length - 1);
}
public static void quickSort(int[] arr, int start, int end) {// 如果区域内的数字少于 2 个退出递归if (start end) return;// 将数组分区并获得中间值的下标int middle partition(arr, start, end);// 对左边区域快速排序quickSort(arr, start, middle - 1);// 对右边区域快速排序quickSort(arr, middle 1, end);
}
// 将 arr 从 start 到 end 分区左边区域比基数小右边区域比基数大然后返回中间值的下标
public static int partition(int[] arr, int start, int end) {// 取第一个数为基数int pivot arr[start];// 从第二个数开始分区int left start 1;// 右边界int right end;// left、right 相遇时退出循环while (left right) {// 找到第一个大于基数的位置while (left right arr[left] pivot) left;// 交换这两个数使得左边分区都小于或等于基数右边分区大于或等于基数if (left ! right) {exchange(arr, left, right);right--;}}// 如果 left 和 right 相等单独比较 arr[right] 和 pivotif (left right arr[right] pivot) right--;// 将基数和中间数交换if (right ! start) exchange(arr, start, right);// 返回中间值的下标return right;
}
private static void exchange(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;
}
因为我们选择了数组的第一个元素作为基数并且分完区后会执行将基数和中间值交换的操作这就意味着交换后的中间值会被分到左边区域。所以我们需要保证中间值的下标是分区完成后最后一个比基数小的值这里我们用 right 来记录这个值。
这段代码有一个细节。首先在交换 left 和 right 之前我们判断了 left ! right这是因为如果剩余的数组都比基数小则 left 会加到 right 才停止这时不应该发生交换。因为 right 已经指向了最后一个比基数小的值。
但这里的拦截可能会拦截到一种错误情况如果剩余的数组只有最后一个数比基数大left 仍然加到 right 停止了但我们并没有发生交换。所以我们在退出循环后单独比较了 arr[right] 和 pivot。
实际上这行单独比较的代码非常巧妙一共处理了三种情况
一是刚才提到的剩余数组中只有最后一个数比基数大的情况二是 left 和 right 区间内只有一个值则初始状态下 left right所以 while (left right) 根本不会进入所以此时我们单独比较这个值和基数的大小关系三是剩余数组中每个数都比基数大此时 right 会持续减小直到和 left 相等退出循环此时 left 所在位置的值还没有和 pivot 进行比较所以我们单独比较 left 所在位置的值和基数的大小关系
⑥双指针分区算法
除了上述的分区算法外还有一种双指针的分区算法更为常用从 left 开始遇到比基数大的数记录其下标再从 right 往前遍历找到第一个比基数小的数记录其下标然后交换这两个数。继续遍历直到 left 和 right 相遇。然后就和刚才的算法一样了交换基数和中间值并返回中间值的下标。
public static void quickSort(int[] arr) {quickSort(arr, 0, arr.length - 1);
}
public static void quickSort(int[] arr, int start, int end) {// 如果区域内的数字少于 2 个退出递归if (start end) return;// 将数组分区并获得中间值的下标int middle partition(arr, start, end);// 对左边区域快速排序quickSort(arr, start, middle - 1);// 对右边区域快速排序quickSort(arr, middle 1, end);
}
// 将 arr 从 start 到 end 分区左边区域比基数小右边区域比基数大然后返回中间值的下标
public static int partition(int[] arr, int start, int end) {// 取第一个数为基数int pivot arr[start];// 从第二个数开始分区int left start 1;// 右边界int right end;while (left right) {// 找到第一个大于基数的位置while (left right arr[left] pivot) left;// 找到第一个小于基数的位置while (left right arr[right] pivot) right--;// 交换这两个数使得左边分区都小于或等于基数右边分区大于或等于基数if (left right) {exchange(arr, left, right);left;right--;}}// 如果 left 和 right 相等单独比较 arr[right] 和 pivotif (left right arr[right] pivot) right--;// 将基数和轴交换exchange(arr, start, right);return right;
}
private static void exchange(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;
}同样地我们需要在退出循环后单独比较 left 和 right 的值。
4.4 性能分析
时间复杂度
快速排序的每一次遍历都将基数摆到了最终位置上。第一轮遍历排好 1 个基数第二轮遍历排好 2 个基数每个区域一个基数但如果某个区域为空则此轮只能排好一个基数第三轮遍历排好 4 个基数同理最差的情况下只能排好一个基数以此类推。总遍历次数为 lognn 次每轮遍历的时间复杂度为 O(n)所以很容易分析出快速排序的时间复杂度为 O(nlogn) O(n^2)平均时间复杂度为 O(nlogn)最坏的时间复杂度为 O(n^2)
空间复杂度
空间复杂度与递归的层数有关每层递归会生成一些临时变量所以空间复杂度为 O(logn) ~ O(n)平均空间复杂度为 O(logn)。
稳定性
从代码实现中可以分析出快速排序是一种不稳定的排序算法在分区过程中相同数字的相对顺序可能会被修改。
4.5快速排序的优化思路
如何解决这样的问题呢其实思路也很简单只要我们每轮选择的基数不是剩余数组中最大或最小的值就可以了。具体方案有很多种其中较常用的有三种 第一种就是我们在前文中提到的每轮选择基数时从剩余的数组中随机选择一个数字作为基数。这样每轮都选到最大或最小值的概率就会变得很低了。所以我们才说用这种方式选择基数其平均时间复杂度是最优的 第二种解决方案是在排序之前先用洗牌算法将数组的原有顺序打乱以防止原数组正序或逆序。 第三种就是既然数组重复排序的情况如此常见那么我们可以在快速排序之前先对数组做个判断如果已经有序则直接返回如果是逆序则直接倒序即可。在 Java 内部封装的 Arrays.sort() 的源码中就采用了此解决方案。
5.希尔排序Shell Sort
希尔排序和冒泡、选择、插入等排序算法一样逐渐被快速排序所淘汰但作为承上启下的算法不可否认的是希尔排序身上始终闪耀着算法之美。希尔排序本质上是对插入排序的一种优化它利用了插入排序的简单又克服了插入排序每次只交换相邻两个元素的缺点。
5.1 算法描述
它的基本思想是
将待排序数组按照一定的间隔分为多个子数组每组分别进行插入排序。这里按照间隔分组指的不是取连续的一段数组而是每跳跃一定间隔取一个值组成一组逐渐缩小间隔进行下一轮排序最后一轮时取间隔为 11也就相当于直接使用插入排序。但这时经过前面的「宏观调控」数组已经基本有序了所以此时的插入排序只需进行少量交换便可完成
每一遍排序的间隔在希尔排序中被称之为增量所有的增量组成的序列称之为增量序列也就是本例中的。增量依次递减最后一个增量必须为 1所以希尔排序又被称之为「缩小增量排序」。要是以专业术语来描述希尔排序可以分为以下两个步骤
定义增量序列 D_m D_{m-1} D_{m-2} … D_1 1对每个D_k进行「D_k间隔排序」
有一条非常重要的性质保证了希尔排序的效率
「D_{k1}间隔」有序的序列在经过「D_k间隔排序」排序后仍然是有序的增量序列的选择会极大地影响希尔排序的效率。
5.2 图解演示 5.3 代码实现
代码实现如下
public static void shellSort(int[] arr) {// 间隔序列在希尔排序中我们称之为增量序列for (int gap arr.length / 2; gap 0; gap / 2) {// 分组for (int groupStartIndex 0; groupStartIndex gap; groupStartIndex) {// 插入排序for (int currentIndex groupStartIndex gap; currentIndex arr.length; currentIndex gap) {// currentNumber 站起来开始找位置int currentNumber arr[currentIndex];int preIndex currentIndex - gap;while (preIndex groupStartIndex currentNumber arr[preIndex]) {// 向后挪位置arr[preIndex gap] arr[preIndex];preIndex - gap;}// currentNumber 找到了自己的位置坐下arr[preIndex gap] currentNumber;}}}
} 这份代码与我们上文中提到的思路是一模一样的先分组再对每组进行插入排序。同样地这里的插入排序也可以采用交换元素的方式。
5.4 优化过程
实际上这段代码可以优化一下。我们现在的处理方式是处理完一组间隔序列后再回来处理下一组间隔序列这非常符合人类思维。但对于计算机来说它更喜欢从第 gap 个元素开始按照顺序将每个元素依次向前插入自己所在的组这种方式。虽然这个过程看起来是在不同的间隔序列中不断跳跃但站在计算机的角度它是在访问一段连续数组。
代码实现如下
public static void shellSort(int[] arr) {// 间隔序列在希尔排序中我们称之为增量序列for (int gap arr.length / 2; gap 0; gap / 2) {// 从 gap 开始按照顺序将每个元素依次向前插入自己所在的组for (int i gap; i arr.length; i) {// currentNumber 站起来开始找位置int currentNumber arr[i];// 该组前一个数字的索引int preIndex i - gap;while (preIndex 0 currentNumber arr[preIndex]) {// 向后挪位置arr[preIndex gap] arr[preIndex];preIndex - gap;}// currentNumber 找到了自己的位置坐下arr[preIndex gap] currentNumber;}}
}5.5增量序列
增量序列的选择会极大地影响希尔排序的效率。增量序列如果选得不好希尔排序的效率可能比插入排序效率还要低举个例子
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VhSU36io-1620379072803)(C:\Users\86178\AppData\Roaming\Typora\typora-user-images\image-20210504124048637.png)]
在这个例子中我们发现原数组 8 间隔、4 间隔、2 间隔都已经有序了使用希尔排序时真正起作用的只有最后一轮 1 间隔排序也就是直接插入排序。希尔排序反而比直接使用插入排序多执行了许多无用的逻辑。于是人们发现增量元素不互质则小增量可能根本不起作用。
事实上希尔排序的增量序列如何选择是一个数学界的难题但它也是希尔排序算法的核心优化点。Knuth 增量序列D_1 1; D_{k1} 3 * D_k 1也就是1,4,13,40,…数学界猜想它的平均时间复杂度为 O(n^{3/2})
以 Knuth 增量序列为例使用 Knuth 序列进行希尔排序的代码如下
public static void shellSortByKnuth(int[] arr) {// 找到当前数组需要用到的 Knuth 序列中的最大值int maxKnuthNumber 1;while (maxKnuthNumber arr.length / 3) {maxKnuthNumber maxKnuthNumber * 3 1;}// 增量按照 Knuth 序列规则依次递减for (int gap maxKnuthNumber; gap 0; gap (gap - 1) / 3) {// 从 gap 开始按照顺序将每个元素依次向前插入自己所在的组for (int i gap; i arr.length; i) {// currentNumber 站起来开始找位置int currentNumber arr[i];// 该组前一个数字的索引int preIndex i - gap;while (preIndex 0 currentNumber arr[preIndex]) {// 向后挪位置arr[preIndex gap] arr[preIndex];preIndex - gap;}// currentNumber 找到了自己的位置坐下arr[preIndex gap] currentNumber;}}
}5.6 性能分析
时间复杂度
增量序列的选择Shell排序的执行时间依赖于增量序列。
好的增量序列的共同特征 最后一个增量必须为1 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。 有人通过大量的实验给出了较好的结果当n较大时比较和移动的次数约在n1.25到(1.6n)1.25之间。 事实上希尔排序时间复杂度非常难以分析它的平均复杂度界于 O(n) 到 O(n^2) 之间普遍认为它最好的时间复杂度为 O(n^{1.3})
空间复杂度
希尔排序的空间复杂度为 O(1)只需要常数级的临时变量。
稳定性
虽然插入排序是稳定的排序算法但希尔排序是不稳定的。在增量较大时排序过程可能会破坏原有数组中相同关键字的相对次序。
5.7 希尔排序与 O(n^2)级排序算法的本质区别 希尔排序凭什么可以打破时间复杂度 O(n^2)的魔咒呢它和之前介绍的 O(n^2)级排序算法的本质区别是什么 只要理解了这一点我们就能知道为什么希尔排序能够承上启下启发出之后的一系列 O(n^2)级以下的排序算法这个问题我们可以用逆序对来理解。 当我们从小到大排序时在数组中的两个数字如果前面一个数字大于后面的数字则这两个数字组成一个逆序对。 排序算法本质上就是一个消除逆序对的过程。
对于随机数组逆序对的数量是 O(n^2)级的如果采用「交换相邻元素」的办法来消除逆序对每次最多只能消除一组逆序对因此必须执行 O(n^2)级的交换次数这就是为什么冒泡、插入、选择算法只能到 O(n^2)级的原因。反过来说基于交换元素的排序算法要想突破 O(n^2)级必须通过一些比较交换间隔比较远的元素使得一次交换能消除一个以上的逆序对。
希尔排序算法就是通过这种方式打破了在空间复杂度为 O(1)的情况下时间复杂度为 O(n^2)的魔咒此后的快排、堆排等等算法也都是基于这样的思路实现的。
6.归并排序Merge Sort
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为2-路归并。
6.1算法描述
把长度为n的输入序列分成两个长度为n/2的子序列对这两个子序列分别采用归并排序将两个排序好的子序列合并成一个最终的排序序列。
6.2 算法图解 6.3 代码实现
6.3.1如何将两个有序的列表合并成一个有序的列表
在第二个列表向第一个列表逐个插入的过程中由于第二个列表已经有序所以后续插入的元素一定不会在前面插入的元素之前。在逐个插入的过程中每次插入时只需要从上次插入的位置开始继续向后寻找插入位置即可。这样一来我们最多只需要将两个有序数组遍历一次就可以完成合并。在向数组中不断插入新数字时原数组需要不断腾出位置这是一个比较复杂的过程而且这个过程必然导致增加一轮遍历。有一个替代方案只要开辟一个长度等同于两个数组长度之和的新数组并使用两个指针来遍历原有的两个数组不断将较小的数字添加到新数组中并移动对应的指针即可。
代码实现如下
// 将两个有序数组合并为一个有序数组
private static int[] merge(int[] arr1, int[] arr2) {int[] result new int[arr1.length arr2.length];int index1 0, index2 0;while (index1 arr1.length index2 arr2.length) {if (arr1[index1] arr2[index2]) {result[index1 index2] arr1[index1];//index1;} else {result[index1 index2] arr2[index2];//index2;}}// 将剩余数字补到结果数组之后while (index1 arr1.length) {result[index1 index2] arr1[index1];//index1;}while (index2 arr2.length) {result[index1 index2] arr2[index2];//index2;}return result;
}6.3.2将数组拆分成有序数组
拆分过程使用了二分的思想这是一个递归的过程归并排序使用的递归框架如下
6.3.3归并排序的优化减少临时空间的开辟
为了减少在递归过程中不断开辟空间的问题我们可以在归并排序之前先开辟出一个临时空间在递归过程中统一使用此空间进行归并即可。
public static void mergeSort(int[] arr) {if (arr.length 0) return;int[] result new int[arr.length];mergeSort(arr, 0, arr.length - 1, result);
}// 对 arr 的 [start, end] 区间归并排序
private static void mergeSort(int[] arr, int start, int end, int[] result) {// 只剩下一个数字停止拆分if (start end) return;int middle (start end) / 2;// 拆分左边区域并将归并排序的结果保存到 result 的 [start, middle] 区间mergeSort(arr, start, middle, result);// 拆分右边区域并将归并排序的结果保存到 result 的 [middle 1, end] 区间mergeSort(arr, middle 1, end, result);// 合并左右区域到 result 的 [start, end] 区间merge(arr, start, end, result);
}// 将 result 的 [start, middle] 和 [middle 1, end] 区间合并
private static void merge(int[] arr, int start, int end, int[] result) {int end1 (start end) / 2;int start2 end1 1;// 用来遍历数组的指针int index1 start;int index2 start2;while (index1 end1 index2 end) {if (arr[index1] arr[index2]) {result[index1 index2 - start2] arr[index1];} else {result[index1 index2 - start2] arr[index2];}}// 将剩余数字补到结果数组之后while (index1 end1) {result[index1 index2 - start2] arr[index1];}while (index2 end) {result[index1 index2 - start2] arr[index2];}// 将 result 操作区间的数字拷贝到 arr 数组中以便下次比较while (start end) {arr[start] result[start];}
} 其中 mergeSort(int[] arr) 函数是对外暴露的公共方法内部调用了私有的mergeSort(int[] arr, int start, int end) 函数这个函数用于对 arr 的 [start, end] 区间进行归并排序。
可以看到我们在这个函数中将原有数组不断地二分直到只剩下最后一个数字。此时嵌套的递归开始返回一层层地调用merge(int[] arr1, int[] arr2)函数也就是我们刚才写的将两个有序数组合并为一个有序数组的函数。
这就是最经典的归并排序只需要一个二分拆数组的递归函数和一个合并两个有序列表的函数即可。
我们统一使用 result 数组作为递归过程中的临时数组所以merge 函数接收的参数不再是两个数组而是 result 数组中需要合并的两个数组的首尾下标。根据首尾下标可以分别计算出两个有序数组的首尾下标 start1、end1、start2、end2之后的过程就和之前合并两个有序数组的代码类似了。
6.3.4原地归并排序
现在的归并排序看起来仍美中不足那就是仍然需要开辟额外的空间能不能实现不开辟额外空间的归并排序呢好像是可以做到的。在一些文章中将这样的归并排序称之为 In-Place Merge Sort直译为原地归并排序。
public static void mergeSort(int[] arr) {if (arr.length 0) return;mergeSort(arr, 0, arr.length - 1);
}// 对 arr 的 [start, end] 区间归并排序
private static void mergeSort(int[] arr, int start, int end) {// 只剩下一个数字停止拆分if (start end) return;int middle (start end) / 2;// 拆分左边区域mergeSort(arr, start, middle);// 拆分右边区域mergeSort(arr, middle 1, end);// 合并左右区域merge(arr, start, end);
}// 将 arr 的 [start, middle] 和 [middle 1, end] 区间合并
private static void merge(int[] arr, int start, int end) {int end1 (start end) / 2;int start2 end1 1;// 用来遍历数组的指针int index1 start;int index2 start2;while (index1 end1 index2 end) {if (arr[index1] arr[index2]) {index1;} else {// 右边区域的这个数字比左边区域的数字小于是它站了起来int value arr[index2];int index index2;// 前面的数字不断地后移while (index index1) {arr[index] arr[index - 1];index--;}// 这个数字坐到 index1 所在的位置上arr[index] value;// 更新所有下标使其前进一格index1;index2;end1;}}
}
/*
这段代码在合并 arr 的 [start, middle] 区间和 [middle 1, end] 区间时将两个区间较小的数字移动到 index1 的位置并且将左边区域不断后移目的是给新插入的数字腾出位置。最后更新两个区间的下标继续合并更新后的区间。
*/ 分析代码可以看出这样实现的归并本质上是插入排序前文已经说到在插入排序中腾出位置是一个比较复杂的过程而且这个过程必然导致增加一轮遍历。在这两份代码中每一次合并数组时都使用了两层循环目的就是不断腾挪位置以插入新数字可以看出这里合并的效率是非常低的。这两种排序算法的时间复杂度都达到了 O(n^2)级不能称之为归并排序。它们只是借用了归并排序的递归框架而已。
也就是说所谓的原地归并排序事实上并不存在许多算法书籍中都没有收录这种算法。它打着归并排序的幌子卖的是插入排序的思想实际排序效率比归并排序低得多。
6.4 性能分析
时间复杂度
归并排序的复杂度比较容易分析拆分数组的过程中会将数组拆分 logn 次每层执行的比较次数都约等于 n 次所以时间复杂度是 O(nlogn)。
空间复杂度
空间复杂度是 O(n)主要占用空间的就是我们在排序前创建的长度为n的result数组。
稳定性
分析归并的过程可知归并排序是一种稳定的排序算法。其中对算法稳定性非常重要的一行代码是
if (arr[index1] arr[index2]) { result[index1 index2 - start2] arr[index1]; } 在这里我们通过arr[index1] arr[index2]来合并两个有序数组保证了原数组中相同的元素相对顺序不会变化如果这里的比较条件写成了arr[index1] arr[index2]则归并排序将变得不稳定。
6.5 应用分析
总结起来归并排序分成两步一是拆分数组二是合并数组它是分治思想的典型应用。分治的意思是“分而治之”分的时候体现了二分的思想治是一个滚雪球的过程将 1 个数字组成的有序数组合并成一个包含 2 个数字的有序数组再将 2 个数字组成的有序数组合并成包含 4 个数字的有序数组…
由于性能较好且排序稳定归并排序应用非常广泛Arrays.sort() 源码中的 TimSort就是归并排序的优化版。
7.堆排序Heap Sort
数组、链表都是一维的数据结构相对来说比较容易理解而堆是二维的数据结构对抽象思维的要求更高所以许多程序员「谈堆色变」。但堆又是数据结构进阶必经的一步我们不妨静下心来将其梳理清楚。 堆符合以下两个条件之一的完全二叉树 根节点的值 ≥ 子节点的值这样的堆被称之为最大堆或大顶堆 根节点的值 ≤ 子节点的值这样的堆被称之为最小堆或小顶堆。 7.1算法描述
堆排序过程如下
用数列构建出一个大顶堆取出堆顶的数字调整剩余的数字构建出新的大顶堆再次取出堆顶的数字循环往复完成整个排序。
整体的思路就是这么简单我们需要解决的问题有两个 如何用数列构建出一个大顶堆 取出堆顶的数字后如何将剩余的数字调整成新的大顶堆。 构建大顶堆 调整堆 构建大顶堆有两种方式 方案一从 0 开始将每个数字依次插入堆中一边插入一边调整堆的结构使其满足大顶堆的要求 方案二将整个数列的初始状态视作一棵完全二叉树自底向上调整树的结构使其满足大顶堆的要求。 方案二更为常用动图演示如下 7.2图解演示 在介绍堆排序具体实现之前我们先要了解完全二叉树的几个性质。将根节点的下标视为 0则完全二叉树有如下性质
对于完全二叉树中的第 i 个数它的左子节点下标left 2i 1对于完全二叉树中的第 i 个数它的右子节点下标right left 1对于有 n 个元素的完全二叉树(n≥2)它的最后一个非叶子结点的下标n/2 - 1
7.3 代码实现
堆排序代码如下
public static void heapSort(int[] arr) {// 构建初始大顶堆buildMaxHeap(arr);for (int i arr.length - 1; i 0; i--) {// 将最大值交换到数组最后swap(arr, 0, i);// 调整剩余数组使其满足大顶堆maxHeapify(arr, 0, i);}
}
// 构建初始大顶堆
private static void buildMaxHeap(int[] arr) {// 从最后一个非叶子结点开始调整大顶堆最后一个非叶子结点的下标就是 arr.length / 2-1for (int i arr.length / 2 - 1; i 0; i--) {maxHeapify(arr, i, arr.length);}
}
// 调整大顶堆第三个参数表示剩余未排序的数字的数量也就是剩余堆的大小
private static void maxHeapify(int[] arr, int i, int heapSize) {// 左子结点下标int l 2 * i 1;// 右子结点下标int r l 1;// 记录根结点、左子树结点、右子树结点三者中的最大值下标int largest i;// 与左子树结点比较if (l heapSize arr[l] arr[largest]) {largest l;}// 与右子树结点比较if (r heapSize arr[r] arr[largest]) {largest r;}if (largest ! i) {// 将最大值交换为根结点swap(arr, i, largest);// 再次调整交换数字后的大顶堆maxHeapify(arr, largest, heapSize);}
}
private static void swap(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;
} 堆排序的第一步就是构建大顶堆对应代码中的 buildMaxHeap 函数。我们将数组视作一颗完全二叉树从它的最后一个非叶子结点开始调整此结点和其左右子树使这三个数字构成一个大顶堆。
调整过程由 maxHeapify 函数处理 maxHeapify 函数记录了最大值的下标根结点和其左右子树结点在经过比较之后将最大值交换到根结点位置。这样这三个数字就构成了一个大顶堆。
需要注意的是如果根结点和左右子树结点任何一个数字发生了交换则还需要保证调整后的子树仍然是大顶堆所以子树会执行一个递归的调整过程。
这里的递归比较难理解我们打个比方构建大顶堆的过程就是一堆数字比赛谁更大。比赛过程分为初赛、复赛、决赛每场比赛都是三人参加。但不是所有人都会参加初赛只有叶子结点和第一批非叶子结点会进行三人组初赛。初赛的冠军站到三人组的根结点位置然后继续参加后面的复赛。
而有的人生来就在上层比如李小胖它出生在数列的第一个位置上是二叉树的根结点当其他结点进行初赛、复赛时它就静静躺在根结点的位置等一场决赛。
当王大强和张壮壮经历了重重比拼来到了李小胖的左右子树结点位置。他们三个人开始决赛。王大强和张壮壮是靠实打实的实力打上来的他们已经确认过自己是小组最强。而李小胖之前一直躺在这里等决赛。如果李小胖赢了他们两个说明李小胖是所有小组里最强的毋庸置疑他可以继续坐在冠军宝座。
但李小胖如果输给了其中任何一个人比如输给了王大强。王大强会和张壮壮对决选出本次构建大顶堆的冠军。但李小胖能够坐享其成获得第三名吗生活中或许会有这样的黑幕但程序不会欺骗我们。李小胖跌落神坛之后就要从王大强的打拼路线回去继续向下比较找到自己真正实力所在的真实位置。这就是 maxHeapify 中会继续递归调用 maxHeapify 的原因。
当构建出大顶堆之后就要把冠军交换到数列最后深藏功与名。来到冠军宝座的新人又要和李小胖一样开始向下比较找到自己的真实位置使得剩下的 n - 1n−1 个数字构建成新的大顶堆。这就是 heapSort 方法的 for 循环中调用 maxHeapify 的原因。
变量 heapSize 用来记录还剩下多少个数字没有排序完成每当交换了一个堆顶的数字heapSize 就会减 11。在 maxHeapify 方法中使用 heapSize 来限制剩下的选手不要和已经躺在数组最后当过冠军的人比较免得被暴揍。
这就是堆排序的思想。学习时我们采用的是最简单的代码实现在熟练掌握了之后我们就可以加一些小技巧以获得更高的效率。比如我们知道计算机采用二进制来存储数据数字左移一位表示乘以 22右移一位表示除以 22。所以堆排序代码中的arr.length / 2 - 1 可以修改为 (arr.length 1) - 1左子结点下标2 * i 1可以修改为(i 1) 1。需要注意的是位运算符的优先级比加减运算的优先级低所以必须给位运算过程加上括号。
7.4 性能分析
时间复杂度
堆排序分为两个阶段初始化建堆buildMaxHeap和重建堆maxHeapify直译为大顶堆化。所以时间复杂度要从这两个方面分析。
根据数学运算可以推导出初始化建堆的时间复杂度为 O(n)重建堆的时间复杂度为 O(n\log n)O所以堆排序总的时间复杂度为 O(n\log n)。推导过程较为复杂故不再给出证明过程。
空间复杂度
堆排序的空间复杂度为 O(1)只需要常数级的临时变量。堆排序是一个优秀的排序算法但是在实际应用中快速排序的性能一般会优于堆排序。
稳定性
堆排序是不稳定的
比如9 18 27 18
如果堆顶9先输出则第三层的18最后一个18跑到堆顶然后堆稳定继续输出堆顶是刚才那个18这样说明后面的18先于第二个位置的18输出所以不稳定。
8.计数排序Counting Sort
计数排序是一个非基于比较的排序算法它的优势在于在对一定范围内的整数排序时它的复杂度为Ο(nk)其中k是整数的范围快于任何比较排序算法。当然这是一种牺牲空间换取时间的做法而且当O(k)O(nlog(n))的时候其效率反而不如基于比较的排序基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序堆排序
8.1算法描述
算法思想
找出待排序的数组中最大和最小的元素统计数组中每个值为i的元素出现的次数存入数组C的第i项对所有的计数累加从C中的第一个元素开始每一项和前一项相加反向填充目标数组将每个元素i放在新数组的第C(i)项每放一个元素就将C(i)减去1。
8.2 图解演示 8.3代码实现
代码实现如下
//针对c数组的大小优化过的计数排序
public class CountSort{publicstaticvoidmain(String[]args){//排序的数组int a[]{100,93,97,92,96,99,92,89,93,97,90,94,92,95};int b[]countSort(a);for(inti:b){System.out.print(i);}System.out.println();}public static int[] countSort(int[]a){int b[] new int[a.length];int max a[0],min a[0];for(int i:a){if(imax){maxi;}if(imin){mini;}}//这里k的大小是要排序的数组中元素大小的极值差1int kmax-min1;int c[]new int[k];for(int i0;ia.length;i){c[a[i]-min]1;//优化过的地方减小了数组c的大小}for(int i1;ic.length;i){c[i]c[i]c[i-1];}for(int ia.length-1;i0;--i){b[--c[a[i]-min]]a[i];//按存取的方式取出c的元素}return b;}
}8.4 性能分析
时间复杂度
原数组、count数组、累加数组、目标数组先对原数组过滤一遍生成count数组对count数组过滤一遍生成累加数组最后再把原数组从后往前生成目标数组原数组过滤两遍count数组过滤两遍原数组是长度是ncount数组长度是k即2(nk)
从计数排序的实现代码中可以看到每次遍历都是进行 n 次或者 k 次所以计数排序的时间复杂度为 O(n k)k 表示数据的范围大小。用到的空间主要是长度为 k 的计数数组和长度为 n 的结果数组所以空间复杂度也是 O(n k)。
空间复杂度
用了额外的数组长度为n和k所以空间复杂度为O(nk)。
稳定性
经计数排序输出序列中值相同的元素之间的相对次序与他们在输入序列中的相对次序相同换句话说计数排序算法是一个稳定的排序算法。
8.5 拓展
需要注意的是一般我们分析时间复杂度和空间复杂度时常数项都是忽略不计的。但计数排序的常数项可能非常大以至于我们无法忽略。不知你是否注意到计数排序的一个非常大的隐患比如我们想要对这个数组排序
int[] arr new int[]{1, Integer.MAX_VALUE};尽管它只包含两个元素但数据范围是 [1, 2^{31}]我们知道java中int 占4个字节一个长度为 2^{31}次方的 int 数组大约会占8G的空间。如果使用计数排序仅仅排序这两个元素声明计数数组就会占用超大的内存甚至导致 OutOfMemory 异常。
使用于特定问题对源数据有要求适合量比较大数值范围比较小例如企业员工年龄排序快速查询高考名次如果需要排序的数字中存在一位小数可以将所有数字乘以 10再去计算最终的下标位置。当k不是很大并且序列比较集中时计数排序是一个很有效的排序算法。
9.基数排序Radix Sort
基数排序有两种实现方式。本例属于「最高位优先法」简称 MSD (Most significant digital)思路是从最高位开始依次对基数进行排序。与之对应的是「最低位优先法」简称 LSD (Least significant digital)。思路是从最低位开始依次对基数进行排序。使用 LSD 必须保证对基数进行排序的过程是稳定的。
通常来讲LSD 比 MSD 更常用。因为使用的是 MSD例如在第二步比较两个以 99 开头的数字时其他基数开头的数字不得不放到一边。体现在计算机中这里会产生很多临时变量。
但在采用 LSD 进行基数排序时每一轮遍历都可以将所有数字一视同仁统一处理。所以 LSD 的基数排序更符合计算机的操作习惯。
9.1 算法描述
基数排序可以分为以下三个步骤
找出数组中最大的数字的位数 maxDigitLength获取数组中每个数字的基数遍历 maxDigitLength 轮数组每轮按照基数对其进行排序
9.2 图解演示 9.3 代码实现
9.3.1找出数组中最大的数字的位数
首先找到数组中的最大值
public static void radixSort(int[] arr) {if (arr null) return;int max 0;for (int value : arr) {if (value max) {max value;}}// ...
}通过遍历一次数组找到了数组中的最大值 max然后我们计算这个最大值的位数
int maxDigitLength 0;
while (max ! 0) {maxDigitLength;max / 10;
}将 maxDigitLength 初始化为 00然后不断地除以 10每除一次maxDigitLength 就加一直到 max 为 00。
如果 max 初始值就是 00 呢严格来讲00 在数学上属于 11 位数。但实际上基数排序时我们无需考虑 max 为 00 的场景因为 max 为 00 只有一种可能那就是数组中所有的数字都为 00此时数组已经有序我们无需再进行后续的排序过程。
9.3.2获取基数
int dev 1;
for (int i 0; i maxDigitLength; i) {for (int value : arr) {int radix value / dev % 10;// 对基数进行排序}dev * 10;
}9.3.3对基数进行排序
因为每一个基数都在 [0, 9] 之间并且计数排序是一种稳定的算法。
LSD 方式的基数排序代码如下
public class RadixSort {public static void radixSort(int[] arr) {if (arr null) return;// 找出最大值int max 0;for (int value : arr) {if (value max) {max value;}}// 计算最大数字的长度int maxDigitLength 0;while (max ! 0) {maxDigitLength;max / 10;}// 使用计数排序算法对基数进行排序int[] counting new int[10];int[] result new int[arr.length];int dev 1;for (int i 0; i maxDigitLength; i) {for (int value : arr) {int radix value / dev % 10;counting[radix];}for (int j 1; j counting.length; j) {counting[j] counting[j - 1];}// 使用倒序遍历的方式完成计数排序for (int j arr.length - 1; j 0; j--) {int radix arr[j] / dev % 10;result[--counting[radix]] arr[j];}// 计数排序完成后将结果拷贝回 arr 数组System.arraycopy(result, 0, arr, 0, arr.length);// 将计数数组重置为 0Arrays.fill(counting, 0);dev * 10;}}
}
当每一轮对基数完成排序后我们将 result 数组的值拷贝回 arr 数组并且将 counting 数组中的元素都置为 00以便在下一轮中复用。
9.4 对包含负数的数组进行基数排序
如果数组中包含负数如何进行基数排序呢
我们很容易想到一种思路将数组中的每个元素都加上一个合适的正整数使其全部变成非负整数等到排序完成后再减去之前加的这个数就可以了。
但这种方案有一个缺点加法运算可能导致数字越界所以必须单独处理数字越界的情况。
事实上有一种更好的方案解决负数的基数排序。那就是在对基数进行计数排序时申请长度为19的计数数组用来存储 [-9, 9]这个区间内的所有整数。在把每一位基数计算出来后加上99就能对应上 counting 数组的下标了。也就是说counting数组的下标[0, 18]对应基数 [-9, 9]。
代码实现如下
public class RadixSort {public static void radixSort(int[] arr) {if (arr null) return;// 找出最长的数int max 0;for (int value : arr) {if (Math.abs(value) max) {max Math.abs(value);}}// 计算最长数字的长度int maxDigitLength 0;while (max ! 0) {maxDigitLength;max / 10;}// 使用计数排序算法对基数进行排序下标 [0, 18] 对应基数 [-9, 9]int[] counting new int[19];int[] result new int[arr.length];int dev 1;for (int i 0; i maxDigitLength; i) {for (int value : arr) {// 下标调整int radix value / dev % 10 9;counting[radix];}for (int j 1; j counting.length; j) {counting[j] counting[j - 1];}// 使用倒序遍历的方式完成计数排序for (int j arr.length - 1; j 0; j--) {// 下标调整int radix arr[j] / dev % 10 9;result[--counting[radix]] arr[j];}// 计数排序完成后将结果拷贝回 arr 数组System.arraycopy(result, 0, arr, 0, arr.length);// 将计数数组重置为 0Arrays.fill(counting, 0);dev * 10;}}
}代码中主要做了两处修改
当数组中存在负数时我们就不能简单的计算数组的最大值了而是要计算数组中绝对值最大的数也就是数组中最长的数在获取基数的步骤将计算出的基数加上9使其与 counting 数组下标一一对应
9.5 LSD VS MSD
前文介绍的基数排序都属于 LSD接下来我们看一下基数排序的 MSD 实现
public class RadixSort {public static void radixSort(int[] arr) {if (arr null) return;// 找到最大值int max 0;for (int value : arr) {if (Math.abs(value) max) {max Math.abs(value);}}// 计算最大长度int maxDigitLength 0;while (max ! 0) {maxDigitLength;max / 10;}radixSort(arr, 0, arr.length - 1, maxDigitLength);}// 对 arr 数组中的 [start, end] 区间进行基数排序private static void radixSort(int[] arr, int start, int end, int position) {if (start end || position 0) return;// 使用计数排序对基数进行排序int[] counting new int[19];int[] result new int[end - start 1];int dev (int) Math.pow(10, position - 1);for (int i start; i end; i) {// MSD, 从最高位开始int radix arr[i] / dev % 10 9;counting[radix];}for (int j 1; j counting.length; j) {counting[j] counting[j - 1];}// 拷贝 counting用于待会的递归int[] countingCopy new int[counting.length];System.arraycopy(counting, 0, countingCopy, 0, counting.length);for (int i end; i start; i--) {int radix arr[i] / dev % 10 9;result[--counting[radix]] arr[i];}// 计数排序完成后将结果拷贝回 arr 数组System.arraycopy(result, 0, arr, start, result.length);// 对 [start, end] 区间内的每一位基数进行递归排序for (int i 0; i counting.length; i) {radixSort(arr, i 0 ? start : start countingCopy[i - 1], start countingCopy[i] - 1, position - 1);}}}使用 MSD 时下一轮排序只应该发生在当前轮次基数相等的数字之间对每一位基数进行递归排序的过程中会产生许多临时变量。
相比 LSDMSD 的基数排序显得较为复杂。因为我们每次对基数进行排序后无法将所有的结果一视同仁地进行下一轮排序否则下一轮排序会破坏本次排序的结果。
9.6 性能分析
时间复杂度
无论 LSD 还是 MSD基数排序时都需要经历 maxDigitLength 轮遍历每轮遍历的时间复杂度为 O(n k) 其中 k 表示每个基数可能的取值范围大小。如果是对非负整数排序则 k 10如果是对包含负数的数组排序则 k 19。所以基数排序的时间复杂度为 O(d(n k)) (d 表示最长数字的位数k 表示每个基数可能的取值范围大小)。
每次都复制一遍一遍的时间复杂度为O(n)所以时间复杂度为O(n*k)。
空间复杂度
使用的空间和计数排序是一样的空间复杂度为 O(n k)k 表示每个基数可能的取值范围大小。
稳定性
在基数排序过程中每一次装桶都是将当前位数上相同数值的元素进行装桶并不需要交换位置所以基数排序是稳定的算法。
如果负数可以使用正负数桶负数的排负数正数的排正数然后就可以达到要求。
10.桶排序Bucket Sort
桶排序利用了函数的映射关系高效与否的关键就在于这个映射函数的确定桶排序 (Bucket sort)的工作的原理假设输入数据服从均匀分布将数据分到有限数量的桶里每个桶再分别排序有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排桶排序的思想近乎彻底的分治思想桶排序假设待排序的一组数均匀独立的分布在一个范围中并将这一范围划分成几个子范围桶。
10.1 算法描述
设置一个定量的数组当作空桶遍历输入数据并且把数据一个一个放到对应的桶里去对每个不是空的桶进行排序从不是空的桶里把排好序的数据拼接起来得到结果。
10.2 图解演示
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vBv608ur-1620379072809)(C:\Users\86178\AppData\Roaming\Typora\typora-user-images\image-20210506215159979.png)]
10.3 代码实现
代码实现
public static double[] bucketSort(double[] array){//得到数列的最大值和最小值并计算出差值ddouble maxarray[0];double minarray[0];for (int i1;iarray.length;i){if (array[i]max){maxarray[i];}if (array[i]min){minarray[i];}}double dmax-min;//初始化桶int bucketNumarray.length;ArrayListLinkedListDouble bucketListnew ArrayListLinkedListDouble(bucketNum);for (int i0;ibucketNum;i){bucketList.add(new LinkedListDouble());}//遍历原始数组将每个元素放入桶中for (int i0;iarray.length;i){int num(int)((array[i]-min)*(bucketNum-1)/d);bucketList.get(num).add(array[i]);}//对每个桶内部进行排序for(int i0;ibucketList.size();i){// 使用Collections.sort其底层实现基于归并排序或归并排序的优化版本Collections.sort(bucketList.get(i));}//输出全部元素double[] sortedArraynew double[array.length];int index0;for (LinkedListDouble list:bucketList) {for (double element:list){sortedArray[index]element;index;}}return sortedArray;}10.4 性能分析
时间复杂度这部分内容不太重要增加学习负担
桶排序利用函数的映射关系减少了几乎所有的比较工作。实际上桶排序的f(k)值的计算其作用就相当于快排中划分已经把大量数据分割成了基本有序的数据块(桶)。然后只需要对桶中的少量数据做先进的比较排序即可。
对N个关键字进行桶排序的时间复杂度分为两个部分 循环计算每个关键字的桶映射函数这个时间复杂度是O(n)。 利用先进的比较排序算法对每个桶内的所有数据进行排序其时间复杂度为 ∑ O(Ni*logNi) 。其中Ni 为第i个桶的数据量。 很显然第二部分是桶排序性能好坏的决定因素。尽量减少桶内数据的数量是提高效率的唯一办法(因为基于比较排序的最好平均时间复杂度只能达到O(n*logn)了)。因此我们需要尽量做到下面两点 映射函数f(k)能够将n个数据平均的分配到m个桶中这样每个桶就有[n/m]个数据量。 在额外空间充足的情况下尽量增大桶的数量使用的映射函数能够将输入的 n个数据均匀的分配到 m个桶中。极限情况下每个桶只能得到一个数据这样就完全避开了桶内数据的“比较”排序操作。 当然做到这一点很不容易数据量巨大的情况下f(k)函数会使得桶集合的数量巨大空间浪费严重。这就是一个时间代价和空间代价的权衡问题了。
对于n个待排数据m个桶平均每个桶[n/m]个数据的桶排序平均时间复杂度为 O(n)O(m(n/m)log(n/m))O(nn(logn-logm))O(nnlogn-nlogm)
当nm时即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到O(n)。最糟糕的情况下即所有的数据都放入了一个桶内桶内自排序算法为插入排序那么其时间复杂度就为 O(n^2) 了。
空间复杂度
当然桶排序的空间复杂度 为O(NM)如果输入数据非常庞大而桶的数量也非常多则空间代价无疑是昂贵的。
稳定性
桶排序是稳定的。
10.5 拓展
其次我们可以发现区间划分的越细即桶的数量越多理论上分到每个桶中的元素就越少桶内数据的排序就越简单其时间复杂度就越接近于线性。
极端情况下就是区间小到只有1即桶内只存放一种元素桶内的元素不再需要排序因为它们都是相同的元素这时桶排序差不多就和计数排序一样了。
总结 桶排序的平均时间复杂度为线性的O(nC)其中Cn*(logn-logm)。如果相对于同样的n桶数量m越大其效率越高最好的时间复杂度达到O(n)。 桶排序的空间复杂度 为O(nm)如果输入数据非常庞大而桶的数量也非常多则空间代价无疑是昂贵的。此外桶排序是稳定的。
11.非比较类排序算法总结
这三种排序算法都利用了桶的概念但对桶的使用方法上有明显差异
基数排序根据键值的每位数字来分配桶计数排序每个桶只存储单一键值桶排序每个桶存储一定范围的数值 部分动图参考https://www.cnblogs.com/onepixel/articles/7674659.html 部分优化参考https://leetcode-cn.com/leetbook/detail/sort-algorithms/
