Jimmy小站
小明也有大梦想 — 蒋明/铭小明学排序-归并排序算法
2016-03-23 / 数据结构算法 / 3116 次围观 / 0 次吐槽典型的排序算法--归并排序,按照自己理解的思路,做了一遍。关于排序算法的资源已经有很多,但是自己整理一遍还是有很大的收获的。主要是学习一种编程思想。
package net.jimmyme; import java.util.Arrays; public class MergeSort { public static void main(String[] args) { int[] source = {101,8,9,13,45,17,26,99,78,11,46}; int[] sourceAfterSort = new int[11]; sourceAfterSort = mergeSort(source); System.out.println(Arrays.toString(sourceAfterSort)); } public static int[] mergeSort(int[] source){ if (source.length <= 1) { return source; } int length = source.length; int middle = length/2; int[] sourceLeft = new int[middle]; int[] sourceRight = new int[length-middle]; // 将前半部分复制到sourceLeft System.arraycopy(source, 0, sourceLeft, 0, middle); // 将后半部分复制到sourceRight System.arraycopy(source, middle, sourceRight, 0, length-middle); // 左右递归 进行排序 int[] left = mergeSort(sourceLeft); int[] right = mergeSort(sourceRight); // 两边数组归并成一个数组,返回上一层递归 return merge(left, right); } public static int[] merge(int[] left, int[] right){ int leftLength = left.length; int rightLength = right.length; int[] source = new int[leftLength+rightLength]; int leftIndex = 0; int rightIndex = 0; int sourceIndex = 0; while (leftIndex < leftLength || rightIndex < rightLength) { // 如果左边数组已经遍历完成,而右边还有剩余元素 if(leftIndex == leftLength && rightIndex < rightLength){ for (int i = rightIndex; i < rightLength; i++) { source[sourceIndex] = right[rightIndex]; sourceIndex++; rightIndex++; } } // 如果右边数组已经遍历完成,而左边还有剩余元素 else if (rightIndex == rightLength && leftIndex < leftLength) { for (int i = leftIndex; i < leftLength; i++) { source[sourceIndex] = left[leftIndex]; sourceIndex++; leftIndex++; } } // 两边还有剩余元素 exists elements both sides else if (leftIndex < leftLength && rightIndex < rightLength) { // 哪边元素比较小就将该元素放入 source数组 if (left[leftIndex] <= right[rightIndex]) { source[sourceIndex] = left[leftIndex]; sourceIndex++; leftIndex++; } else { source[sourceIndex] = right[rightIndex]; sourceIndex++; rightIndex++; } } } // both sides have on elements return source; } }
- 上一篇:tomcat war包 部署到根目录
- 下一篇:小明学排序-快速排序
本月热文
Copyright © Jimmy小站 Allrights Reserved.备案号:桂ICP备 15005996
额 本文暂时没人评论 来添加一个吧
发表评论