【合并两个已排序数组算法】Java/Go/Python/JS不同语言详解

说明

合并两个已排序的数组，在算法中经常遇到。实现方式多种多样，不同语言的实现也不尽相同。

策略：

策略一：双指针法，建立1个新数组，长度为两个数组的长度之和。从两个数组的第1项开始比较，将数值小的一项添加到新数组中，并将数值小的指针右移1位，继续两两比较，哪个小就添加到新数组中，并且右移小项的指针，直到遍历完其中一个数组，也就是把1个数组项全部添加到新数组时终止。最后再将剩余那个数组项追击到新数组即可。

策略二：将数组1和数组2先合在一起，然后当成一个新数组排序，这样的排序采用普通排序算法即可。因为两个都是已排序了的数组，在遍历时，可以从后面的数组开始，前面已排序数组无需再排。

策略三：将一个数组的长度扩展成两个数组之和，按照任意一种排序，将这个数组当成是已排序部分，遍历另外1个数组，将另外1个数组项逐个插入到这个数组中的位置中去。

实现过程

1. 新建1个空数组，长度为两个数组之和
2. 同时遍历数组1和数组2，比较数组1和数组2里的第一项，哪个小就追加到新数组中，小项的指针后移1位
3. 继续遍历，直到数组1或数组2完成遍历
4. 将另外1个数组剩余的内容追加到新数组

示意图

性能分析

平均时间复杂度：O(nlogn) 最佳时间复杂度：O(n) 最差时间复杂度：O(nlogn) 空间复杂度：O(n) 排序方式：In-place 稳定性：稳定

Java

public class MergeSortedArray {

  /**
   * @desc 移动指针，两两比较移动指针实现已排序数组合并
   */
  static int[] mergeSorted1(int[] one, int[] two) {
    // 新数组长度是两个数组长度之和
    int[] result = new int[one.length + two.length];
    // 数组1下标
    int i = 0;
    // 数组2下标
    int j = 0;
    // 新数组下标
    int k = 0;
    // 两个数组同时遍历，直到一个遍历完成
    while (i < one.length && j < two.length) {
      // 两两比较，把小的项追加到新数组中，同时移动小的那个数组指针
      if (one[i] < two[j]) {
        result[k++] = one[i++];
      } else {
        result[k++] = two[j++];
      }
    }

    // 复制数组1剩余的项目
    while (i < one.length) {
      result[k++] = one[i++];
    }
    // 复制数组2剩余的项目
    while (j < two.length) {
      result[k++] = two[j++];
    }
    return result;
  }

  /**
   * @desc 逐个取出1项插入到另外1个已排序数组中去，相当于选择最小项插入到已排序数组中
   *       从第1个数组里依次取出项插入到第2个数组合适位置中，这里采用List以便动态调整
   */
  static List<Integer> mergeSorted2(List<Integer> one, List<Integer> two) {
    int twoLen = two.size();
    for (int i = 0; i < one.size(); i++) {
      int j = 0;
      // 从第1个列表依次取出比较项，与第2个列表项自前往后逐个比较
      while (j < twoLen) {
        // 如果比较项小于第2个数组的某项，则插入到该项前面
        if (one.get(i) < two.get(j)) {
          // 第2个数组扩容1位，将最后1位复制添加到最后，并增加第2个数组长度
          two.add(two.get(twoLen - 1));
          twoLen++;
          int itemIndex = twoLen - 1 - 1;

          // 并将第2个数组自j位整体后移1位
          while (itemIndex > j) {
            two.set(itemIndex, two.get(itemIndex - 1));
            itemIndex--;
          }

          // 将比较项插入到第2个列表的j位置中
          two.set(j, one.get(i));
          break;
        } else {
          // 如果全部比较完成，数组2里面没有比它还大的，则添加到最后
          // 也可以一次性添加数组1里面全部剩余项，终止外部的循环
          if (j == twoLen - 1) {
            two.add(one.get(i));
            twoLen++;
            break;
          }
        }
        j++;
      }
    }
    // 第2个列表是合并了第1个数组的结果
    return two;
  }

