首页天道酬勤归并排序算法Java,Java实现归并排序

归并排序算法Java,Java实现归并排序

admin 08-27 12:25 400次浏览

1.归并排序

归并操作(merge),也叫归并算法,指的是将两个顺序序列合并成一个顺序序列的方法。

如 设有数列{6,202,100,301,38,8,1}

初始状态:6,202,100,301,38,8,1

第一次归并后:{6,202},{100,301},{8,38},{1},比较次数:3;

第二次归并后:{6,100,202,301},{1,8,38},比较次数:4;

第三次归并后:{1,6,8,38,100,202,301},比较次数:4;

总的比较次数为:3+4+4=11;逆序数为14;



2.归并排序分析

为了对归并排序的运行时间进行划分,对递归层级和每个层级上完成多少工作方面进行思考,是很有帮助的。假设我们从包含n个元素的列表开始。以下是算法的步骤:

生成两个新数组,并将一半元素复制到每个数组中。排序两个数组。合并两个数组。

流程图如下:

第一步复制每个元素一次,因此它是线性的。第三步也复制每个元素一次,因此它也是线性的。现在我们需要弄清楚步骤2的复杂性。为了做到这一点,查看不同的计算图片会有帮助,它展示了递归的层数,如下图所示。

上图为归并排序的展示,它展示了递归的所有层级。

在顶层,我们有1个列表,其中包含n个元素。为了简单起见,我们假设n是2的幂。在下一层,有2个列表包含n/2个元素。然后是4个列表与n/4元素,以此类推,直到我们得到n个列表与1元素。

在每一层,我们共有n个元素。在下降的过程中,我们必须将数组分成两半,这在每一层上都需要与n成正比的时间。在回来的路上,我们必须合并n个元素,这也是线性的。

如果层数为h,算法的总工作量为O(nh)。那么有多少层呢?有两种方法可以考虑:

我们用多少步,可以将n减半直到1?或者,我们用多少步,可以将1加倍直到n?

第二个问题的另一种形式是“2的多少次方是n”?

2^h = n

对两边取以2为底的对数:

h = log2(n)

所以总时间是O(nlogn)。我没有纠结于对数的底,因为底不同的对数差别在于一个常数,所以所有的对数都是相同的增长级别。

O(nlogn)中的算法有时被称为“线性对数”的,但大多数人只是说n log n。

事实证明,O(nlogn)是通过元素比较的排序算法的理论下限。这意味着没有任何“比较排序”的增长级别比n log n好。



3.归并排序实现

实现代码:

/** * @Author Ragty * @Description 归并排序 * @Date 10:02 2019/6/12 **/ public void mergeSortInplace(List<T> list,Comparator<T> comparator) { List<T> sorted = mergeSort(list,comparator); list.clear(); list.addAll(sorted); } /** * @Author Ragty * @Description 分割list并排序 * @Date 10:10 2019/6/12 **/ public List<T> mergeSort(List<T> list,Comparator<T> comparator) { int size = list.size(); if (size <= 1) { return list; } //每次让list中的元素减半(递归) List<T> first = mergeSort(new LinkedList<T>(list.subList(0,size/2)),comparator); List<T> second = mergeSort(new LinkedList<T>(list.subList(size/2,size)),comparator); return merge(first,second,comparator); } /** * @Author Ragty * @Description 将两个排序好的list,合并为一个排序好的List(常数时间) * @Date 10:19 2019/6/12 **/ private List<T> merge(List<T> first,List<T> second, Comparator<T> comparator) { List<T> result = new LinkedList<T>(); int total = first.size()+second.size(); for(int i=0; i<total; i++) { List<T> winner = pickWinner(first,second,comparator); result.add(winner.remove(0)); } return result; } /** * @Author Ragty * @Description 返回第一个元素较小的list,任意列表为空,返回另一个list * @Date 10:52 2019/6/12 **/ private List<T> pickWinner(List<T> first,List<T> second,Comparator<T> comparator) { if (first.size() == 0) { return second; } if (second.size() == 0) { return first; } int res = comparator.compare(first.get(0),second.get(0)); if (res < 0) { return first; } if (res > 0) { return second; } return first; }

测试代码:

list = new ArrayList<Integer>(Arrays.asList(3, 5, 1, 4, 2));sorter.mergeSortInplace(list, comparator);System.out.println(list);

测试结果:

[1, 2, 3, 4, 5]
实时通信)的普及帖空格和标点符号?C#中的位操作小结
归并排序Java实现,归并排序 java java归并排序算法排序数组,归并排序
相关内容