MergeSort 向右看齐 2022-06-02 04:18 102阅读 0赞 从上往下的归并排序:它与"从下往上"在排序上是反方向的。它基本包括3步: ① 分解 -- 将当前区间一分为二,即求分裂点 mid = (low + high)/2; ② 求解 -- 递归地对两个子区间a\[low...mid\] 和 a\[mid+1...high\]进行归并排序。递归的终结条件是子区间长度为1。 ③ 合并 -- 将已排序的两个子区间a\[low...mid\]和 a\[mid+1...high\]归并为一个有序的区间a\[low...high\]。 归并排序时间复杂度 归并排序的时间复杂度是O(N\*lgN)。 假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N),需要遍历多少次呢? 归并排序的形式就是一棵二叉树,它需要遍历的次数就是二叉树的深度,而根据完全二叉树的可以得出它的时间复杂度是O(N\*lgN)。 归并排序稳定性 归并排序是稳定的算法,它满足稳定算法的定义。 算法稳定性 -- 假设在数列中存在a\[i\]=a\[j\],若在排序之前,a\[i\]在a\[j\]前面;并且排序之后,a\[i\]仍然在a\[j\]前面。则这个排序算法是稳定的! ![151853346211212.jpg][] package sort; import java.util.ArrayList; /** * UpToDown * Created by long.chen on 2018/1/3. */ public class MergeSort<T extends Comparable<T>> { /** * @param array * @param start * @param middle * @param end */ public void mergn(T[] array, int start, int middle, int end) { ArrayList<T> arrayList = new ArrayList<>(end - start + 1);//存放合并数据 int i = start;//第一个区域的索引 int j = middle + 1;//第二个区域的索引 int k = 0;//arrayList 的区域索引 while (i <= middle && j <= end) { if (array[i].compareTo(array[j]) < 0) arrayList.add(k++, array[i++]); else arrayList.add(k++, array[j++]); } while (i <= middle) arrayList.add(k++, array[i++]); while (j <= end) arrayList.add(k++, array[j++]); for (i = 0; i < k; i++) array[start + i] = arrayList.get(i); arrayList = null; } public void mergeSortUptoDown(T[] array, int start, int end) { if (start == end || array == null) return; int middle = (start + end) / 2; mergeSortUptoDown(array, start, middle); mergeSortUptoDown(array, middle + 1, end); mergn(array, start, middle, end); } public static void main(String[] args) { MergeSort<Integer> mergeSort = new MergeSort<>(); Integer data[] = {1, 45, 5, 96, 26, 31, 5, 0, 5, 5}; mergeSort.mergeSortUptoDown(data, 0, data.length - 1); for (int i = 0; i < data.length; i++) System.out.printf("%d ", data[i]); } } [151853346211212.jpg]: /images/20220602/8dc79764ec144f89bf479c8367d6a3c7.png
相关 归并排序(MergeSort)(防止标题重复) 归并排序(MergeSort) 1 归并排序原理 分解成最小的记录块(长度为0或1),必须要排序,就是有序块 然后再归并 2 归并排序算法的实现 // 我会带着你远行/ 2022年12月27日 07:58/ 0 赞/ 150 阅读
相关 作业4-8-15:MapReduce编程—Merge和MergeSort 请编写2个MapReduce程序,分别实现功能: (1)合并HDFS文档并去掉重复的记录 (2)对HDFS文档中的数字进行排序,并输出序号和排序结果 请提交程序代码截 妖狐艹你老母/ 2022年11月17日 05:08/ 0 赞/ 107 阅读
相关 【模板】快速排序 与 归并排序——Template,QuickSort&MergeSort 快速排序 include<iostream> using namespace std; int n,a[1000001]; void qsor 秒速五厘米/ 2022年11月12日 02:51/ 0 赞/ 236 阅读
相关 JavaScript实现MergeSort归并排序算法(附完整源码) JavaScript实现MergeSort归并排序算法(附完整源码) Comparator.js完整源代码 Sort.js完整源代码 MergeSort 桃扇骨/ 2022年09月07日 09:55/ 0 赞/ 212 阅读
相关 MergeSort 从上往下的归并排序:它与"从下往上"在排序上是反方向的。它基本包括3步: ① 分解 -- 将当前区间一分为二,即求分裂点 mid = (low + high)/2; 向右看齐/ 2022年06月02日 04:18/ 0 赞/ 102 阅读
还没有评论,来说两句吧...