  /**
   * @desc 先将两个数组合并，然后采用普通排序方式排序
   */
  static int[] mergeSorted3(int[] one, int[] two) {
    int oneLen = one.length;
    int twoLen = two.length;
    int[] output = new int[oneLen + twoLen];
    // 合并数组
    for (int i = 0; i < output.length; i++) {
      if (i < oneLen) {
        output[i] = one[i];
      } else {
        output[i] = two[i - oneLen];
      }
    }
    // 采用任意一种排序算法，这里采用插入算法
    // 前面已排序的无需再排，i从第2个数组开始
    for (int i = oneLen; i < output.length; i++) {
      int j = i;
      int current = output[j];
      // 用未排序的项逐个与左侧已排序项进行对比
      while (j-- > 0 && current < output[j]) {
        // 如果比较项小于已排序的项，需要将已排序项整体右移
        output[j + 1] = output[j];
      }
      // 将比较项插入到空出的位置
      output[j + 1] = current;
    }

    return output;
  }
复制代码

Python

"""
   * 双指针合并两个已排序数组。
   * 新建数组复制法，比较数组1和数组2的当前项，将小的添加到新数组中
   * @param:list one
   * @param:list two
"""


def merge_sorted1(one, two):
    # 数组1下标
    i = 0
    # 数组2下标
    j = 0
    # 结果数组下标
    k = 0

    one_len = len(one)
    two_len = len(two)
    result = [None] * (one_len + two_len)

    # 循环遍历两个数组，直到有1个数组里面的全部被比较过
    while i < one_len and j < two_len:
        # 逐个比较数组1和数组2的项，将小的项添加到新数组中，右移小项的指针再继续比较
        if one[i] < two[j]:
            result[k] = one[i]
            i += 1
        else:
            result[k] = two[j]
            j += 1
        k += 1

    # 如果数组1还有剩余的没有添加完，就全部追加到新数组最后
    while i < one_len:
        result[k] = one[i]
        k += 1
        i += 1

    # 如果数组2还有剩余的没有添加完，就全部追加到新数组最后
    while (j < two_len):
        result[k] = two[j]
        k += 1
        j += 1

    return result


"""
  * 合并两个已排序数组。
  * 插入法，从第一个数组里取出一项，自前往后逐个与第二个数组项进行比较，插入到第二个数组中
  * @param:list one
  * @param:lisit two
"""


def merge_sorted2(one, two):
    one_len = len(one)
    two_len = len(two)
    j = 0
    for i in range(one_len):
        for j in range(two_len):
            # 从数组1里拿出一项来与数组2逐个(自前往后)进行比较
            # 当遇到比它大的项时，则把它插入到数组2里该项的前面
            # 同时数组2下标与长度增加一位，跳出当前循环，进入下一轮比较
            if (one[i] < two[j]):
                two.insert(j, one[i])
                two_len += 1
                break
            else:
                # 如果全部比较完成，且数组2里面没有比它还大的，则添加到最后
                # 也可以一次性添加数组1里面全部剩余项，后面的就无需再比较了
                if j == two_len - 1:
                    two.append(one[i])
                    two_len += 1
                    break

    return two


"""
  * 合并两个已排序数组。
  * 合并数组再采取普通排序法
  * @param:list one
  * @param:list two
"""


def merge_sorted3(one, two):
    one_len = len(one)
    two_len = len(two)

    result = one + two
    # 从第2个数组开始遍历，采用插入排序
    for i in range(one_len, one_len + two_len):
        j = i - 1
        current = result[i]
        # 如果当前项小于已排序的项，则逐个右移1位
        while (j >= 0 and current < result[j]):
            result[j + 1] = result[j]
            j -= 1

        # 空出位置插入比较项
        result[j + 1] = current

