首页 > 代码库 > 经典排序之归并排序
经典排序之归并排序
归并排序 与插入排序不同的是二个有序数组彼此的插入,而插入排序是一个数向有序里插入。
思想是吧一个数组分成若干个最小的有序数组,然后把这些小的有序数组,进行合并。
下面是代码:
public class MergeSort { public int[] sort(int[] nums, int low, int high){ int mid = (low + high) / 2; // System.out.println(low); if (low < high) { sort(nums, low, mid); sort(nums, mid + 1, high); merge(nums, low, mid, high); } System.out.println(Arrays.toString(nums)); return nums; } public void merge(int[] nums, int low, int mid, int high) { int[] temp = new int[high - low + 1]; int i = low; int j = mid + 1; int k = 0; while (i <= mid && j <= high) { if (nums[i] < nums[j]) { temp[k++] = nums[i++]; } else { temp[k++] = nums[j++]; } } while (i <= mid) { temp[k++] = nums[i++]; } while (j <= high) { temp[k++] = nums[j++]; } for (int k2 = 0; k2 < temp.length; k2++) { nums[k2 + low] = temp[k2]; } } public static void main(String[] args) { int nums[]={3,9,1,6,2,8,7,0,4,5}; MergeSort mergeSort=new MergeSort(); mergeSort.sort(nums, 0, nums.length-1); /*Random random=new Random(); int[] nums=new int[10000]; for(int i=0;i<nums.length;i++){ nums[i]=random.nextInt(10000); } MergeSort mergeSort=new MergeSort(); long startTime=System.currentTimeMillis(); mergeSort.sort(nums, 0, nums.length-1); long endTime=System.currentTimeMillis(); System.out.println("程序运行时间: "+(endTime-startTime)+"ms"); for(int i=0;i<nums.length;i++){ System.out.println(nums[i]); }*/ } }
输出序列:
[3, 9, 1, 6, 2, 8, 7, 0, 4, 5] [3, 9, 1, 6, 2, 8, 7, 0, 4, 5] [3, 9, 1, 6, 2, 8, 7, 0, 4, 5] [3, 9, 1, 6, 2, 8, 7, 0, 4, 5] [1, 3, 9, 6, 2, 8, 7, 0, 4, 5] [1, 3, 9, 6, 2, 8, 7, 0, 4, 5] [1, 3, 9, 6, 2, 8, 7, 0, 4, 5] [1, 3, 9, 2, 6, 8, 7, 0, 4, 5] [1, 2, 3, 6, 9, 8, 7, 0, 4, 5] [1, 2, 3, 6, 9, 8, 7, 0, 4, 5] [1, 2, 3, 6, 9, 8, 7, 0, 4, 5] [1, 2, 3, 6, 9, 7, 8, 0, 4, 5] [1, 2, 3, 6, 9, 7, 8, 0, 4, 5] [1, 2, 3, 6, 9, 0, 7, 8, 4, 5] [1, 2, 3, 6, 9, 0, 7, 8, 4, 5] [1, 2, 3, 6, 9, 0, 7, 8, 4, 5] [1, 2, 3, 6, 9, 0, 7, 8, 4, 5] [1, 2, 3, 6, 9, 0, 4, 5, 7, 8] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
十个数:
依次是前二个比并合并,前三个比并合并(因为合并的时候是mid+1),第四个和第五个比并合并,前三个和第四个和第五个比并合并,得到一个前五个的有序数组
后五个和前五个一样,只不过最后把前五个组成的有序数组和后五个组成的有序数组进行比较合并。
经典排序之归并排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。