vlambda博客
学习文章列表

public static void main(String[] args) { System.out.println("quick sort"); int[] arr = new int[]{2, 4, 1, 5, 3}; mergeSort(arr, 0, arr.length - 1); for (int i : arr) { System.out.println("" + i); }
}
private static void mergeSort(int[] arr, int left, int right) { //1.left == right 就没必要了 if (left < right) { //2.找middle // / \ // / \ // / \ // \ / // \ / // \ / //整个算法递归有点类似上面这个图 //和快排的区别：快排是先partition，再进行递归；归并排序是先递归，最后合并 int middle = (left + right) / 2; mergeSort(arr, left, middle); mergeSort(arr, middle + 1, right); mergeArr(arr, left, middle, right); }}
/** * 这一步的目的其实是： * <p> * 将left--->middle组成的arr1 和 middle1--->right组成的arr2进行有序合并 */private static void mergeArr(int[] arr, int left, int middle, int right) { //1.首先构建 arr1 和 arr2 int arr1Length = middle - left + 1; int[] arr1 = new int[arr1Length]; int arr2Length = right - middle; int[] arr2 = new int[arr2Length]; for (int i = 0; i < arr1Length; i++) { arr1[i] = arr[left + i]; } for (int i = 0; i < arr2Length; i++) { arr2[i] = arr[middle + 1 + i]; } //上面整个逻辑都是为了构建两个arr，虽然代码多，但是逻辑不复杂 //涉及到一个点是边界条件，判断边界条件，我习惯用具体例子去带入。 //比如 [1,2,3,4,5]的数组 left = 0， right = 4, middle = 2 //所以那个+1，其实给arr1,arr2都行，只要构建的数据准确
 //2.合并两个有序数组 int i = 0; int j = 0; int k = left; while (i < arr1Length && j < arr2Length) { if (arr1[i] < arr2[j]) { arr[k] = arr1[i]; i ++; } else { arr[k] = arr2[j]; j ++; } k ++; } while (i < arr1Length) { arr[k] = arr1[i]; i++; k++; } while (j < arr2Length) { arr[k] = arr2[j]; j++; k++; } //合并两个数组实在是太常见的一个算法了，个人认为和数组元素交换一样基础，需要达到熟读背诵的情况。 //后续我会整理一些熟记的算法（flag），这些是所有算法的基础，必须要牢牢掌握的。 //其中需要理解的是 k == left，倒推一下倒也明白了，总不能k==0吧，这样每次递归的时候 //都在赋值相同元素了。}