    return result

Go

/**
 * @desc 双指针法，新建数组，两两比较移动指针实现已排序数组合并
 */
func mergeSorted1(one []int, two []int) []int {
	var oneLen = len(one)
	var twoLen = len(two)
	var result = make([]int, oneLen+twoLen)
	i := 0
	j := 0
	k := 0
	// 循环遍历两个数组，直到有1个数组项全部被比较过为止
	for i < oneLen && j < twoLen {
		// 从两个数组里逐个取出最小项来进行比较
		// 哪个更小就取出哪个添加到结果数组中去
		// 被取出最小项的数组下标右移1位，结果数组下标也同样移动1位
		// 继续进行两个数组的最小项比较，直到其中一个数组遍历完成
		if one[i] < two[j] {
			result[k] = one[i]
			k++
			i++
		} else {
			result[k] = two[j]
			k++
			j++
		}
	}

	// 如果第1个数组项有剩余，则依次复制剩余的第1个数组项
	for i < oneLen {
		result[k] = one[i]
		k++
		i++
	}

	// 如果第2个数组项有剩余，则依次复制剩余的第2个数组项
	for j < twoLen {
		result[k] = two[j]
		k++
		j++
	}

	return result
}

/**
 * @desc 逐个取出1项插入到另外1个已排序数组中去，相当于选择最小项插入到已排序数组中
 */
func mergeSorted2(one []int, two []int) []int {
	var oneLen = len(one)
	var twoLen = len(two)
	for i := 0; i < oneLen; i++ {
		for k, v := range two {
			// 如果比较项小于数组2的成员项，则插入到数组2中
			if one[i] < v {
				// 追加最后一位到数组2
				two = append(two, two[twoLen-1])
				twoLen++
				// 将数组2中k的位置整体右移1位
				copy(two[k+1:twoLen-1], two[k:twoLen-2])
				// 将比较项插入到空出的位置
				two[k] = one[i]
				break
			} else {
				// 如果全部比较完成，且数组2里面没有比它还大的，则添加到最后
				if k == twoLen-1 {
					two = append(two, one[i])
					twoLen++
					break
				}
			}
		}
	}
	return two
}

/**
 * @desc 先将两个数组合并，然后采用普通排序方式排序
 */
func mergeSorted3(one []int, two []int) []int {
	var oneLen = len(one)
	var twoLen = len(two)
	var result = make([]int, oneLen+twoLen)
	// 合并数组
	for i := range result {
		if i < oneLen {
			result[i] = one[i]
		} else {
			result[i] = two[i-oneLen]
		}
	}

	// 自第二个数组开始按照普通排序算法排序，这里采用冒泡排序
	// 前面数组已排序，从第二数组的第1项开始
	for i := oneLen; i < len(result); i++ {
		// 自后往前把当前项与前一项进行比较
		for j := i; j > 0; j-- {
			// 如果小于前面项则交换位置
			if result[j] < result[j-1] {
				result[j], result[j-1] = result[j-1], result[j]
			}
		}
	}

	return result
}

JS

/**
   * 双指针合并两个已排序数组。
   * 新建数组复制法，比较数组1和数组2的当前项，将小的添加到新数组中
   * @param {Arary} one
   * @param {Array} two
   */
  function mergeSorted1(one, two) {
    const result = []
    // 数组1下标
    let i = 0
    // 数组2下标
    let j = 0
    // 结果数组下标
    let k = 0

    const oneLen = one.length
    const twoLen = two.length
    // 循环遍历两个数组，直到有1个数组里面的全部被比较过
    while (i < oneLen && j < twoLen) {
      // 逐个比较数组1和数组2的项，将小的项添加到新数组中，移动指针再继续下个比较
      if (one[i] < two[j]) {
        result[k++] = one[i++]
      } else {
        result[k++] = two[j++]
      }
      // console.log(`while one[i] < two[j] ${i} < ${j}`, result)
    }

    console.log(one, i, oneLen)
    // 如果数组1还有剩余的没有添加完，就全部追加到新数组最后
    while (i < oneLen) {
      result[k++] = one[i++]
    }

    // 如果数组2还有剩余的没有添加完，就全部追加到新数组最后
    while (j < twoLen) {
      result[k++] = two[j++]
    }

    return result
  }

