制作游戏的网站,wordpress激活码,dede 获取网站标题,冠县哪做网站排序算法 复杂度原地排序冒泡排序算法逻辑时间复杂度#xff1a;最好O(n)#xff0c;最坏和平均O(n^2)冒泡排序:稳定性算法 选择排序算法逻辑时间复杂度#xff1a;最好#xff0c;最坏和平均都是O(n^2)选择排序:不稳定性算法 插入排序算法逻辑时间复杂度#xff1a;最好O… 排序算法 复杂度原地排序冒泡排序算法逻辑时间复杂度最好O(n)最坏和平均O(n^2)冒泡排序:稳定性算法 选择排序算法逻辑时间复杂度最好最坏和平均都是O(n^2)选择排序:不稳定性算法 插入排序算法逻辑时间复杂度最好O(n)最坏和平均O(n^2)插入排序:稳定性算法 希尔排序逻辑步骤时间复杂度希尔排序不稳定算法 快速排序步骤逻辑时间复杂度最好O(nlog2n)平均O(nlog2n)最坏O(n^2)快速排序不稳定算法 归并排序逻辑步骤时间复杂度最好 平均 最坏都是O(nlog2n)归并排序:稳定性算法 堆排序最大堆MaxHeap堆排序堆调整 使用堆Heap来实现优先级队列管理时间复杂度堆排序不稳定算法 复杂度
在介绍具体的排序分类之前先引入时间空间复杂度的概念这是各个排序算法的应用选择条件
算法的复杂度是一个函数一个语句的频度是指该语句在算法中重复执行的次数时间复杂度是循环执行次数值次数越多那执行越复杂需要运行时间或占用空间也就越多所以也用它定量描述算法运行时间或空间的大小理论上我们运行时间越短空间越小越好也就是循序执行次数越少也好
常见的时间复杂度并且按照从小到大排序
如果一个数据集的规模是n
O(1) O(logn) O(n) O(nlogn) O(n^2) O(n^3) O(2^n)O(1):表示与元素数量无关多了少了都一样为1这种时间复杂度是最低的
O(logn) :其实有个省略的底数可以是2可以是10具体情况看待如每次2分那就是2已2为底数的对数向上取整比如n为102^4 10 里O(logn)这代表值就是4
O(n):表示与元素数量大小正相关多少元素执行多少次
O(nlogn) 算法的运行时间会以n乘以logn的速度增长nlogn的意思是 n * lognO(nlogn) O(n) * O(logn) 归并排序就是这个复杂度
O(n^2)复杂度值与输入数据大小n的二次方成正比比如双重for循环(n-1)(n-2)…21 n*(n-1)/2
O(n^3)复杂度值与输入数据大小n的三次方成正比三层for循环0(1-1)*1/2...(n-1)n/2n(n1)(n-1)/6
O(2^n)复杂度随着输入数据规模 n 的增加呈指数增长原地排序
原地排序就是指在排序过程中不申请多余的存储空间只利用原来存储待排数据的存储空间进行比较和交换的数据排序
int[] array {5,4,3,2,1};
//临时存储元素4
int temp array[1];
//将索引位置2的元素 更新替换掉索引位置1的元素
array[1] array[2];//在将原索引位置1的元素更新替换掉索引位置2的元素
array[2] temp;这种方式 不申请多余的存储空间利用原数组的存储空间进行交互数据也是一种排序至于先介绍它是因为后面介绍的排序都用到它
冒泡排序
通过重复地遍历待排序的列表比较相邻的元素并交换它们的位置来实现排序。该算法的名称来源于较小的元素会像气泡一样逐渐浮到列表的顶端
算法逻辑
它通过不断交换相邻的元素将最大或最小的元素逐渐“冒泡”到数组的末尾 // 将数组元素大小按照从小到大排序public static void main(String[] args) {int[] array {5,4,3,2,1};int count1 0;int count2 0;int n array.length;for (int i 0; i n - 1; i) {count1 count11;System.out.println(外循环第(i1)次);for (int j 0; j n - i - 1; j) {if (array[j] array[j 1]) {count2 count21;// Swap array[j1] and array[j]int temp array[j];array[j] array[j 1];array[j 1] temp;System.out.println(内循环第(j1)次Arrays.toString(array));}}}System.out.println(外循环总次数:count1内循环总次数:count2,最终排序数组Arrays.toString(array));}打印输出
它通过不断交换相邻的元素将最大或最小的元素逐渐“冒泡”到数组的末尾
外层循环一次就能固定一个元素外循环第1次
内循环第1次[4, 5, 3, 2, 1]
内循环第2次[4, 3, 5, 2, 1]
内循环第3次[4, 3, 2, 5, 1]
内循环第4次[4, 3, 2, 1, 5] (n-1)
外循环第2次
内循环第1次[3, 4, 2, 1, 5]
内循环第2次[3, 2, 4, 1, 5]
内循环第3次[3, 2, 1, 4, 5] (n-2)
外循环第3次
内循环第1次[2, 3, 1, 4, 5]
内循环第2次[2, 1, 3, 4, 5] (n-3)
外循环第4次
内循环第1次[1, 2, 3, 4, 5] (n-4)
外循环总次数:4内循环总次数:10,最终排序数组[1, 2, 3, 4, 5]最坏情况下就是原数组元素大小顺序是和我们需求相反的
需要进行(n-1)(n-2)…21 n*(n-1)/2次比较和交换操作用时间复杂度表示 是O(n^2)最好的情况就是 int[] array {1,2,3,4,5}; 原数组顺序正好是我们需要的这种
外循环总次数:4内循环总次数:0,最终排序数组[1, 2, 3, 4, 5] 时间复杂度是(0/n)每外层循序一次通过相邻元素两两比较并交换最终确定一个最值的元素 放在末尾 第二次外循环 确定第二个最值元素放在倒数第二位 以此类推 到确定倒数第二个元素那剩下的一个元素就自然是首位了
索引01234外循环第1次****5外循环第2次***45外循环第3次**345外循环第4次12345
冒泡排序的时间复杂度在(0/n) 到 O(n^2) 之间但(0/n)是极端才有默认的时间复杂度为O(n^2) 平均时间复杂度O(n^2) 最坏时间复杂度O(n^2) 最好时间复杂度O(n)
时间复杂度最好O(n)最坏和平均O(n^2)
什么情况下时间复杂度为(0/n)呢数组元素顺序正好是我们排序需要的顺序比如我们需要正序数组正好是[1, 2, 3, 4, 5] 这样正序的而且还需要优化下排序算法上面算法复杂度是O(n^2) public static void bubbleSort(int arr[]) {// 添加一个是否进行了交互元素的标识boolean didSwap;for(int i 0, len arr.length; i len - 1; i) {//初始还没有交互元素 默认flasedidSwap false;for(int j 0; j len - i - 1; j) {//第一次内循环 n-1次,不断相邻位置比较if(arr[j 1] arr[j]) {//走到这里证明有需要相互交互的元素 执行了交换swap(arr, j, j 1);//交换过元素 变更标识 证明了数组调整了 原数组不是正好排序的didSwap true;}}// 如果标识为false,代表不需要交换元素原数组正好排序的那就直接退出if(didSwap false)return; }}// 原地排序private static void swap(int[] arr, int j, int i) {int temp arr[i];arr[i] arr[j];arr[j] temp;}如果int[] arr {1,2,3,4,5};这样正序的数组那么再i0,然后进行4次内循环之后就会因didSwap false触发return,循环结束时间复杂度O(n)这就是最好也是最极端的情况
冒泡排序:稳定性算法
稳定性是指在排序过程中保持相等元素的相对顺序不变。简单来说如果一个排序算法能够保证相等元素的顺序相对位置不发生改变那么它就是稳定的 比如[5,4,3,3,2] 排序的过程中无论怎么调整 相等的两个元素3相对位置顺序不变即第一个元素3始终在第二个元素3前面
冒泡排序冒泡排序是稳定的因为在比较相邻元素并交换时只有当前元素比相邻元素大才会交换, 相等元素的顺序不会发生交换的这种稳定性在处理具有多个相同键值的记录时十分有用
选择排序
算法逻辑
先找到最小元素所在位置的索引然后将该元素与第一位上的元素进行交换 int[] array {5,4,3,2,1};int count1 0;int count2 0;for (int i 0; i array.length-1; i) {int swapIndex i;//获取剩余未排序元素最小值的索引值for (int j i 1; j array.length; j) {if (array[j] array[swapIndex]) {// 如果在这一步 是两个比较元素符合条件直接替换 就是冒泡排序了swapIndex j;}}//获取到最小元素的索引值不是 不是当前元素的 直接替换if(swapIndex ! i){int swapValue array[i];array[i] array[swapIndex];array[swapIndex] swapValue;}System.out.println(外循环第(i1)次变更后Arrays.toString(array));}打印输出
外循环第1次变更后[1, 4, 3, 2, 5]第1次外循环:内循环4次得最小元素并根据索引替换第一个元素
外循环第2次变更后[1, 2, 3, 4, 5]第2次外循环:内循环3次得剩余最小的元素并根据索引替换第二个元素
外循环第3次变更后[1, 2, 3, 4, 5]第3次外循环:内循环2次得剩余最小的元素并根据索引替换第三个元素
外循环第4次变更后[1, 2, 3, 4, 5]第4次外循环:内循环1次得剩余最小的元素并根据索引替换第四个元素
外循环总次数:4 内循环总次数:10,最终排序数组[1, 2, 3, 4, 5]处理逻辑是
索引01234外循环第1次确定外循环第2次确定确定外循环第3次确定确定确定外循环第4次确定确定确定确定
选择排序按照空间顺序每次从未排序的序列中 通过遍历比较确定选择一个元素 替换到当前待确认的空间
和冒泡排序相似地方在于每次外循环一次都能确定一个最值 区别就在于 冒泡排序每次内循环符合条件的都有交换一次(可能需要多次交换元素)最多替换值次数是O(n^2) 选择排序内循环上只获取最值的索引值在外层循环里交换值(每次外循环交换一次)最多替换值次数是n-1
这样看其实选择排序是冒泡排序的优化后的排序,虽然两者时间复杂度看似一样但实际应用中选择使用选择排序的比较多因为选择排序的交换次数较少通常比冒泡排序更快
时间复杂度最好最坏和平均都是O(n^2)
时间复杂度上 平均时间复杂度O(n^2) 最坏时间复杂度O(n^2) 最好时间复杂度O(n^2)
正如这个逻辑图所示n为5
索引01234元素12345外循环第1次确定1外循环第2次确定1确定2外循环第3次确定1确定2确定3外循环第4次确定1确定2确定3确定4余下的5
第1次外循环内循环n-1
第2次外循环内循环n-2
第3次外循环内循环n-3
第4次外循环内循环n-4
需要进行(n-1)(n-2)…21 n*(n-1)/2次用时间复杂度表示 是O(n^2)
最好情况下 数组顺序正好是排序的就是上面展示 的数组元素样式但依然需要 n*(n-1)/2次选择排序:不稳定性算法
选择排序的工作原理是 第一次从待排序的数据元素中选出最小或最大的一个元素存放在起始位置 然后再从剩余的未排序元素中寻找到最小大元素然后存放到第二位。 以此类推直到全部待排序的数据元素的个数为零
选择排序在交换过程中可能会改变相同元素间的原始顺序 在一趟选择如果一个元素比当前元素小而该小的元素又出现在一个和当前元素相等的元素后面那么交换后稳定性就被破坏了
比如序列arr [5 8 5 2 9]第一遍选择中第1个元素5会和2交换 数组变成arr [2 8 5 5 9]两个相对元素5相对先后顺序变化了所以选择排序是非稳定的
插入排序
算法逻辑
通过构建有序序列对于未排序的数据在已排序序列中从后向前扫描找到相应位置并插入工作原理类似于整理扑克牌 int[] array {5,4,3,2,1};for (int i 1; i array.length; i) {for (int j i; j 0; j--) {//不断和有序列表元素比较大的放后面if (array[j - 1] array[j]) {int tmp array[j - 1];array[j - 1] array[j];array[j] tmp;}}}}打印输出
外循环第1次 第2个元素和第1个元素比较符合条件替换
内循环第1次[4, 5, 3, 2, 1]
外循环第2次 第3个元素和前2个元素比较符合条件替换
内循环第1次[4, 3, 5, 2, 1]
内循环第2次[3, 4, 5, 2, 1]
外循环第3次 第4个元素和前3个元素比较符合条件替换
内循环第1次[3, 4, 2, 5, 1]
内循环第2次[3, 2, 4, 5, 1]
内循环第3次[2, 3, 4, 5, 1]
外循环第4次 第5个元素和前4个元素比较符合条件替换
内循环第1次[2, 3, 4, 1, 5]
内循环第2次[2, 3, 1, 4, 5]
内循环第3次[2, 1, 3, 4, 5]
内循环第4次[1, 2, 3, 4, 5]
外循环总次数:4内循环总次数:10,最终排序数组[1, 2, 3, 4, 5]外层循环标识并决定待比较的数值
内层循环为待比较数值确定其最终位置和上面的排序的区别在于: 冒泡排序每次外循序将一个数归位将最值元素放入合适的对应位置 选择排序每次外循环能确定一个索引位置 选择了哪个元素
而直接插入排序每次外循环确定的是一个有序列表这个有序列表每次外循序一次 增加一个元素到这个有序表
第一次外循环 比较索引1的值和首的值大小并决定是否交换后面的元素内容不管的着就相当于把原数组切割相当于得到一个有序数组{45} 和 剩余待管理的数组{x,x,x}
索引01234外循环第1次45***
第二次循环从剩余待管理数组{x,x,x}按照顺序取一个元素和有序数组{45}里面的元素比较并直接插入合适的位置相当于得到一个有序数组{345} 和 剩余待管理的数组{x,x,x}然后依次类推
索引01234外循环第1次345**
该算法设计亮点之一在于利用了数组元素在存储空间的联系性原数组切割后有序列表和未管理列表总空间大小还是原数组空间未管理列表拿出以为元素相当于空间减少1 对于的有序列表空间加1
时间复杂度最好O(n)最坏和平均O(n^2)
上面的逻辑步骤里面 随着有序列表越长内循环次数越多,最坏的情况就是数组顺序完全是相反的
原始数组 [5, 4, 3, 2, 1]外循环第1次:确定有序列表[4, 5, *, *, *] 内循环1一次:n-4
外循环第2次:确定有序列表[3, 4, 5, *, *] 内循环2一次:n-3
外循环第3次:确定有序列表[2, 3, 4, 5, *] 内循环3一次:n-2
外循环第4次:确定有序列表[1, 2, 3, 4, 5] 内循环4一次:n-1
需要进行(n-1)(n-2)…21 n*(n-1)/2次用时间复杂度表示 是O(n^2)上面的展示代码就是最坏情况时间复杂度就是O(n^2)
那最好的情况下数组顺序正好是正序的原始数组 [1, 2, 3, 4, 5]但是需要调整一步算法逻辑 调整的插入排序算法加强点在于:利用已知序列表的排序性,逻辑解读:
原始数组 [135468]按正序
第一次外循环
第一个元素和第二个元素比较并确定长度为2的有序列表
得到一个有序数组{13} 和 剩余待管理的数组{x,x,x,x}第二次外循环
第三个元素5和有序列表元素{13}比较
这里就利用已知序列表的排序性,有序列表已经排序了最后元素也是最大的是3
拿元素5和元素3比较如果比元素3大那有序列表前面的元素一定都比该元素小的就不用比了
得到一个有序数组{1,3,5} 和 剩余待管理的数组{x,x,x}第三次外循环
第四个元素4和有序列表元素{135}比较
拿元素4和元素5比结果比元素5小交换两者位置
然后继续往前比
拿元素4和元素3比结果比元素3大好前面的都不用再比了循序上面步骤直到外层循序结束那这里看下时间复杂度
外层循序总共次数n-1次这个省不掉的外层循序对应的内层循环里每次最理想的情况就是待比较的元素比有序列表的最后元素大
这样外层循序里的比较次数就是1那这种情况下的总的时间复杂度就是n-1就是O(n)这种思路对应的代码: public static void main(String[] args) {int[] array {1,2,3,4,5};int i, j;int temp;//外层循序从未知排序列表开始for (i 1; i array.length; i) {//未知排序列表第一个元素准备往有序列表插入的元素temp array[i];j i - 1;/**待插入的元素 和有序列表从后往前顺序开始比较大小*不满足j0 array[j] array[i] 的两种情况* 1.有序列表从后往前遍历到头了结束这次循环* 2.array[j] array[i]找到合适插入的位置了*/for (;j0 array[j] array[i];j-1){//插入的位置不符合要求有序列表的元素往后移array[j 1] array[j];j--;}//待插入的元素插入到合适位置array[j 1] temp;} 所以直接插入排序复杂度在(0/n) 到 O(n^2) 之间但(0/n)也是极端下才有这段展示代码时间复杂度就是O(n) 默认的平均时间复杂度为O(n^2) 平均时间复杂度O(n^2) 最坏时间复杂度O(n^2) 最好时间复杂度O(n)正好数组的顺序就是我们需要的排序而且优化算法
插入排序:稳定性算法
插入排序插入排序是稳定的因为插入时只有当前元素比前面的元素小才会插入并且插入位置是有序区的最后一个位置
比如数组序列arr [1,3,2,2] 第一次排序后变化 [1,2,3,2] 第二次排序后变化 [1,2,2,3] 相对元素2的相对顺序没有变化原来在前面的元素2还是在前面
希尔排序
插入排序每次移动比较的是1位希尔排序是插入排序的高效改进版本通过引入“增量gap”分组来预处理数据使得元素可以一次移动多位从而减少总的移动次数和后续插入排序的工作量
逻辑步骤
1.选择增量序列gap: 增量序列的选择对希尔排序的性能至关重要。常见的增量序列有
希尔原始序列gap n/2, n/4, ..., 1Hibbard序列1, 3, 7, ..., 2^k-1Sedgewick序列1, 5, 19, 41, ...由9×4^k - 9×2^k 1或4^k - 3×2^k 1组成
2.按增量分组对每个子序列 进行插入排序操作 区别于直接插入排序每次都是从未排序的数组排序选择出最值插入到有序区间这样相当于每次增量都是1。希尔排序通过增量序列值每次都是“跳着”选择排序的空间比如gap n/2
初始数组: [8, 3, 5, 1, 4, 2, 7, 6]0 1 2 3 4 5 6 7
gap4:增量分组
Group1: [8, 4] - 排序后虚拟数组: [4, 8]
Group2: [3, 2] - 排序后虚拟数组: [2, 3]
Group3: [5, 7] - 排序后虚拟数组: [5, 7]
Group4: [1, 6] - 排序后虚拟数组: [1, 6]
这样的好处在于
每个虚拟数组的首位都是最值最终排序数组的首位的最值也从这些总序列数组产生
同样第二个最值也从各自排序后子序列中的第二位产生这样竖着合并起来
第一次合并[4, 2, 5, 1, 8, 3, 7, 6]缩小增量继续排序gap 2分组:
当前数组[4, 2, 5, 1, 8, 3, 7, 6]
对应索引:0 1 2 3 4 5 6 7
Group1: [4, 5, 8, 7] - 排序后: [4, 5, 7, 8]
Group2: [2, 1, 3, 6] - 排序后: [1, 2, 3, 6]
第二次合并[4, 1, 5, 2, 7, 3, 8, 6]缩小增量继续排序gap 1最终插入排序
执行标准插入排序:
[4, 1, 5, 2, 7, 3, 8, 6]
第一次→ [1, 4, 5, 2, 7, 3, 8, 6]
第二次→ [1, 4, 5, 2, 7, 3, 8, 6]
第三次→ [1, 2, 4, 5,7, 3, 8, 6]
直到完成最终排序
→ [1, 2, 3, 4, 5, 6, 7, 8] (完成)下面已希尔原始序列gap(每次减半)为例 代码展示 public static void shellSort(int[] arr) {int n arr.length;//初始增量序列设为数组长度的一半逐步缩小增量直到gap为1for (int gap n/2; gap 0; gap / 2) {// 对每个子序列进行插入排序从gap开始subsequenceShort(array,n,gap);}}进入每个子序列进行插入排序subsequenceShort方法 private static void subsequenceShort(int[] array,int n, int gap) {//开始位置从每次增量分组索引位置开始for (int i gap; i n; i) {// 当前待插入变量元素array[gap]int temp array[i]; int j;// 对以gap为间隔的子序列进行插入排序,将比temp大的元素向前移动 交换for (j i; j gap array[j - gap] temp; j - gap) {array[j] array[j - gap];}// 插入到正确位置array[j] temp;}}这段代码眼熟吗和上面插入排序优化时间复杂度算法里的一样只是插入排序每次移动单位是1这里替换成了增量序列gap
时间复杂度
如果按照上面每次已一半为增量序列 gap gap/2 初始gap n/2 那么最外层的循环次数就是底数为2的时间复杂度O(logn)
对于每个增量的内层循环就是一个插入排序 平均时间复杂度O(n^2) 最坏时间复杂度O(n^2) 最好时间复杂度O(n)
所以总体时间复杂度 最好的情况就是O(n) * O(logn) O(nlogn),
最坏的情况gao增量设置为1的定量这时候的希尔排序就完全退化成了退化排序那最坏的情况下的时间复杂度就完全取决于插入排序的最坏时间复杂度O(n^2)
所以希尔排序的时间复杂度的范围空间在O(nlogn)~O(n^2)
主要取决于 1.增量系列的选择比如每次是一半 还是三分之一 还是4分之一 2.子序列的有序性根据增量序列的子序列排序性状况越好对应的时间复杂度越低
不同增量序列的时间复杂度 {1, 2, 4, 8, …}这种序列的时间复杂度在最坏情况下是O(n^2)。 {1, 3, 7, …, 2^k-1} 这种序列的时间复杂度在最坏情况下是O(n^1.5)。 {1, 5, 19, 41, 109, …}这种序列的时间复杂度在最坏情况下可以达到O(n^1.3)
虽然看着希尔排序的时间复杂度好像还不如插入排序但是对应中等规模的数据处理上是比较快速的
希尔排序不稳定算法
希尔排序不是稳定性的算法虽然是插入排序的改进原有就在于增量序列的跳这比对
初始数组: [1, 3, 3, 2]初始增量gap n/2 对应元素a b c d 表示 gap2:增量分组 Group1: [1, 3] - 排序后虚拟数组: [1, 3] 这里的元素是[a, c] Group2: [3, 2] - 排序后虚拟数组: [2, 3]这里的元素是[d, b] 第一次合并[1, 2, 3, 3]对应元素是[a,d,c, b] 这里 bc两个相等元素的相对顺序变化了 所以希尔排序不是稳定算法
快速排序
快速排序采用分区治理策略。基本思想是选一个元素作为基准pivot将数组分成两部分使得左边部分的元素都小于等于基准右边部分的元素都大于等于基准然后递归地对左右两部分进行排序
步骤逻辑
快速排序步骤 1.选择基准pivot:数组中随机选一个元素,一般选首尾或者最中间位置的(这样好比较移动不乱) 2.分区Partition将数组分成两部分 左边元素都小于基准元素值5 右边元素都大于基准元素5 public static void main(String[] args) {//定义一个乱序的数组int[] arr {4,6,7,9,8,1,3,5};int head 0;int tail arr.length-1;// 进入自定义快速排序方法进行排序quickSort(arr,head,tail);System.out.println(Arrays.toString(arr));
}
// 进入到自定义的快速排序的方法
private static void quickSort(int[] arr, int head, int tail) {// 先判断待排序的数组是否有效存在,比如就head tail 就一个元素的不用排序了if (arr null || arr.length 0) return;if( head tail) return;//随选基准值这里选择最后一个元素作为基准int pivot arr[tail]; //定义一个小于基准的左子数组末尾索引值 int i head - 1; for (int j head; j tail; j) {// 当前元素 基准时将其交换到左侧if (arr[j] pivot) {i;//当前索引位置j的元素和 左子数组末尾元素后一位置元素交互//即左子数组扩容新增一位后面预留的右子数组少一位总体空间不变if(ij)continue;//如果相互交互的两个元素是同一个元素 跳过swap(arr, i, j);}}//上面都交互完了那么这时候将基准放到正确位置swap(arr, i 1, tail);// 记录下现在基准索引的值pivot i 1; }//指定索引位置的元素相互交互private static void swap(int[] arr, int i, int j) {if(i j) return;int temp arr[i];arr[i] arr[j];arr[j] temp;}代码到这里就是分区的步骤逻辑分区过程如下
原数组 [4, 6, 7, 9, 8, 1, 3, 5]基准选择末尾元素5这个时候的分区数组其实相当于
左子数组 右子数组
[还没有元素 4, 6, 7, 9, 8, 1, 3, 5]
理论上现在左子数组的末尾索引在元素4的前一位
即左子数组 末尾索引 元素4索引 - 1 代码表示就是int i head-1开始移动分区元素
第一次循环基准和第一个元素4比较 符合在左子数组条件
将元素4和左子数组末尾索引后一位的元素进行交换 只是这里正好是同一个索引位置元素
左子数组 右子数组
[4, 6, 7, 9, 8, 1, 3, 5]
现在左子数组里面有一个元素了末尾索引值变为0了第二次循环基准和第2个元素6比较 不符合在左子数组条件 跳过交互 开始下次循环
第三次循环基准和第3个元素7比较 不符合在左子数组条件 跳过交互 开始下次循环
第四次循环基准和第4个元素9比较 不符合在左子数组条件 跳过交互 开始下次循环
第五次循环基准和第5个元素8比较 不符合在左子数组条件 跳过交互 开始下次循环第六次循环基准和第6个元素1比较 符合在左子数组条件现在左子数组末尾索引值为0
将元素1和 左子数组的末尾元素的后一位元素交换即和索引位011位置的元素交互
左子数组 右子数组
[4, 1, 7, 9, 8, 6, 3, 5]
现在左子数组里面有两个元素了末尾索引值变为1了第七次循环基准和第7个元素3比较 符合在左子数组条件现在左子数组末尾索引值为1
将元素3和 左子数组的末尾元素的后一位元素交换即和索引位112位置的元素交互
左子数组 右子数组
[4, 1, 3, 9, 8, 6, 7, 5]
现在左子数组里面有三个元素了末尾索引值变为2了到这里循环就结束了然后左右子数组都分好了但基准还在右子数组里面
把基准元素5 挪到左右子数组中间现在左子数组末尾索引值为2
方法就是将基准元素5和 左子数组的末尾元素的后一位元素交换即和索引位213位置的元素交互
左子数组 基准 右子数组
[4, 1, 3, 5, 8, 6, 7,9]
到这里第一次分区结束,保证已选择的基准值为标准左变都比基准值小右边都比基准值大2.递归排序对左右子数组递归执行相同操作 上面分区后得到是左子数组都比基准值小,右子数组都比基准大但左右子数组还是乱序呢
左子数组 基准 右子数组
[4, 1, 3, 5, 8, 6, 7,9]处理的方式就是把左右子数组各看成一个数组只是右子数组的起始索引不是0而已还和上面的分区操作一样继续操作左右子数组 //上面我们代码理我们保留的基准现在的索引位置pivot i 1; // 递归排序左子数组 从左子数组的首位为到末尾元素(基准值元素前一位) 进行分区递归quickSort(arr, head, pivot - 1);// 递归排序右子数组 从基准值元素后一位的右边子数组 进行分区递归quickSort(arr, pivot 1, tail);处理逻辑步骤 Ⅰ.处理左子数组
左子数组 基准 右子数组
[4, 1, 3, 5, 8, 6, 7,9]左子数组[4, 1, 3] 索引值01 2 按照上面的分区步骤 得到一个分区数组
左子数组 二次基准值 右子数组
[1, 3, 4]
然后就分不动了 左子数组递归也就结束了,分区的左侧区域也就治理好了
左子数组 基准值 右子数组
已排序的区域:[1, 3, 4, 5,
未排序的区域: 8, 6, 7,9]Ⅱ.处理右子数组
右子数组[ 8, 6, 7,9] 索引值45 67 按照上面的分区步骤 基准值用末尾元素9
第一次
左子数组 右子数组
[ 8, 6, 7,9]第二次
左子数组 右子数组
[ 8, 6, 7,9]第三次
左子数组 右子数组
[ 8, 6, 7, 9]然后调整基准值位置
左子数组 基准值 右子数组
[ 8, 6, 7, 9 ]
右子树组第一次递归也就结束了到这里
已排序的区域:[1, 3, 4, 5, ,9]
未排序的区域: 8, 6, 7 然后继续递归按照上面的步骤执行未排序区域 8, 6, 7 ]最终于排序完成总结快速排序的步骤逻辑
这就是整个的分区治理的策略的概念一分二二分四四分八 等直到分不下去的时候也就排好序列了
一分二 一个基准元素(相当于插眼一个点) 两块区域
二分四 又多了两个基准元素(又查验两个点) 四块区域
.....直到分不下去了
这些基准值的点占据的位置就正好是整个数组的全部空间(点连成线)此时排序完成时间复杂度最好O(nlog2n)平均O(nlog2n)最坏O(n^2)
快速排序的时间复杂度 每次分区域成2份 就相当于除以2虽然得到的不一定是大小相同的区域(不是平均切割的哦)那这里的时间复杂度理论上应该就是能除以2多少次即 O(logn)已2为底数的对数
切割后的区域里面有循环进行比较然后决定是否交互这里的时间复杂度应该是O(n)
所以理论上的时间复杂度是O(logn) * O(n) O(nlogn)当然极端情况下时间复杂度会多点比如最坏情况下每次选择的基准元素都是当前子数组中的最小或最大元素这样每次分区都相于没分其中一个子数组和原数组一样递归调用就变成了类似for循序的作用在加上分区比较的for循序就是双层for循环了这样的快速排序实际上退化成了冒泡排序或选择排序时间复杂度变为O(n^2)
快速排序的性能很大程度上取决于选择的基准元素pivot基于基准元素的每次分区能越均衡整体时间复杂度越小这里不进行介绍更优化的分区方法只是了解快速排序的逻辑步骤 平均时间复杂度O(nlog2n) 最坏时间复杂度O(n^2) 最好时间复杂度O(nlog2n)
当然Java数组快速排序最简单是是可以使用Java内置的Arrays.sort()方法 int[] array {5,4,3,2,1};//调用排序方法Arrays.sort(arr1);Arrays.sort()方法默认使用的是快速排序算法但在某些情况下可能会退化为归并排序
快速排序不稳定算法
快速排序分区时可能改变相等元素顺序
先说一下快速排序的几种分区方式 1.单方向扫描分区:Lomuto洛穆托 分区方法就是常用方式以最后一个元素为基准的选择 2.双向扫描分区:Hoare霍尔 分区方法也是原始分区方式左右两边同时开始 3.三指针扫描分区和基准的元素相同的元素划出成一个区间左区间小于基准右边区间大于基准 先看Lomuto分区方式的稳定性选第一个元素为基准从左向右遍历 情况Ⅰ:和基准值相同的元素的顺序
示例数组[3a, 2, 4, 3b, 1]其中有两个相等的元素3用3a和3b区分3a表示第一个33b表示第二个3
基准值(pivot) 3a (第一个元素)交换移动条件是arr[j] pivot 就将其移动到左边
[3a, 2, 4, 3b, 1]0 1 2 3 4
从索引位置j 1开始 从左到右遍历到最后一个元素
j1 元素23a- 真交换arr[1]和arr[1] 后数组[3a, 2, 4, 3b, 1]
j2元素43a- 否不交换数组不变。继续。
j3元素3b3a)- 真 交换arr[2]和arr[3] 后数组[3a, 2, 3b, 4, 1]
j3元素13a)- 真 交换arr[3]和arr[4] 后数组[3a, 2, 3b, 1, 4]
此时遍历结束分区 左右序列2, 3b, 1 和 4注意最后一步将基准值索引0与左侧序列末尾元素1索引3对调
得到[1, 2, 3b, 3a, 4] 原数组是3a在前3b在后现在相对顺序改变了
所以得出非稳定性这个举例出现非稳定性的情况是因为
选择第一个元素为基准值如果后面元素有和基准值相同的元素在移动到左序列时候在最后一步替换基准值位置到左序列末尾这样一定会出现相等元素相对顺序改变的情况解决方案
1.如果选择的是第一个元素作基准值在Lomuto分区中一般将相等元素放在右侧不放在左侧
j3元素3b3a)- 真 这步条件里 改成 条件2.更简单按照Lomuto分区选择末尾元素还使用这个条件这样如果有和基准相等的元素放在左序列最后基准值调换到左序列末尾一定在还在原来相等元素的后面情况Ⅰ:在排序后的左序列末尾元素有相等元素
示例数组[3, 2a, 1, 2b]这里基准值选第一个元素3从索引位置j 1开始 从左到右遍历
j1 元素2a 3 - 真交换arr[1]和arr[1] 后数组不变[3, 2a, 1, 2b]
j2元素1 3 - 真交换arr[2]和arr[2] 后数组不变[3, 2a, 1, 2b]
j3元素2a 3- 真交换arr[3]和arr[3] 后数组不变[3, 2a, 1, 2b]
遍历结束将基准值索引0与左侧序列末尾元素2b索引3对调,呜呼
[2b, 2a, 1, 3] 元素2a 和 2b的先后顺序改变了,不稳定性体现了这两个例子都能看出在最后一步替换基准值和左序列末尾时候相同元素相对顺序变化的不可控
这就是不稳定的表现再看Hoare霍尔分区方式的稳定性 Hoare分区的逻辑及特性 1.已双向指针left和right 分别从两端开始指针扫描 2.区别单向扫描的分区最后已基准值作枢轴双向扫描最后已左右指针做区分左右序列递归调用时候选择右指针做分区索引
数组[3, 7, 8, 5, 2, 1, 9, 4]为例选择第一个元素 3 作为基准值 (pivot 3)
索引 0 1 2 3 4 5 6 7左边指针left 已首位 索引位置0开始从左到右顺序遍历不符合指针移动条件时 指针移动停
右边指针right 已末尾 索引位置7开始从右到做顺序遍历不符合指针移动条件时 指针移动停
注意:内层循环 指针移动条件 使用严格比较 (左循环使用 和 右循环)不能使用 和
主要是为了遍历时遇到和基准元素相同的元素时停止移动。这对于正确分区和避免死锁至关重要
不使用严格比较可能会出现越界异常无法正确异常 比如[4,3,2,1] left直接越界了
死锁(无限循环)主要会由于递归引起 这两点下面讲第一次扫描交换
此时left 0 (值 3), right 7 (值 4)
内左循环arr[0] (3) pivot (3)-否 不符合移动条件 - 停。此时left0(值 3)
内右循环:arr[7] (4) pivot (3)-真 符合移动条件 -往前移动指针 right-1 6(值 9) arr[6] (9) pivot (3)-真 符合移动条件 -往前移动指针 right-1 5(值 1) arr[5] (1) pivot (3)-否 不符合移动条件 - 停。此时right5(值 1)
左指针停下的位置表明该元素不符合在左序标准应该呆在右序
右指针停下的位置表明该元素不符合在右序标准应该呆在左序先进行左右指针交叉或相遇判断 if left right--不成立
好的 两者进行元素交换 - 交换 arr[0] (3) 和 arr[5] (1) --交换元素后左右指针各移1位
- 数组变为 [1, 7, 8, 5, 2, 3, 9, 4]
此时左右指针 L R
移动左右指针 L R
左半部分也就是左指针左侧 所有元素 小于或等于 基准
右半部分也就是右指针右侧 所有元素 大于或等于 基准第二次扫描继续缩小范围
此时left 1 (值 7), right 4 (值 2)
内左循环arr[1] (7) 3 -否 不符合移动条件 - 停。此时left1(值 7)
内右循环arr[4] (2) 3 -否 不符合移动条件 - 停。此时right4(值 2)
左右指针交叉或相遇判断 if left right--不成立
两者进行元素交换 - 交换 arr[1] (7) 和 arr[4] (2)
- 数组变为 [1, 2, 8, 5, 7, 3, 9, 4]
此时左右指针 L R
此时左右指针 L R第三次扫描
此时left 2 (值 8), right 3 (值 5)
内左循环arr[2] (8) 3 - 否 不符合移动条件 - 停。此时left2(值 8)
内右循环arr[3] (5) 3 - 真 符合移动条件 -往前移动指针 right-1 2(值 8) arr[2] (8) 3 - 真 符合移动条件 -往前移动指针 right-1 1(值 2) arr[1] (2) 3 - 否 不符合移动条件 - 停。此时right1(值 2)
然后左右指针 left right--成立-- 返回right 1(值 2) 值 跳出循环此时左指针left 2分区结果[1, 2, 8, 5, 7, 3, 9, 4] left 2 right 1
左分区 (索引 0 到 2): [1,2,8] - 1 2都小于基准(枢轴)3 但8好像不符合
右分区 (索引 1 到 7): [2,8,5,7,3,9,4] - 基准(枢轴)3 为什么放在右边序列里面了这里揭示了 Hoare 分区的一个重要特性
它不保证分区点左边的元素都严格 枢轴或者右边的都严格 枢轴。它的保证是在分区完成时
left 指针左边的所有元素不包括 left 本身都 枢轴()。
right 指针右边的所有元素不包括 right 本身都 枢轴。分区点 right 是划分两个区域的边界索引之一另一个是 left)看完逻辑步骤三个问题 1.为什么内层循环指针移动条件使用严格比较 (左循环使用 和 右循环) 2.为什么在分区结果左序列中会存在元素比基准值大的 3.为什么基准值会放在序列中而不是替换位置放在左右分区中间
延申的有点多了但是不把这些疑问解释清除是不好理解霍尔分区的特性上代码 public static void main(String[] args) {int[] arr {3, 7, 8, 5, 2, 1, 9, 4};//进入快速分区方法quickSort(arr, 0, arr.length - 1);}public static void quickSort(int[] arr, int low, int high) {//判断待分区的序列是否为有效数组空间if (low high) {//返回上次分区的右指针作为分区索引int pi partition(arr, low, high);//递归左序分区空间(low 到 pi)quickSort(arr, low, pi);//递归右序分区空间(pi1 到 high)quickSort(arr, pi 1, high);}}//霍尔分区方法private static int partition(int[] arr, int low, int high) {int pivot arr[low]; // 选择第一个元素作为枢轴int left low; // 初始化左指针 (实际会立即右移)int right high; // 初始化右指针while (true){// 无限循环内部检查退出条件// 移动左指针找到 pivot 的元素while (arr[left] pivot){// 注意严格小于才移动left left 1;}// 移动右指针找到 pivot 的元素while (arr[right] pivot){// 注意严格大于才移动right right - 1;}// 检查指针是否相遇或交叉if (left right) return right;// 返回分区点// 交换左右指针指向的元素swap(arr[left], arr[right]);// 移动指针继续扫描 (避免死锁尤其是元素等于pivot时)left left 1;right right - 1;}}这段代码是一个霍尔分区的递归调用解释一下上面的问题 1.为什么在分区结果左序列中会存在元素比基准值大的 这是因为左右指针是作为 分区边界线 用的 比如
分区结果[1, 2, 8, 5, 7, 3, 9, 4] right 1
左分区 (索引 0 到 2): [1,2,8] - 1 2都小于基准(枢轴)3 但8好像不符合
右分区 (索引 1 到 7): [2,8,5,7,3,9,4] - 元素2不符合而且基准(枢轴)3 为什么放在右边序列里面了这里是内层循环 指针移动条件 使用严格比较 (左循环使用 和 右循环)的好处之一
任何一个不等于基准元素的值 是不可能同时满足 和 严格条件
它必然会让左右指针双方一方移动一方停下
这样符合left right条件的情况就是left right1左右序列交互的元素个数最多是2个
而且这两个元素必然按照顺序排序好的如果是left right 满足那代表左右指针指向同一个元素而且这个元素必然是和基准元素相同的元素
此时左右序列交互的元素数量是一个以上这两种情况表示存在交互数据那么在递归调用之后交互范围的元素不可能同时给两边处理
只能归属一方要么归左边 要么归右边不然数据就重复了这里的处理方式就是讲交互范围的元素
已右指针作为分区索引切割划分
[1, 2, 8, 5, 7, 3, 9, 4] R
位置小于等于R的 属于真正意义上的左半部分
位置大于R 属于真正意义上的右半部分那么此时R指针数据是不算真正的右半部分如果已左指针作为分区索引切割划分
[1, 2, 8, 5, 7, 3, 9, 4] L
位置小于L的 属于真正意义上的左半部分
位置大于等于L 属于真正意义上的右半部分常见方式是已右指针作为分区索引方式这里也就是Hoare 分区的一个重要特性在重申一下
它不保证分区点左边的元素都严格 枢轴或者右边的都严格 枢轴。它的保证是在分区完成时
left 指针左边的所有元素不包括 left 本身都 枢轴()。
right 指针右边的所有元素不包括 right 本身都 枢轴。分区点 right 是划分两个区域的边界索引之一另一个是 left)2.为什么在分区结果左序列中会存在元素比基准值大的 个人认为的几点原因 a.稳定性在上面单向扫描最后替换基准值的不可控制相对顺序从而破坏稳定性
b.简化算法单向扫描最后替换基准值是选择基准值是一个分区标准最后分区后使用指针作为分区索引就不用特意在替换基准值并作为分区索引了使用基准值分区索引意义没必要了 c.算法的平衡基准值放在左边序列那一定是当前序列最大值基准值放在右边序列一定是右边序列的最小值 在快速排序的逻辑步骤讲解里每次分区左右序列越均衡越好,这和随机选则的基准值有很大关系应使用三数取中法取基准值的(随机三个元素 排序取中间值那个元素作基准值)如果分区后左右一侧元素为空极度失衡不好这里基准值放在子序列中有点配重意思基准值停留在子序列中为了均衡下次分区
作用体现:递归子序列分区如上面例子[8,5,7,3,9,4]无论基准值选哪个左边序列一定有元素3这样能保证左边序列不为空保证该分区算法不会失衡 3.为什么内层循环指针移动条件使用严格比较 (左使用 和 右循环) a.保证正确分区[18,5,7,3,9,4]选择第一个18作为基准恰巧是最大值如果使用 while (arr[left] pivot){//在比对元素4之后 再后移动,arr[6]越界报错了left left 1;}//发生越界异常程序都报错终止了 还谈什么能正常分区b.放在死锁(无线循环):发生再递归调用中 //为了放在报错 我们加上边界限制while (leftarr.length-1 arr[left] pivot){left left 1;}while (right0 arr[right] pivot){right right - 1;}if (left right) return right;会再递归调用出现无限循环
比如数组[3,3,3]
执行分区
quickSort(arr, 0, 2);
这样左边指针会一直指完整个数组最后left arr.length
右指针这样也会一直指完整个数组最后right -1[3,3,3]
左序列 L
右序列 R 0 1 2
也就是整个数组既然成左序列 又成右序列然后递归左版本分Larr.length 不执行分区方法了
但右半部分符合开始分区执行输入参数
quickSort(arr, pi 1, high); quickSort(arr, 0, 2); 就这样递归循环下去吧直到堆栈溢出报error以上就是霍尔分区的逻辑步骤以及注意特性现在对其稳定性解析
1.基准值被放在子序列中防止了像单向扫描最后替换基准值时相对顺序不可控的情况提高稳定性
2.不一定是相邻两个元素顺序交换所以相同元素的先后顺序不可控制 比如[5,1a,3,1b]基准值选择3第一次左右指针停留左指针停留在5右指针停留在1然后交换变更数组[1b,1a,3,5], 两个1的先后顺序变更
3.对于和基准值相同的元素稳定性完全破坏稳定性比如[3a,1,3b]第一次交换就是[3b,1,3a],相同元素3的先后顺序变更
总结相同元素霍尔分区不稳定算法分区
归并排序
归并排序Merge Sort是一种分治算法其核心思想是将数组分成两半分别排序然后合并两个有序数组。归并排序是稳定的排序算法时间复杂度为 O(n log n)但需要额外的空间。
逻辑步骤
算法步骤 1.分解Divide将数组递归地分成两个子数组直到每个子数组只有一个元素 2.解决Conquer对每个子数组进行排序单个元素自然有序 3.合并Combine将已排序的子数组合并成一个完整的有序数组
public static void main(String[] args) {int[] arr {38, 27, 43, 3, 9, 82, 10};// 复制一个临时存储数组并作为参数传入这样只new一次 能复用节省空间int[] temp new int[arr.length];//进入归并排序方法mergeSort(array, 0, array.length - 1, temp);
}进入归并排序的mergeSort方法 步骤1分解
private static void mergeSort(int[] arr, int left, int right, int[] temp) {if (left right) {//步骤1:分解 这里每次都是对半分,防止整数溢出不能平分的就元素给左边int mid left (right - left) / 2; // 排序左半部分leftmergeSort(arr, left, mid,temp);// 排序右半部分right mergeSort(arr, mid 1, right,temp);//步骤2解决 将拆分后的子数组进行排序 并 合并有序数组merge(arr, left, mid, right, temp,temp);}
}先图解看步骤1分解 到步骤2解决之间的逻辑
以数组 arr数组 [38, 27, 43, 3, 9, 82, 10] 为例
1. 分解[38, 27, 43, 3] 和 [9, 82, 10]继续分解[38, 27] [43, 3] [9, 82] [10]继续分解[38] [27] [43] [3] [9] [82] [10]注意:这里的拆分并不是将原数组分解成n个数组
只是将对应的索引值标记出来传递进入治理合并的方法里去
merge(arr, left, mid, right, temp);步骤2治理解决排序问题 // 解决并合并两个有序数组参数mid是左右区域分开的中间索引值(偏左指向)private static void merge(int[] arr, int left, int mid, int right, int[] temp) {int i left; // 左序列子数组初始位置索引指针int j mid 1; // 右序列子数组初始位置索引指针int t 0; // 临时存储数组的指针
原数组arr [38, 27, 43, 3, 9, 82, 10]已分解为 [38] [27] [43] [3] [9] [82] [10]
临时数组temp [0, 0, 0, 0, 0, 0,0]
第一次进入该方法比较执行的这样序列是[38] [27] 左序列索引为0 右序列索引为1
(0和1之间没有两个中间索引值总不能0.5吧所以参数mid偏左指向)就下面这样式的
left|mid righti j[38] [27]第一次进入该方法的参数 letf:0 mid:0 right:1 i:0 j:1步骤1比较左右子数组元素按序放入临时数组 //自旋条件是不能超出两块数组的空间范围while (i mid j right) {if (arr[i] arr[j]) {temp[t] arr[i];} else {temp[t] arr[j];}}
(i mid j right) 索引指针范围 符合条件
[38] [27] 比较得出最小元素是 27 放入临时存储数组temp
arr [38, 27, 43, 3, 9, 82, 10]
temp [27, 0, 0, 0, 0, 0,0]注意一下符合条件的元素放入temp后 其索引指针进行了后置1
如果仅仅是填充temp元素temp[t] arr[i];或者temp[t] arr[j];就可以了
为什么还要后置1呢因为还要把它作为判断标识:biao如i mid成立表明左序指针还在左数组范围内左序还存在未填充进temp的剩余元素,刚填充的元素是右侧的
left|mid righti j [38] [27]//这时候就将左边剩余元素按空间顺序陆续填充进tempwhile (i mid) {temp[t] arr[i];}如jright成立表明右序指针还在右数组范围内右序还存在未填充进temp的剩余元素,刚填充的元素是左序的
left|mid righti|j[38] [27]//这时候就将右边剩余元素按空间顺序陆续填充进tempwhile (j right) {temp[t] arr[j];}
填充后的数组
arr [38, 27, 43, 3, 9, 82, 10]
temp [27, 38, 0, 0, 0, 0,0]步骤2将temp中的元素全部拷贝回原数组 //重置临时数组索引指针从首位元素开始t 0;// 将temp中的元素全部拷贝回原数组while (left right) { //表明拷贝的范围只在这次排序的左右序列范围内arr[left] temp[t];}
拷贝后
arr [27, 38, 43, 3, 9, 82, 10]
temp [27, 38, 0, 0, 0, 0,0]
原来分解的数组[38] [27] 就归并成了 [27, 28]步骤4递归调用 再来看第二次参数进入执行
第二次要解决的是[43] [3]
参数
arr [27, 38, 43, 3, 9, 82, 10]
temp [27, 38, 0, 0, 0, 0,0]
left|mid righti j[43] [3]
letf:2 mid:2 right:3 i:2 j:3然后执行到比较大小 小的元素放入临时数组temp,这里元素3小于元素43,放入元素3
temp [3, 38, 0, 0, 0, 0,0]
left|mid righti j[43] [3]然后执行填充剩余元素,i没超过左序指针范围那就是左侧还有未填充元素进入temp,填充进去
temp [3, 43, 0, 0, 0, 0,0]此时数组arr和临时数组元素
arr [27, 38, 43, 3, 9, 82, 10]
temp [3, 43, 0, 0, 0, 0,0]开始按arr[left] temp[t];合并变成
arr [27, 38, 3, 43, 9, 82, 10]
原来分解的数组[43] [3]就归并成了 [3, 34]再来看第三次参数进入指向情况
第三次传入的参数letf:0 mid:1 right:3
arr [27, 38, 3, 43, 9, 82, 10]
temp [3, 43, 0, 0, 0, 0,0]
这次处理的是上面归并的两个数组[27, 38] [3, 43] (自上而下分解然后自下而上归并)left|mid righti j
[27, 38] [3, 34]
letf:0 mid:1 right:3 i:0 j:2然后执行比较arr[i] arr[j]while (i mid j right) {if (arr[i] arr[j]) {temp[t] arr[i];} else {temp[t] arr[j];}}
第一次:arr[0] arr[2] 否 temp填充arr[2]3 变成[3, 43, 0, 0, 0, 0,0] j
第二次:arr[0] arr[3] 是 temp填充arr[0]27 变成[3, 27, 0, 0, 0, 0,0] i
第二次:arr[1] arr[3] 是 temp填充arr[1]27 变成[3, 27, 28, 0, 0, 0,0] i
循环结束变成这样式的了
left|mid righti j
[27, 38] [3, 34]
这里i超出左侧数组指针范围表明元素填充完了右侧没有超还有待填充进temp的元素
temp [3, 27, 28, 34, 0, 0,0]然后开始拷贝
temp [3, 27, 28, 43, 0, 0,0]
arr [3, 27, 28, 43, 9, 82, 10] 到这里原数组第一次分解的左序 可就归并好了右边同样如此总结一下步骤
原数组[38, 27, 43, 3, 9, 82, 10] 分解[38, 27, 43, 3] 和 [9, 82, 10]继续分解[38, 27] [43, 3] [9, 82] [10]继续分解[38] [27] [43] [3] [9] [82] [10]第一次归并 [38] [27] 成 [27, 38]
第二次归并 [43] [3] 成[3, 43]
第二次归并 [27, 38] [3, 43] 成 [3, 27, 28, 43]
-----------
最后归并[3, 27, 28, 43][9, 10, 82] 得到最终排序的数组时间复杂度最好 平均 最坏都是O(nlog2n)
至于时间复杂度每次对半分这样时间复杂度是O(log2n) 循环比较并交互元素复杂度是O(n) 两者相乘O(nlog2n) O(n) * O(log2n) 由于每次都是对半分不像快速排序每次分可能两边极度不平衡导致退化成冒泡排序或选择排序所以归并排序是稳定的排序方式而快速排序就属于非稳定排序了
归并排序 平均时间复杂度O(nlog2n) 最坏时间复杂度O(nlog2n) 最好时间复杂度O(nlog2n)
归并排序:稳定性算法
归并排序在合并过程中如果遇到相等的元素会先保留原来顺序因此它是稳定的排序算法
它只是将数组从上往下不停拆分直到拆不动了然后开始比较排序在这个排序的过程中不断的是有序的左右子数组 比较元素然后合并这个过程是中相等元素的顺序是不变的
堆排序
区别于以上的基于数组结构的排序算法堆排序Heap Sort虽然实际操作的还是数组但是 是一种基于二叉堆Binary Heap这种数据结构所设计的一种排序算法堆是一个近似完全二叉树。并同时满足堆的性质即父节点的值总是大于或等于最大堆或小于或等于最小堆子节点的值
基于数组 隐式指针方式构建二叉堆 static class TaskTreeNode {int priority;TaskTreeNode (int x) {priority x;}}TaskTreeNode buildCompleteTaskTree() {int[] arr {38, 27, 43, 3, 9, 82, 10};// 构建初始数组TreeNode[]这里是一维静态数组TaskTreeNode[] nodes new TaskTreeNode [arr.length];// 按照先后顺序给所有节点创建节点TreeNode,并且加到数组nodes for (int i 0; i arr.length; i) {nodes[i] new TaskTreeNode (arr[i]);}//返回一个根节点就是一个符合的完全二叉树return nodes[0];}父子节点之间的索引值的数学规律 得到的隐式指针可以看这里关于完全二叉树的详细介绍
父节点索引i
其存在的左边子节点索引值为2*i 1
其存在的右边子节点索引值为2*i 2基于数组的隐式指针构建二叉堆的方式又免除了 替换操作节点时候变更显示指针的麻烦所以二叉堆的实现大都是基于数组实现的
隐式指针的完全二叉树实际上就是数组这种设计的好处 1.可以利用二叉树的数据结构优势和数学规律 2.可以利用数组优势数组连续的存储空间可以根据索引值快速定位 3.操作数据时候不用再处理二叉树中的节点指针指向关系 4.完全二叉树的数据结构特征就决定了一维数组的数据集是一定符合完全二叉树的即父子节点索引值的规律是一定适用的
堆排序的算法步骤过程叫 堆化过程而堆类型分最大堆MaxHeap(大顶堆)和最小堆MinHeap(小顶堆)两种
最大堆MaxHeap
最大堆MaxHeap(大顶堆) ①首先它必须满足完全二叉树的定义 ②其次堆树中任一节点的值总是不小于其子节点的值 ③最大的值是根节点堆树中每个节点的子树都是堆树注意没有要求左右节点的大小关系
如下图所示 #mermaid-svg-rP8o6r6NqnA4Pw1w {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-rP8o6r6NqnA4Pw1w .error-icon{fill:#552222;}#mermaid-svg-rP8o6r6NqnA4Pw1w .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-rP8o6r6NqnA4Pw1w .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-rP8o6r6NqnA4Pw1w .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-rP8o6r6NqnA4Pw1w .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-rP8o6r6NqnA4Pw1w .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-rP8o6r6NqnA4Pw1w .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-rP8o6r6NqnA4Pw1w .marker{fill:#333333;stroke:#333333;}#mermaid-svg-rP8o6r6NqnA4Pw1w .marker.cross{stroke:#333333;}#mermaid-svg-rP8o6r6NqnA4Pw1w svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-rP8o6r6NqnA4Pw1w .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-rP8o6r6NqnA4Pw1w .cluster-label text{fill:#333;}#mermaid-svg-rP8o6r6NqnA4Pw1w .cluster-label span{color:#333;}#mermaid-svg-rP8o6r6NqnA4Pw1w .label text,#mermaid-svg-rP8o6r6NqnA4Pw1w span{fill:#333;color:#333;}#mermaid-svg-rP8o6r6NqnA4Pw1w .node rect,#mermaid-svg-rP8o6r6NqnA4Pw1w .node circle,#mermaid-svg-rP8o6r6NqnA4Pw1w .node ellipse,#mermaid-svg-rP8o6r6NqnA4Pw1w .node polygon,#mermaid-svg-rP8o6r6NqnA4Pw1w .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-rP8o6r6NqnA4Pw1w .node .label{text-align:center;}#mermaid-svg-rP8o6r6NqnA4Pw1w .node.clickable{cursor:pointer;}#mermaid-svg-rP8o6r6NqnA4Pw1w .arrowheadPath{fill:#333333;}#mermaid-svg-rP8o6r6NqnA4Pw1w .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-rP8o6r6NqnA4Pw1w .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-rP8o6r6NqnA4Pw1w .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-rP8o6r6NqnA4Pw1w .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-rP8o6r6NqnA4Pw1w .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-rP8o6r6NqnA4Pw1w .cluster text{fill:#333;}#mermaid-svg-rP8o6r6NqnA4Pw1w .cluster span{color:#333;}#mermaid-svg-rP8o6r6NqnA4Pw1w div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-rP8o6r6NqnA4Pw1w :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 14 12 11 10 9 8 7 堆排序
以数组 [4, 10, 3, 5, 1,12] 为例展示堆排序过程
初始数组: [4, 10, 3, 5,1,12]对应的二叉堆结构4/ \10 3/ \ / 5 1 12
根节点为4 索引值为0
左子节点10 索引值为1 隐藏指针链接关系为 leftIndex 2*rootIndex 1
右子节点3 索引值为2 隐藏指针链接关系为rightIndex 2*rootIndex 2
节点3是该二叉堆最后一个非叶子节点 索引值为(N-1)/2
.......这些规律介绍可以点击上面关于完全二叉树的详情介绍链接...........二叉堆排序调整数据序列将待排序的序列构造成一个大顶堆(最大堆) public static void main(String[] args) {int[] array {4, 10, 3, 5, 1,12};int n array.length;// 步骤1: 构建最大堆从最后一个非叶子节点开始 也就是倒数第二层最后一个节点开始for (int i n / 2 - 1; i 0; i--) {heapSort(array, n, i);}}//堆排序(下沉对比)private static void heapSort(int[] array, int heapSize, int rootIndex) {int maxValueIndex rootIndex; // 先初始定义最大值的元素是根节点int left 2 * rootIndex 1; // 左子节点索引int right 2 * rootIndex 2; // 右子节点索引// 如果左子节点比根节点大if (left heapSize array[left] array[rootIndex]) {maxValueIndex left;}// 如果右子节点比当前最大值大if (right heapSize array[right] array[rootIndex]) {maxValueIndex right;}// 如果最大值不是根节点需要交换值if (maxValueIndex ! rootIndex) {swap(array, rootIndex, maxValueIndex);}}//原地排序 交互对应索引的值private static void swap(int[] array, int i, int j) {int temp array[i];array[i] array[j];array[j] temp;}打印输出
第1次循环后[4, 10, 12, 5, 1, 3]
第2次循环后[4, 10, 12, 5, 1, 3]
第3次循环后[12, 10, 4, 5, 1, 3]来看具体步骤
二叉堆数据结构4/ \10 3/ \ / \5 1 12 NIL(空节点)第一次排序
选择最后一个非叶子节点也就是倒数第二层的最后一个节点(最后一个子树)
比较的范围是3 和左子节点比较 rootValueleftValue/ \ ---------------- 更新最大值索引值给MaxIndex
12 NIL(空节点)
swap交互值 数组变更为[4, 10, 12, 5, 1, 3]
此时二叉堆数据结构 未排序 的范围4/ \10 12/ \ 5 1 第二次排序 递减推选择节点 10
比较的范围是10 和左子节点比较 rootValueleftValue 和右子节点比较/ \ ---------------- 不更新maxIndex---------------- 不更新maxIndex
5 1
这次数组元素顺序不需要变更
此时二叉堆数据结构 未排序 的范围4/ \10 12第三次排序 和上面一样步骤
比较的范围是4 和右子节点比较/ \
10 12
和左子节点比较 MaxValueleftValue--- 更新maxIndex 此时maxIndex 对应value 10
和右子节点比较 MaxValueleftValue--- 更新maxIndex 此时maxIndex 对应value 12
swap交互值 数组变更为[12, 10, 4, 5, 1, 3] 这样排序完成
最终二叉树数据结构调整未12/ \10 4/ \ / \5 1 3 NIL(空节点)总结一下 1.归并排序递归排序原地排序
归并排序每次一个子树从最后的开始往上递推排序最终将最值 给“堆”到顶上去
递归排序for循环控制的每次子树范围的比较根据子树个数循环次数
原地排序每次有需要交互元素的时候根据索引值进行交互不需要申请额外的空间2.看下堆排序的复杂度 外层循环或者说递归次数是0到n/2 - 1 接近n/2每次循环里面子树root和left right比较最多进行两次比较和互换操作 所以复杂度就是(n/2 ) 乘以2 n所以堆排序的时间复杂度是O(n)网上很多都说堆排序的时间复杂度都是O(nlogn)这个说法是不太准确的正确的说法应该是构建最大堆未或者最小堆的时间复杂度O(nlogn)包括堆排序的O(n)和堆调整O(logn) 构建堆:
1.堆排序 对一个非排序的完全二叉树进行排序时间复杂度O(n) 2.堆调整进行堆调整的前提是 当前堆已经是最大堆或者最小堆了 a.当向一个堆中新增节点上浮调整排序每次只需要和其对应的父节点比较时间复杂度O(log n) b.当从堆中取出一个节点后剩余的堆中节点下沉调整已维持最大堆或最小堆特性时间复杂度O(logn)
堆调整
区别于我们上面从一个已经存在元素的堆再进行排序堆调整示例从数据元素最初添加进去就按照最大堆的数据结构添加 第一步:创建一个堆的内部表示
public class MaxHeap {private final int[] heap;//用来存放元素的数组private int size; //当前堆的大小也就是节点N的数量private final int capacity; //堆的最大容量public MaxHeap(String mame,int capacity) {this.capacity capacity;this.size 0; this.heap new int[capacity];//初始化堆数组}二叉堆的构造函数给一个初始容量值相当于 MaxHeap maxHeap new MaxHeap(10);
先初始一个容量为10的数组Heap,初始元素默认值都为0
0 0 0 0 0 0 0 0 0 0 第二步:实现添加元素的操作insert // 插入元素public void insert(int value) {if (size capacity) throw new IllegalStateException(Heap is full);heap[size] value;//将新的元素放在堆的末尾heapifyUp(size);//上浮新的元素已来维持最大堆或者最小堆的性质size; //增加堆的大小}// 核心方法上浮调整private void heapifyUp(int index) {int parent (index - 1) / 2; //计算新插入节点对应的父节点的索引while(index 0 ){if(heap[index] heap[parent]){//和父节点比较swap(index, parent);//原地排序:交互位置index parent;//更新当前索引为父节点的位置 然后继续往上比}else{break;}}}// 辅助方法交换元素private void swap(int i, int j) {int temp heap[i];heap[i] heap[j];heap[j] temp;}测试代码 public static void main(String[] args) {//表明容量大小为10如果是任务优先级队列表明最大同时9个任务,也就是二叉堆节点最多9个MaxHeap maxHeap new MaxHeap(10);maxHeap.insert(10);maxHeap.insert(15);maxHeap.insert(20);maxHeap.insert(19);maxHeap.insert(22);maxHeap.insert(13);maxHeap.insert(6);//...如添加元素的数量超过了数组容量,报错抛出 }打印输出
第1次插入节点后[10, 0, 0, 0, 0, 0, 0, 0, 0, 0]
第2次插入节点后[15, 10, 0, 0, 0, 0, 0, 0, 0, 0]
第3次插入节点后[20, 10, 15, 0, 0, 0, 0, 0, 0, 0]
第4次插入节点后[20, 19, 15, 10, 0, 0, 0, 0, 0, 0]
第5次插入节点后[22, 20, 15, 10, 19, 0, 0, 0, 0, 0]
第6次插入节点后[22, 20, 15, 10, 19, 13, 0, 0, 0, 0]
第7次插入节点后[22, 20, 15, 10, 19, 13, 6, 0, 0, 0]二叉堆数据结构随着添加进的数据进行上浮调整节点位置插入数据前提是该二叉堆已经是最大堆所以每次比较都只需要和父节点比较就行(不用和旁边节点比较了因为旁边节点肯定没有父节点大)只是如果比父节点大交互位置后还需要再往上一层比较直到能确定值不在比父节点的值大
新增节点--父节点--爷爷节点--太爷爷节点--....--根节点那最好的情况下:新增节点就是最小的到父节点比较来位置都不需要交互 时间复杂度O(1)
那最坏的情况下新增节点 要比较到 根节点才能知道最大值是哪个并确定最值位置
那这种情况下 上面这条线上有多少个节点就需要多少次就是对应的时间复杂度还是画图为例吧,已4层二叉堆为例A/ \B C/ \ / \D E F G/ \ / \ / \ / \
H I J K M L O NEW最坏情况下需要比较次数:NEW--G--C--A
往上推导父节点索引 parent (N- 1) / 2,如果满足上面比较次数那就是需要比较到A
那此时parent (N- 1) / 2 0也就是共需要多少次(N- 1) / 2为0就个次数是对应的时间复杂度
对应的表示就是O(log2 n)第三步:查看最大元素的操作peek public int peek() {if (size 0) throw new IllegalStateException(Heap is empty);return heap[0];//返回根节点元素也就是最大元素第四步:取出最大元素的操作poll // 删除最大值每次移除都是根元素 就不用索引值了public int poll() {//检查堆是不是空了if (size 0) throw new IllegalStateException(Heap is empty);int max heap[0];//保持一下最大元素值heap[0] heap[size - 1];//将最后一个元素赋值到根节点先保持下二叉堆的完整size--;//减少堆的大小heapifyDown(0);//向下调整return max;//返回最大元素}// 核心方法下沉调整private void heapifyDown(int index) {int maxIndex index;//先假设最大值是当前节点int left 2 * index 1;//左子节点索引int right 2 * index 2;//右子节点索引if (left size heap[left] heap[maxIndex]) //和左子节点比较元素大小maxIndex left;//更新最大元的索引if (right size heap[right] heap[maxIndex])maxIndex right;//更新最大元的索引if (index ! maxIndex) {swap(index, maxIndex);//原地排序交互当前位置与最大的位置heapifyDown(maxIndex);//往下递归调整}}这个方法实现的根基在于移除元素操作的二叉堆是最大堆或者最小堆在移除节点操作时候通过下沉调整堆中节点元素位置已维持最大堆或最小堆的特征
[20, 15, 11, 10, 12, 9, 6, 0, 0, 0]20/ \15 11/ \ / \ 10 12 9 6
此时最大堆的最大值为根节点第二大的值就在左右子树的顶点中产生即15 或者 11第一步先赋值heap[0] heap[size - 1];//将最后一个元素赋值到根节点先保持下二叉堆的完整
此时的数组数据为[6, 15, 11, 10, 12, 9, 6, 0, 0, 0]
对应对二叉树结构为6/ \15 11/ \ / 10 12 9 会发现和数组比少了一个老6
因为size,堆大小表示值size在取出最大元素进行了size--,虽然当前数组元素是7个但有效节点就6个了第二步骤 开始递归判断6/ \ --根节点和左右节点两次比较得出最大值并替换6和15的位置15 11
此时树结构为15/ \ 6 11 / \ / 10 12 9 此时新的根节点已经确定了再往下进行的是调整节点已维持最大堆的性质第二次递归判断比较6/ \10 12 --根节点和左右节点两次比较得出最大值并替换6和12的位置
二叉堆的数据结构变成15/ \12 11/ \ / 10 6 9 最新的需要比较的节点是6在索引4是叶子节点了循序也就结束了
最新数组为 [15, 12, 11, 10, 6, 9, 6, 0, 0, 0]其中在insert方法
if (size capacity) throw new IllegalStateException(Heap is full);
每添加一次size; 如果capacity为10 那么添加到第10次就会触发报错
所以这个容量为10的数组最多能同时容纳9个有效元素再来看时间赋值度
第一次根节点和左右子节点比较 替换并决定下次比较是左树还是右树
第二次节点和其左右子节点比较 替换并决定下次比较是其左树还是右树
-------------------这样相当于每次都除以2 时间复杂度O(log2n)---------------测试一下 public static void main(String[] args) {MaxHeap maxHeap new MaxHeap(10);maxHeap.insert(10);maxHeap.insert(15);maxHeap.insert(20);maxHeap.insert(9);System.out.println(此时堆中有效节点数maxHeap.size);System.out.println(最大值maxHeap.peek());System.out.println(移除的最大值maxHeap.poll());System.out.println(最新最大值maxHeap.peek());}最小堆和这个逻辑思路类似总体来说时间复杂度 1.构建堆O(n) 2.每次堆调整O(log n) 总时间复杂度O(n log n)最优、最差和平均情况相同
使用堆Heap来实现优先级队列管理
堆排序讲的比较多顺便这里在提一下为什么选择使用二叉堆来进行优先级任务队列的管理
首先明确优先级队列的操作需求插入任务带优先级和取出最高优先级的任务即出队这就要求 最快找出最小或最大元素为了删除最小或最大
满足该需求的数据结构符合条件 1.最快找出最小或最大元素这点上大顶堆取根节点值arr[0]就可以复杂度为O(1)但是首位为最大值的平常数组 或者 首位为最大值的链表这点也符合为什么不用他们来管理呢 2.数据结构调整上复杂度为了上述条件1新增或删除后的数据结构首位保持是最值元素那么新增或者删除元素后的数据结构调整是必要的选择数据结构调整上复杂度最低的
①.先看没有采用二叉堆数据结构设计思路的完全排序的数组 int[] arr new int[10];
先初始一个容量为10的数组,初始元素默认值都为0
0 0 0 0 0 0 0 0 0 0 设计思路上1将最大值放在首位,后续位置不管排序上
第一次来添加优先级值9 放入索引0
9 0 0 0 0 0 0 0 0 0
第二次添加优先级元素值7 和首位比较 然后决定索引位置放入数组
9 7 0 0 0 0 0 0 0 0
第二次添加优先级元素值10 和首位比较 然后决定索引位置放入数组
10 7 9 0 0 0 0 0 0 0
时间复杂度只需要取[0] 比较插入值 是O(1)
调整上:
取出首位最大值元素[0]剩下的元素哪个是最大的呢冒泡排序或者选择排序给它重新排序
时间复杂度瞬间就上来了设计思路上2完全按照从大到小顺序排放这就已经是冒泡排序或者选择排序了
排序上
第一次来添加优先级值9 放入索引0
9 0 0 0 0 0 0 0 0 0
第二次添加优先级元素值7 和前面的比较 然后决定索引位置放入数组
9 7 0 0 0 0 0 0 0 0
第二次添加优先级元素值10 和前面的比较 然后决定索引位置放入数组
10 9 7 0 0 0 0 0 0 0
再看调整上
取出首位最大值元素[0]剩下的元素最大的[1]
但是注意是取出也就是[0]对应的元素不在数组了原来[1]变成[0]
9 7 0 0 0 0 0 0 0 0
每个元素都往前平移一位时间复杂度和空间复杂度又上一层②再来看链表再进行优先级节点调整上的时间复杂度 #mermaid-svg-h6qLYbzKFDLIhqdT {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-h6qLYbzKFDLIhqdT .error-icon{fill:#552222;}#mermaid-svg-h6qLYbzKFDLIhqdT .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-h6qLYbzKFDLIhqdT .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-h6qLYbzKFDLIhqdT .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-h6qLYbzKFDLIhqdT .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-h6qLYbzKFDLIhqdT .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-h6qLYbzKFDLIhqdT .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-h6qLYbzKFDLIhqdT .marker{fill:#333333;stroke:#333333;}#mermaid-svg-h6qLYbzKFDLIhqdT .marker.cross{stroke:#333333;}#mermaid-svg-h6qLYbzKFDLIhqdT svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-h6qLYbzKFDLIhqdT .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-h6qLYbzKFDLIhqdT .cluster-label text{fill:#333;}#mermaid-svg-h6qLYbzKFDLIhqdT .cluster-label span{color:#333;}#mermaid-svg-h6qLYbzKFDLIhqdT .label text,#mermaid-svg-h6qLYbzKFDLIhqdT span{fill:#333;color:#333;}#mermaid-svg-h6qLYbzKFDLIhqdT .node rect,#mermaid-svg-h6qLYbzKFDLIhqdT .node circle,#mermaid-svg-h6qLYbzKFDLIhqdT .node ellipse,#mermaid-svg-h6qLYbzKFDLIhqdT .node polygon,#mermaid-svg-h6qLYbzKFDLIhqdT .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-h6qLYbzKFDLIhqdT .node .label{text-align:center;}#mermaid-svg-h6qLYbzKFDLIhqdT .node.clickable{cursor:pointer;}#mermaid-svg-h6qLYbzKFDLIhqdT .arrowheadPath{fill:#333333;}#mermaid-svg-h6qLYbzKFDLIhqdT .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-h6qLYbzKFDLIhqdT .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-h6qLYbzKFDLIhqdT .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-h6qLYbzKFDLIhqdT .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-h6qLYbzKFDLIhqdT .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-h6qLYbzKFDLIhqdT .cluster text{fill:#333;}#mermaid-svg-h6qLYbzKFDLIhqdT .cluster span{color:#333;}#mermaid-svg-h6qLYbzKFDLIhqdT div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-h6qLYbzKFDLIhqdT :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} A B C D E 使用单链表的方式进行管理优先级队列的方式按照大小顺序排放最大的放在队首
// 继承一个比较接口这样可以方便比较节点里面的优先级值大小
public class PriorityQueueTest T extends ComparableT {//定义一个队首private NodeT head;//记录任务节点数private int size;private static class NodeT {T data;NodeT next;Node(T data) {this.data data;this.next null;}}//新增元素public void insert(T data) {//根据插入优先级值 生成新的节点NodeT newNode new Node(data);//和最大值头子比较如果比队列首位大就把新节点放在首位if (head null || data.compareTo(head.data) 0) {newNode.next head;head newNode;} else { //否则就往下遍历查找合适插入的位置NodeT current head;// 已值大小作为判断条件不断往下遍历查找位置while (current.next ! null data.compareTo(current.next.data) 0) {current current.next;}//直到找到合适插入的位置,最坏情况可能需要到队尾 时间复杂度 O(n)newNode.next current.next;current.next newNode;}size;}//移除最大元素简单 拿掉队首的和第二位的指针指向关系就行 时间复杂度 O(1)public T poll() {if (head null) {throw new NoSuchElementException(Priority queue is empty);}T data head.data;head head.next;size--;return data;}// 查看队头元素 查看最大值元素时间复杂度也是O(1)public T peek() {if (head null) {throw new NoSuchElementException(Priority queue is empty);}return head.data;}// 检查队列是否为空public boolean isEmpty() {return head null;}//获取队列大小sizepublic int size() {return size;}
}时间复杂度
插入操作insert在最坏情况下插入操作需要遍历整个链表以找到合适的位置。因此 时间复杂度为O(n)其中 n 是链表的长度。 删除最小元素操作deleteMin删除操作总是从链表的头部进行因此时间复杂度为 O(1)。 获取最小元素操作peek获取最小元素操作也是从链表的头部进行因此时间复杂度为 O(1)。 判断队列是否为空isEmpty这个只要检查链表的头部是否为 null因此时间复杂度为 O(1)。 获取队列大小size这个操作只需要返回一个整数值因此时间复杂度为 O(1)。
总结 1.二叉堆的堆调整的时间复杂度是O(log2n),随着n越大 二叉堆管理优先级队列的性能越好 2.使用链表实现的优先级队列在插入操作上时间复杂度较高为 O(n)但在删除最小元素和获取最小元素等操作上时间复杂度较低为 O(1)。这种实现方式适用于需要频繁删除最小元素但插入操作较少的场景
堆排序不稳定算法
堆排序堆排序不是稳定的因为堆化过程中会交换不相邻的元素
在堆数据调整过程不是相邻的元素调整的调整的元素一般是隔着2i1或者2i2个空间调整的所以这种相对元素先后顺序的稳定性是完全不可控滴堆排序不稳定举例
[8, 2, 5a, 5b,3],其中5a和5b都是元素5一个未排序的二叉堆进行堆排序8/ \2 5a/ \5b 3
排序最大堆结果(排序逻辑在上面堆排序里面)8/ \5b 5a/ \2 3
5b 跑到5a前面去了相对顺序变了所以堆排序非稳定的算法
