Java 迭代实现归并排序

Java 迭代实现归并排序

文章目录

• 归并排序思想：
• 归并排序实现步骤
• • 1.数组拆分
  • 2.数组第一次合并
  • 3.数组循环合并
• 迭代实现归并排序完整代码

归并排序思想：

1. 大家都说将大问题化为小问题，这个是比较抽象的，其实如果小问题也不好解决，那我们化为小问题又有什么用呢
2. 举个例子 [5, 2, 1, 4, 3] ,我们可以把它分为小数组，但小数组有多小呢，这就是看小问题好不好解决，如分为 [5, 2, 1] 和 [4，3] ，那第一个数组排序也至少需要比较两次，那么这个小问题相对来说不是很好解决，如果看第二个数组，只需要比较一次就行了，可以发现如果一个数组有三个元素我们要比较两次，一个数组有两个元素我们只要比较一次就行了，很明显小问题最好是分为两个元素的数组
3. 分为小问题，解决了小问题又有什么用呢，如果给你两个数组 [1, 5] 和 [3，4]，因为两个数组内部是有序的，合并这两个数组是很简单的，只需要维护两个指针，每次只将两个指针指向的最小值，放入一个新数组，就可以合并成功了，只需要比较3次我们就需要排序完成了，比较过程是先比较1和3，放入1到第三个数组，将第一个指针往后移动指向5，比较5和3，放入3，移动第二个指针，指向4，比较5和4，放入4，最后放入由于第二个数组已经空了，将第一个数组剩下元素放入第三个数组
4. 合并和分解有个类似的东西，我们分解考虑过分为两个元素还是三个元素，合并的时候同样有这个问题，我们是一次合并三个数组还是合并两数组呢，和上面道理一样，合并三个数组每选出一个元素都需要比较两次，而合并两个数组每选出一个元素只需要比较一次
5. 从上面可以看到归并排序优化排序速度的方法有两个，分为小数组后比较次数非常少，还有就是各个小数组之间内部有序后合并也很快，只有建立在这两个的基础上，将大问题分为小问题再合并才会快

归并排序实现步骤 1.数组拆分

我们的上面的思路是将数组拆成多个2个元素的数组，然后让每个两个元素数组都有序，但我们没必要真正创建那么多个小数组，只要想象在一个数组中有很多分界线就行

public static void mergeSortUp(int[] nums) {
    int stepLength = 2;        
    for (int i = 0; i < nums.length; i += stepLength) {
        if (i + 1 < nums.length && nums[i] > nums[i + 1]) {
            tempValue = nums[i];
            nums[i] = nums[i+1];
            nums[i+1] = tempValue;
        }
    }
}

2.数组第一次合并

1. 可能看起来比较复杂，但只是因为我没想出怎么优雅的防止数组越界
2. 第一个for循环为了将数组分区，我们一开始以2个元素为一个数组，那么我们先合并的时候，就先合并两个数组，就是以4个元素为一个界限，所以for循环就是将数组进行分区
3. while循环是将两个小数组合成一个数组，因为我们不能改变原数组nums，则只能将元素全放到temp数组中
4. 两个数组合并为一个数组需要考虑三种情况，也就是两个数组都有元素没放到第三个数组上，左边的数组有元素没放到第三个数组上和右边的数组有元素没放到第三个数组，分为这三种情况合并就行了
5. 合并完成后我们就完成了第一次合并，将我们分的小数组个数减少了一半，下一步就是继续合并，直至只剩一个数组

public static void mergeSortUp(int[] nums) {
      for (int i = 0; i < nums.length; i += stepLength * 2) {
            int index = i, left = i, right = i + stepLength;
            while (left < i + stepLength || (right < i + stepLength * 2 && right < nums.length)) {
                if (left < i + stepLength && (right < i + stepLength * 2 && right < nums.length)) {
                    if (nums[left] < nums[right]) {
                        temp[index] = nums[left];
                        left++;
                    } else {
                        temp[index] = nums[right];
                        right++;
                    }
                } else if (left < i + stepLength && left < nums.length) {
                    temp[index] = nums[left];
                    left++;
                } else if (right < i + stepLength * 2 && right < nums.length){
                    temp[index] = nums[right];
                    right++;
                } else {
                    break;
                }
                index++;
            }
        }
}