  /**
   * 合并两个已排序数组。
   * 插入法，从第一个数组里取出一项，自前往后逐个与第二个数组项进行比较，插入到第二个数组中
   * @param {Arary} one
   * @param {Array} two
   */
  function mergeSorted2(one, two) {
    const oneLen = one.length
    let twoLen = two.length
    let j = 0
    for (let i = 0; i < oneLen; i++) {
      for (; j < twoLen; j++) {
        // 从数组1里拿出一项来与数组2逐个(自前往后)进行比较
        // 当遇到比它大的项时，则把它插入到数组2里该项的前面
        // 同时数组2下标与长度增加一位，跳出当前循环，进入下一轮比较
        if (one[i] < two[j]) {
          console.log(`insert ${one[i]} into two at ${j}`)
          two.splice(j, 0, one[i])
          twoLen++
          break
        } else {
          // 如果全部比较完成，且数组2里面没有比它还大的，则添加到最后
          // 也可以一次性添加数组1里面全部剩余项，后面的就无需再比较了
          if (j === twoLen - 1) {
            two[j + 1] = one[i]
            twoLen++
            break
          }
        }
        // console.log(`for one[i] < two[j] ${i} vs ${j}`, one[i], two[j], one, two)
      }
    }
    return two
  }

  /**
   * 合并两个已排序数组。
   * 插入法，从第一个数组里取出一项，自后往前逐个与第二个数组项进行比较，插入到第二个数组中
   * @param {Arary} one
   * @param {Array} two
   */
  function mergeSorted3(one, two) {
    const oneLen = one.length
    let twoLen = two.length
    for (let i = 0; i < oneLen; i++) {
      let j = twoLen - 1
      // 拿数组1的一项作为比较项，逐个跟数组2里的项进行比较
      // 自后往前查找，直到找到比它小的位置，插入到该位置后面
      // 如果没有比它还小的，那么j无变化，就会插入到最后
      while (one[i] < two[j]) {
        j--
      }
      // 优化点: 如果j的位置无变化，说明比较项是数组2里最大的，则可以一次性复制数组1后面全部的项
      if (j === twoLen - 1) {
        const remained = one.slice(i, oneLen)
        console.log('concat remained:', remained)
        two = two.concat(remained)
        break
      }

      // 把比较项插入到第二个数组里比它小的位置后面
      console.log(`insert ${one[i]} into two at ${j + 1}`)
      two.splice(j + 1, 0, one[i])
      twoLen++

    }
    return two
  }

  /**
   * 合并两个已排序数组。
   * 新建数组push法，比较数组1和数组2的当前项，将小的添加到新数组中
   * @param {Arary} one
   * @param {Array} two
   */
  function mergeSorted4(one, two) {
    const result = []
    // 数组1下标
    let i = 0
    // 数组2下标
    let j = 0

    const oneLen = one.length
    const twoLen = two.length
    // 循环遍历两个数组，直到有1个数组里面的全部被比较过
    while (i < oneLen && j < twoLen) {
      // 逐个比较数组1和数组2的项，将小的项添加到新数组中，再继续下个比较
      if (one[i] < two[j]) {
        result.push(one[i])
        i++
      } else {
        result.push(two[j])
        j++
      }
      // console.log(`while one[i] < two[j] ${i} < ${j}`, result)
    }

    // 如果数组1还有剩余的没有添加完，就全部追加到新数组最后
    while (i < oneLen) {
      result.push(one[i])
      i++
    }

    // 如果数组2还有剩余的没有添加完，就全部追加到新数组最后
    while (j < twoLen) {
      result.push(two[j])
      j++
    }

    return result
  }

  /**
   * 合并两个已排序数组。
   * 合并数组再采取普通排序法
   * @param {Arary} one
   * @param {Array} two
   */
  function mergeSorted5(one, two) {
    const oneLen = one.length
    const twoLen = two.length

    const result = one.concat(two)
    // 从第2个数组开始遍历，采用插入排序
    for (let i = oneLen; i < oneLen + twoLen; i++) {
      let j = i
      const current = result[i]
      // 如果当前项小于已排序的项，则逐个右移1位
      while (j-- > 0 && current < result[j]) {
        result[j + 1] = result[j]
      }
      // 空出位置插入比较项
      result[j + 1] = current
    }

    return result
  }

链接

归并排序算法源码：https://github.com/microwind/algorithms/tree/master/sorts/mergesort
更多排序算法源码，请关注：https://github.com/microwind/algorithms