归并排序 Merge sort

归并排序 Merge sort

归并排序相对于上两个的思路不同,并不是遍历单条序列找最大或最小的思路,最主要的是递归思想。假定有两个有序序列,将其合并为一个有序序列,所需要做的就是不断取出两个序列中最小的,并将其中较小的放在新的序列中,则最后合并得到的序列仍然是有序的序列,这就是所谓归并。

归并排序

  1. 要归并排序一个序列,可以先将其分成两部分,分别进行排序,得到的就是两个有序序列,再按照如下步骤进行。
  2. 有两个指针分别指向两个有序序列的首位。
  3. 比较两个指针对应的大小,小的放入新序列,并且此指针向后移,再重复比较。
int[] array = {3, 5, 7, 4, 2, 1, 6};
mergeSort(array, 0, array.length - 1);  // 指定排序范围
public static void mergeSort(int[] arr, int start, int end) {
    if (start == end - 1) {  // 如果起始与终点相邻,则将两者进行比对
        if (arr[start] > arr[end]) {
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
        }
    } else if (start < end - 1) {  // 如果排序子集大于三个,则需要进行递归操作
        int mid = (start + end) / 2;  // 选取中间点
        mergeSort(arr, start, mid);  // 前半部分进行排序
        mergeSort(arr, mid + 1, end);  // 后半部分进行排序
        merge(arr, start, mid, end);  // 将排好序的两部分进行合并
    }
    // 这里的情形是起始等于终点,即只有一个数,所以无需排序
}
public static void merge(int[] arr, int start, int mid, int end) {
    int[] newArr = new int[end - start + 1];  // 建立一个新数组用于放置新的合并结果
    int pos1 = start;  // 前半部分的指针
    int pos2 = mid + 1;  // 后半部分的指针
    int newArrPos = 0;  // 新数组的指针
    while (pos1 <= mid && pos2 <= end) {  //控制两个指针不超界
        if (arr[pos1] < arr[pos2]) {  // 取两个指针对应较小的数,放入新数组,对应指针后移
            newArr[newArrPos] = arr[pos1];
            pos1++;
        } else {
            newArr[newArrPos] = arr[pos2];
            pos2++;
        }
        newArrPos++;
    }
    // 当某半部分的指针已经到达末尾时,另半部分可能还有剩余,所以需要全部移入新的数组
    while (pos1 <= mid) {
        newArr[newArrPos] = arr[pos1];
        pos1++;
        newArrPos++;
    }
    while (pos2 <= end) {
        newArr[newArrPos] = arr[pos2];
        pos2++;
        newArrPos++;
    }
    System.arraycopy(newArr, 0, arr, start, newArr.length);  // 将新的合并好的数组替换原有的未合并部分
}

发表评论