3.数组循环合并

1. 可以看出在第二步变化上并不大，我们只需要先交换nums和temp两个数组的引用就行，因为nums是我们要的数组，而temp是排序的数组，在上一步合并后合并的数组是放在temp中的，所以我们要把temp给nums，而把nums给temp让它继续当中间数组，简单来说就是原来的nums数组我们不要了，让它当作中间容器
2. stepLength步长要翻倍，因为第二次我们要合并两个4个元素数组为8个元素数组，但是我们最开始待排序的数组可能没有8个，所以我们的while条件上是tempLength / 2 就是为了处理边界情况
3. 我们可以理解当stepLength代表有序数组的长度，如果它大于原数组长度，说明原数组已经排序成功

while (stepLength / 2 < nums.length) {
   for (int i = 0; i < nums.length; i += stepLength * 2) {
       int index = i, left = i, right = i + stepLength;
       while (left < i + stepLength || (right < i + stepLength * 2 && right < nums.length)) {
           if (left < i + stepLength && (right < i + stepLength * 2 && right < nums.length)) {
               if (nums[left] < nums[right]) {
                   temp[index] = nums[left];
                   left++;
               } else {
                   temp[index] = nums[right];
                   right++;
               }
           } else if (left < i + stepLength && left < nums.length) {
               temp[index] = nums[left];
               left++;
           } else if (right < i + stepLength * 2 && right < nums.length){
               temp[index] = nums[right];
               right++;
           } else {
               break;
           }
           index++;
       }
   }
   t = nums;
   nums = temp;
   temp = t;
   stepLength *= 2;
}

迭代实现归并排序完整代码

public class MergeSortUpDemo {
    public static void main(String[] args) {
        int[] nums = new int[]{5, 2, 1, 4, 3,2,5,6,1,2,5};
        int[] temp = new int[nums.length];
        mergeSortUp(nums);
        System.out.println(Arrays.toString(nums));
    }

    // temp为中间数组，长度和nums一样的空数组
    public static void mergeSortUp(int[] nums) {
        int[] temp = new int[nums.length];
        int[] t;
        int stepLength = 2;
        int tempValue = 0;
        // 以2个元素为单位排序
        for (int i = 0; i < nums.length; i += stepLength) {
            if (i + 1 < nums.length && nums[i] > nums[i + 1]) {
                tempValue = nums[i];
                nums[i] = nums[i+1];
                nums[i+1] = tempValue;
            }
        }

        // 将相邻的两个块合并
        while (stepLength / 2 < nums.length) {
            // i用来分区
            for (int i = 0; i < nums.length; i += stepLength * 2) {
                int index = i, left = i, right = i + stepLength;
                // 在区内才循环
                while (left < i + stepLength || (right < i + stepLength * 2 && right < nums.length)) {
                    if (left < i + stepLength && (right < i + stepLength * 2 && right < nums.length)) {
                        if (nums[left] < nums[right]) {
                            temp[index] = nums[left];
                            left++;
                        } else {
                            temp[index] = nums[right];
                            right++;
                        }
                    } else if (left < i + stepLength && left < nums.length) {
                        temp[index] = nums[left];
                        left++;
                    } else if (right < i + stepLength * 2 && right < nums.length){
                        temp[index] = nums[right];
                        right++;
                    } else {
                        break;
                    }
                    index++;
                }
            }
            // 合并一次后的数组为temp，将nums设为合并后的数组，然后在temp数组里面再次合并
            t = nums;
            nums = temp;
            temp = t;
            stepLength *= 2;
        }
    }
}