分治算法 ———— 排序问题

2019-11-06 07:29:06

字体：大中小

来源：转载

供稿：网友

使用分制算法来解决排序问题，是一种比较高效的方法。这里是原理图这里写图片描述

在java中的代码是这样的，先看排序的代码，然后再看主函数

package com.li;public class MergeSort { public static void sort (double[] a, int begin, int end) { if((end - begin) >= 1) { int splitPoint = split(begin, end); sort(a, begin, splitPoint); sort(a, splitPoint + 1, end); join(a, begin, splitPoint, end); } } PRivate static int split(int begin, int end) { return ((begin + end) / 2); } private static void join(double[] a, int begin, int splitPoint, int end) { double[] temp; int intervalSize = (end - begin) + 1; temp = new double[intervalSize]; int nextLeft = begin; int nextRight = splitPoint + 1; int i = 0; while((nextLeft <= splitPoint) && (nextRight <= end)) { if(a[nextLeft] < a[nextRight]) { temp[i] = a[nextLeft]; i++; nextLeft++; } else { temp[i] = a[nextRight]; i++; nextRight++; } } while(nextLeft <= splitPoint) { temp[i] = a[nextLeft]; i++; nextLeft++; } while(nextRight <= end) { temp[i] = a[nextRight]; i++; nextRight++; } for(i=0; i<intervalSize; i++) { a[begin+i] = temp[i]; } }}

这是主函数

package com.li;public class MergeSortDemo { public static void main(String[] args) { // TODO 自动生成的方法存根 double[] b = {7.7, 5.5, 11, 3, 16, 4.4, 20, 14, 13, 42}; System.out.println("Before sorting"); int i; for(i=0; i<b.length; i++) { System.out.print(b[i] + " "); } System.out.println(); MergeSort.sort(b, 0, b.length-1); System.out.println("After sortint"); for(i=0; i<b.length; i++) { System.out.print(b[i] + " "); } }}

代码是依照图片中的样式进行编写的。就是对一个数组进行划分，不停的细分，把复杂问题简单化，进而解决问题。

上一篇：MFC中利用FindFile函数在文件夹路径下连续读取多个文件

下一篇：rtmp握手过程