数据结构----排序--分治法排序

分治法排序

1.分治法是什么

下面是百度百科的解释:
分治法可以通俗的解释为:把一片领土分解,分解为若干块小部分,然后一块块地占领征服,被分解的可以是不同的政治派别或是其他什么,然后让他们彼此异化。
分治法的精髓:
分--将问题分解为规模更小的子问题;
治--将这些规模更小的子问题逐个击破;
合--将已解决的子问题合并,最终得出“母”问题的解;

通俗理解来说,就是把一个东西拆分成一个个很小的组件,然后通过一定的方式组合起来。

2.分治法排序的思路

  1. 我们试想有两个个排序杂乱的数组,和两个已经排好序的数组分别合成一个排好序的数组。很显然,后者已经排好序的数组合并成一个数组更快点。
  2. 任何一个数组都可以拆分成只含一个元素的数组,而且只含一个元素的数组肯定是已经排好序了的
    那么,我们有一个构想:我们把一个杂乱无章的数组拆分成只含一个个元素的数组,然后再一步步合并起来,那样岂不是更好。这就是分治法排序

3.如何拆?

把一个数组从中分开,代码如下:

运行结果如下:

每一个华丽的分割线之间,就是一步分割的操作。
好,现在我们可以拆分了。那么怎么合并起来了?

4.如何合并?

合并,大概思路是这样:
假设有两个排序好了的数组arr1, arr2. 一个空数组arr.
从arr1里面拿第一个元素和arr2的第一个元素做比较,谁小就push到arr里面。
假设arr1[0]比较小,那么下一次就把arr1的第二个元素和arr2的第一个元素做比较,谁小就把谁push到arr中。
具体代码如下:

结果如下:

5.拆分+合并

合久必分,分久必合。
我们把分合整在一起,久可以完成了。

代码如下:

结果如下:

说实话,拆分和合并是最难的一步操作。单独的拆分和合并并不难,大家可以尝试一下。

评论 ( 0 )
最新评论
暂无评论

赶紧努力消灭 0 回复