排序 - 归并排序 [1]

野性酷女 2021-12-11 05:29 201阅读 0赞

实在是觉得自己很笨。

笨鸟就要先飞。

那就勤奋些，把自己想清楚的尽量也写清楚，下次复习容易些。-- 勉励下自己。加油！！！

归并排序。

算法的过程想必大部分人都知道，如果你是搜到这篇文章的，那我就用最详细的语句来描述清楚吧。

跟往常一样，傻文，专为没有耐性的人提供白痴级服务。

算法描述：

总体思想：divide and conquer

以待排序数组的中间元素为支点，将其分为左右两半部分；

递归拆分，分别对左右部分继续进行拆分，那么问题就出来了？什么时候拆分结束呢？

很简单：拆到不能拆的时候就结束了。

你会说：这不是废话吗？！

绝不是废话。

那什么时候就“拆到不能拆”了呢？

我问你：如果一个数组只有一个元素，我让你拆，你怎么拆？

是的！拆到只有一个元素的时候就算拆分结束。

我给你举个例子吧！

如果一个数组为 \{9,7,11\}

那么他的长度是 3, 最后一个元素的下标为2，中间元素是：0 + 2/ 2 (start + end / 2) = 1 , 也就是下标为1的地方是中点，那么我们以此拆分得到两个数组：

\{9, 7\}  和 \{11\}

此时，很明显没有结束。

我们还会将\{9, 7\} 拆分为 \{9\} 和 \{7\}.

那么我们最终得到的是 \{9\} \{7\} \{11\}。

（估计你会想：这么费劲干嘛？我直接将每个元素都当做一个数组不就得了！ >\_<  确实不是这样啊！我就有这个想法！看下面吧）

以上是“拆分”，拆分完了就要“合并”。

合并又如何工作呢？

在说合并部分之前，我要重新描述下上面的拆分过程。

（我次奥！你废话真多啊，刚说过一遍又说！别TMD浪费我的时间了行不行！我没有耐性了！）

别急，这是必须说的。

其实拆分是这么做的。

拆分是一个递归的过程。

说道递归，你一定不陌生吧。

对于这个问题来讲，递归的算法中较容易迷惑的地方是，算法在没有对左半部分完全拆分完成之前是不会对右半部分进行拆分的！

所以呢拆分其实是这么做的：

数组\{9, 7, 11\}

得到中间节点7.

得到左半部分\{9, 7\} （程序会记住这个中点元素是 7 ），在这儿记上个标记A。

再对左半部分继续进行拆分，此时中点是 0 + 1 / 2 = 0

故我们得到了进一步的左半部分\{9\}，在这儿记上标记 B。

再对这个进行拆分，发现长度已经是1了，故此部分拆分完毕，再回去到B的地方，去处理右半部分。

右半部分是\{7\}, 进行拆分，发现已经不能再拆分，右半部分也拆分完成。    \*\*\*\*\*\* 注意这个地方！因为现在你已经拆分出了小范围的左右两部分，故这个地方是一个“合并点”！

那么\{9， 7\} 这个较大范围的左半部分完成。

回到标记A，进行最外层的右半部分的拆分。

最外层右半部分是\{11\}. 好的，长度为1，不能再拆分了，最外层的右半部分拆分完毕。\*\*\*\*\*\* 注意这个地方！因为现在你已经拆分出整个的左右两部分，故这个地方是一个“合并点”！

至此整个拆分过程结束。

上面两次提到了“合并点“。

提到的时机都是当有右半部分完成拆分的时候。

故我们知道，顺序大概是这样：

拆分左面；

拆分右面：

合并点进行合并。

那么我们看第一个合并点如何进行合并呢？

第一个合并点：左半部分\{9\}， 右半部分\{7\}

我们会比较左半部分和右半部分的第一个元素，将较小的取出来放到另外的数组中。

\{7\}。

如果此时右半部分还有元素，我们则会再将右半部分的下一个元素同左半部分的第一个相比，取出较小的，放到另外的数组中，如此进行下去。

直到某个部分被处理完毕，那么肯定还有一个没处理完，怎么办呢？

直接追加到另外数组的后面，因为这些没处理的肯定是更大的元素。

今天就说这么多吧。

我今天主要是想说下这个”递归“来拆分，对我这样的菜鸟来说，这个不容易想通，所以我写一个拆分的程序出来吧。明天再写合并的部分。

public class Divide {
    
      public static int[] array = {19, 1,90, 2};
      
      public static void divide(int[] sortArr, int start, int end) {
        int len = end - start;
        if (len < 1) return;
        else {
          int mid = start + len / 2;
          printArr(sortArr, start, mid); // 打印本次拆分的左半部分
          printArr(sortArr, mid + 1, end); // 打印本次拆分的右半部分
          
          System.out.println("======================");
          divide(sortArr, start, mid); // 递归拆分左半部分
          divide(sortArr, mid + 1, end); // 递归拆分右半部分
        }
      }
    
      private  static void printArr(int[] arr, int start, int end) {
        for (int i = start; i <= end; i++) {
          System.out.print(arr[i] + "  ");
        }
        System.out.println("\r\n--------");
      }
      
      
      public static void main(String[] args) {
        divide(array, 0, array.length - 1);
      }
    }

本来想加个gif动画在这儿，发现传上去也不”动“！是不是我操作出错了？

Good night! 明天见。