东莞微网站建设免费优化网站

 数据结构加油站：

Comparison Sorting Visualization

并发设计模式

单线程归并排序

public class MergeSort {private final int[] arrayToSort; //要排序的数组private final int threshold;  //拆分的阈值，低于此阈值就不再进行拆分public MergeSort(final int[] arrayToSort, final int threshold) {this.arrayToSort = arrayToSort;this.threshold = threshold;}/*** 排序* @return*/public int[] mergeSort() {return mergeSort(arrayToSort, threshold);}public static int[] mergeSort(final int[] arrayToSort, int threshold) {//拆分后的数组长度小于阈值，直接进行排序if (arrayToSort.length < threshold) {//调用jdk提供的排序方法Arrays.sort(arrayToSort);return arrayToSort;}int midpoint = arrayToSort.length / 2;//对数组进行拆分int[] leftArray = Arrays.copyOfRange(arrayToSort, 0, midpoint);int[] rightArray = Arrays.copyOfRange(arrayToSort, midpoint, arrayToSort.length);//递归调用leftArray = mergeSort(leftArray, threshold);rightArray = mergeSort(rightArray, threshold);//合并排序结果return merge(leftArray, rightArray);}public static int[] merge(final int[] leftArray, final int[] rightArray) {//定义用于合并结果的数组int[] mergedArray = new int[leftArray.length + rightArray.length];int mergedArrayPos = 0;// 利用双指针进行两个数的比较int leftArrayPos = 0;int rightArrayPos = 0;while (leftArrayPos < leftArray.length && rightArrayPos < rightArray.length) {if (leftArray[leftArrayPos] <= rightArray[rightArrayPos]) {mergedArray[mergedArrayPos] = leftArray[leftArrayPos];leftArrayPos++;} else {mergedArray[mergedArrayPos] = rightArray[rightArrayPos];rightArrayPos++;}mergedArrayPos++;}while (leftArrayPos < leftArray.length) {mergedArray[mergedArrayPos] = leftArray[leftArrayPos];leftArrayPos++;mergedArrayPos++;}while (rightArrayPos < rightArray.length) {mergedArray[mergedArrayPos] = rightArray[rightArrayPos];rightArrayPos++;mergedArrayPos++;}return mergedArray;}

forkjoin排序

/*** 利用fork-join实现数组排序*/
public class MergeSortTask extends RecursiveAction {private final int threshold; //拆分的阈值，低于此阈值就不再进行拆分private int[] arrayToSort; //要排序的数组public MergeSortTask(final int[] arrayToSort, final int threshold) {this.arrayToSort = arrayToSort;this.threshold = threshold;}@Overrideprotected void compute() {//拆分后的数组长度小于阈值，直接进行排序if (arrayToSort.length <= threshold) {// 调用jdk提供的排序方法Arrays.sort(arrayToSort);return;}// 对数组进行拆分int midpoint = arrayToSort.length / 2;int[] leftArray = Arrays.copyOfRange(arrayToSort, 0, midpoint);int[] rightArray = Arrays.copyOfRange(arrayToSort, midpoint, arrayToSort.length);MergeSortTask leftTask = new MergeSortTask(leftArray, threshold);MergeSortTask rightTask = new MergeSortTask(rightArray, threshold);//调用任务,阻塞当前线程，直到所有子任务执行完成invokeAll(leftTask,rightTask);//提交任务
//		leftTask.fork();
//		rightTask.fork();
//		//合并结果
//		leftTask.join();
//		rightTask.join();// 合并排序结果arrayToSort = MergeSort.merge(leftTask.getSortedArray(), rightTask.getSortedArray());}public int[] getSortedArray() {return arrayToSort;}

随机生成一个数组的工具类

public class Utils {/*** 随机生成数组* @param size 数组的大小* @return*/public static int[] buildRandomIntArray(final int size) {int[] arrayToCalculateSumOf = new int[size];Random generator = new Random();for (int i = 0; i < arrayToCalculateSumOf.length; i++) {arrayToCalculateSumOf[i] = generator.nextInt(100000000);}return arrayToCalculateSumOf;}
}

单线程归并排序 & forkjoin排序  对比

public class ArrayToSortMain {public static void main(String[] args) {//生成测试数组  用于归并排序int[] arrayToSortByMergeSort = Utils.buildRandomIntArray(20000000);//生成测试数组  用于forkjoin排序int[] arrayToSortByForkJoin = Arrays.copyOf(arrayToSortByMergeSort, arrayToSortByMergeSort.length);//获取处理器数量int processors = Runtime.getRuntime().availableProcessors();MergeSort mergeSort = new MergeSort(arrayToSortByMergeSort, processors);long startTime = System.nanoTime();// 归并排序mergeSort.mergeSort();long duration = System.nanoTime()-startTime;System.out.println("单线程归并排序时间: "+(duration/(1000f*1000f))+"毫秒");//利用forkjoin排序MergeSortTask mergeSortTask = new MergeSortTask(arrayToSortByForkJoin, processors);//构建forkjoin线程池ForkJoinPool forkJoinPool = new ForkJoinPool(processors);startTime = System.nanoTime();//执行排序任务forkJoinPool.invoke(mergeSortTask);duration = System.nanoTime()-startTime;System.out.println("forkjoin排序时间: "+(duration/(1000f*1000f))+"毫秒");}
}

执行结果