算法学习:归并排序
2017-07-14 本文已影响0人
DreamFish
-
**背景介绍: **
是创建在归并操作上的一种有效的排序算法,效率为O(n log n)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。 ----- 来自 wikipedia -
算法规则:
像快速排序一样,由于归并排序也是分治算法,因此可使用分治思想:
1.申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
2.设定两个指针,最初位置分别为两个已经排序序列的起始位置
3.比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
4.重复步骤3直到某一指针到达序列尾
5.将另一序列剩下的所有元素直接复制到合并序列尾 -
代码实现(Java版本)
public static int[] mergeSort(int[] nums, int low, int high) { int mid = (low + high) / 2; if (low < high) { // 左边 mergeSort(nums, low, mid); // 右边 mergeSort(nums, mid + 1, high); // 左右归并 merge(nums, low, mid, high); } return nums; } public static 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++]; } // 把新数组中的数覆盖nums数组 for (int k2 = 0; k2 < temp.length; k2++) { nums[k2 + low] = temp[k2]; } }