【合并兩個已排序數(shù)組算法詳解】Java/Go/Python/JS不同語言實現(xiàn)
說明
合并兩個已排序的數(shù)組，這再算法中經(jīng)常遇到。
策略：
策略一：雙指針法，建立1個新數(shù)組，長度為兩個數(shù)組的長度之和。從兩個數(shù)組的第1項開始比較，將數(shù)值小的一項添加到新數(shù)組中，并將數(shù)值小的指針右移1位，繼續(xù)兩兩比較，哪個小就添加到新數(shù)組中，并且右移小項的指針，直到遍歷完其中一個數(shù)組，也就是把1個數(shù)組項全部添加到新數(shù)組時終止。最后再將剩余那個數(shù)組項追擊到新數(shù)組即可。
策略二：將數(shù)組1和數(shù)組2先合在一起，然后當(dāng)成一個新數(shù)組排序，這樣的排序采用普通排序算法即可。因為兩個都是已排序了的數(shù)組，在遍歷時，可以從后面的數(shù)組開始，前面已排序數(shù)組無需再排。
策略三：將一個數(shù)組的長度擴展成兩個數(shù)組之和，按照任意一種排序，將這個數(shù)組當(dāng)成是已排序部分，遍歷另外1個數(shù)組，將另外1個數(shù)組項逐個插入到這個數(shù)組中的位置中去。
實現(xiàn)過程
- 新建1個空數(shù)組，長度為兩個數(shù)組之和
- 同時遍歷數(shù)組1和數(shù)組2，比較數(shù)組1和數(shù)組2里的第一項，哪個小就追加到新數(shù)組中，小項的指針后移1位
- 繼續(xù)遍歷，直到數(shù)組1或數(shù)組2完成遍歷
- 將另外1個數(shù)組剩余的內(nèi)容追加到新數(shù)組
示意圖
merge-sorted1.png
merge-sorted2.gif
性能分析
平均時間復(fù)雜度：O(nlogn)
最佳時間復(fù)雜度：O(n)
最差時間復(fù)雜度：O(nlogn)
空間復(fù)雜度：O(n)
排序方式：In-place
穩(wěn)定性：穩(wěn)定
代碼
Java
public class MergeSortedArray {
/**
* @desc 移動指針，兩兩比較移動指針實現(xiàn)已排序數(shù)組合并
*/
static int[] mergeSorted1(int[] one, int[] two) {
// 新數(shù)組長度是兩個數(shù)組長度之和
int[] result = new int[one.length + two.length];
// 數(shù)組1下標(biāo)
int i = 0;
// 數(shù)組2下標(biāo)
int j = 0;
// 新數(shù)組下標(biāo)
int k = 0;
// 兩個數(shù)組同時遍歷，直到一個遍歷完成
while (i < one.length && j < two.length) {
// 兩兩比較，把小的項追加到新數(shù)組中，同時移動小的那個數(shù)組指針
if (one[i] < two[j]) {
result[k++] = one[i++];
} else {
result[k++] = two[j++];
}
}
// 復(fù)制數(shù)組1剩余的項目
while (i < one.length) {
result[k++] = one[i++];
}
// 復(fù)制數(shù)組2剩余的項目
while (j < two.length) {
result[k++] = two[j++];
}
return result;
}
/**
* @desc 逐個取出1項插入到另外1個已排序數(shù)組中去，相當(dāng)于選擇最小項插入到已排序數(shù)組中
* 從第1個數(shù)組里依次取出項插入到第2個數(shù)組合適位置中，這里采用List以便動態(tài)調(diào)整
*/
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個數(shù)組的某項，則插入到該項前面
if (one.get(i) < two.get(j)) {
// 第2個數(shù)組擴容1位，將最后1位復(fù)制添加到最后，并增加第2個數(shù)組長度
two.add(two.get(twoLen - 1));
twoLen++;
int itemIndex = twoLen - 1 - 1;
// 并將第2個數(shù)組自j位整體后移1位
while (itemIndex > j) {
two.set(itemIndex, two.get(itemIndex - 1));
itemIndex--;
}
// 將比較項插入到第2個列表的j位置中
two.set(j, one.get(i));
break;
} else {
// 如果全部比較完成，數(shù)組2里面沒有比它還大的，則添加到最后
// 也可以一次性添加數(shù)組1里面全部剩余項，終止外部的循環(huán)
if (j == twoLen - 1) {
two.add(one.get(i));
twoLen++;
break;
}
}
j++;
}
}
// 第2個列表是合并了第1個數(shù)組的結(jié)果
return two;
}
/**
* @desc 先將兩個數(shù)組合并，然后采用普通排序方式排序
*/
static int[] mergeSorted3(int[] one, int[] two) {
int oneLen = one.length;
int twoLen = two.length;
int[] output = new int[oneLen + twoLen];
// 合并數(shù)組
for (int i = 0; i < output.length; i++) {
if (i < oneLen) {
output[i] = one[i];
} else {
output[i] = two[i - oneLen];
}
}
// 采用任意一種排序算法，這里采用插入算法
// 前面已排序的無需再排，i從第2個數(shù)組開始
for (int i = oneLen; i < output.length; i++) {
int j = i;
int current = output[j];
// 用未排序的項逐個與左側(cè)已排序項進(jìn)行對比
while (j-- > 0 && current < output[j]) {
// 如果比較項小于已排序的項，需要將已排序項整體右移
output[j + 1] = output[j];
}
// 將比較項插入到空出的位置
output[j + 1] = current;
}
return output;
}
Python
"""
* 雙指針合并兩個已排序數(shù)組。
* 新建數(shù)組復(fù)制法，比較數(shù)組1和數(shù)組2的當(dāng)前項，將小的添加到新數(shù)組中
* @param:list one
* @param:list two
"""
def merge_sorted1(one, two):
# 數(shù)組1下標(biāo)
i = 0
# 數(shù)組2下標(biāo)
j = 0
# 結(jié)果數(shù)組下標(biāo)
k = 0
one_len = len(one)
two_len = len(two)
result = [None] * (one_len + two_len)
# 循環(huán)遍歷兩個數(shù)組，直到有1個數(shù)組里面的全部被比較過
while i < one_len and j < two_len:
# 逐個比較數(shù)組1和數(shù)組2的項，將小的項添加到新數(shù)組中，右移小項的指針再繼續(xù)比較
if one[i] < two[j]:
result[k] = one[i]
i += 1
else:
result[k] = two[j]
j += 1
k += 1
# 如果數(shù)組1還有剩余的沒有添加完，就全部追加到新數(shù)組最后
while i < one_len:
result[k] = one[i]
k += 1
i += 1
# 如果數(shù)組2還有剩余的沒有添加完，就全部追加到新數(shù)組最后
while (j < two_len):
result[k] = two[j]
k += 1
j += 1
return result
"""
* 合并兩個已排序數(shù)組。
* 插入法，從第一個數(shù)組里取出一項，自前往后逐個與第二個數(shù)組項進(jìn)行比較，插入到第二個數(shù)組中
* @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):
# 從數(shù)組1里拿出一項來與數(shù)組2逐個(自前往后)進(jìn)行比較
# 當(dāng)遇到比它大的項時，則把它插入到數(shù)組2里該項的前面
# 同時數(shù)組2下標(biāo)與長度增加一位，跳出當(dāng)前循環(huán)，進(jìn)入下一輪比較
if (one[i] < two[j]):
two.insert(j, one[i])
two_len += 1
break
else:
# 如果全部比較完成，且數(shù)組2里面沒有比它還大的，則添加到最后
# 也可以一次性添加數(shù)組1里面全部剩余項，后面的就無需再比較了
if j == two_len - 1:
two.append(one[i])
two_len += 1
break
return two
"""
* 合并兩個已排序數(shù)組。
* 合并數(shù)組再采取普通排序法
* @param:list one
* @param:list two
"""
def merge_sorted3(one, two):
one_len = len(one)
two_len = len(two)
result = one + two
# 從第2個數(shù)組開始遍歷，采用插入排序
for i in range(one_len, one_len + two_len):
j = i - 1
current = result[i]
# 如果當(dāng)前項小于已排序的項，則逐個右移1位
while (j >= 0 and current < result[j]):
result[j + 1] = result[j]
j -= 1
# 空出位置插入比較項
result[j + 1] = current
return result
Go
/**
* @desc 雙指針法，新建數(shù)組，兩兩比較移動指針實現(xiàn)已排序數(shù)組合并
*/
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
// 循環(huán)遍歷兩個數(shù)組，直到有1個數(shù)組項全部被比較過為止
for i < oneLen && j < twoLen {
// 從兩個數(shù)組里逐個取出最小項來進(jìn)行比較
// 哪個更小就取出哪個添加到結(jié)果數(shù)組中去
// 被取出最小項的數(shù)組下標(biāo)右移1位，結(jié)果數(shù)組下標(biāo)也同樣移動1位
// 繼續(xù)進(jìn)行兩個數(shù)組的最小項比較，直到其中一個數(shù)組遍歷完成
if one[i] < two[j] {
result[k] = one[i]
k++
i++
} else {
result[k] = two[j]
k++
j++
}
}
// 如果第1個數(shù)組項有剩余，則依次復(fù)制剩余的第1個數(shù)組項
for i < oneLen {
result[k] = one[i]
k++
i++
}
// 如果第2個數(shù)組項有剩余，則依次復(fù)制剩余的第2個數(shù)組項
for j < twoLen {
result[k] = two[j]
k++
j++
}
return result
}
/**
* @desc 逐個取出1項插入到另外1個已排序數(shù)組中去，相當(dāng)于選擇最小項插入到已排序數(shù)組中
*/
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 {
// 如果比較項小于數(shù)組2的成員項，則插入到數(shù)組2中
if one[i] < v {
// 追加最后一位到數(shù)組2
two = append(two, two[twoLen-1])
twoLen++
// 將數(shù)組2中k的位置整體右移1位
copy(two[k+1:twoLen-1], two[k:twoLen-2])
// 將比較項插入到空出的位置
two[k] = one[i]
break
} else {
// 如果全部比較完成，且數(shù)組2里面沒有比它還大的，則添加到最后
if k == twoLen-1 {
two = append(two, one[i])
twoLen++
break
}
}
}
}
return two
}
/**
* @desc 先將兩個數(shù)組合并，然后采用普通排序方式排序
*/
func mergeSorted3(one []int, two []int) []int {
var oneLen = len(one)
var twoLen = len(two)
var result = make([]int, oneLen+twoLen)
// 合并數(shù)組
for i := range result {
if i < oneLen {
result[i] = one[i]
} else {
result[i] = two[i-oneLen]
}
}
// 自第二個數(shù)組開始按照普通排序算法排序，這里采用冒泡排序
// 前面數(shù)組已排序，從第二數(shù)組的第1項開始
for i := oneLen; i < len(result); i++ {
// 自后往前把當(dāng)前項與前一項進(jìn)行比較
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
/**
* 雙指針合并兩個已排序數(shù)組。
* 新建數(shù)組復(fù)制法，比較數(shù)組1和數(shù)組2的當(dāng)前項，將小的添加到新數(shù)組中
* @param {Arary} one
* @param {Array} two
*/
function mergeSorted1(one, two) {
const result = []
// 數(shù)組1下標(biāo)
let i = 0
// 數(shù)組2下標(biāo)
let j = 0
// 結(jié)果數(shù)組下標(biāo)
let k = 0
const oneLen = one.length
const twoLen = two.length
// 循環(huán)遍歷兩個數(shù)組，直到有1個數(shù)組里面的全部被比較過
while (i < oneLen && j < twoLen) {
// 逐個比較數(shù)組1和數(shù)組2的項，將小的項添加到新數(shù)組中，移動指針再繼續(xù)下個比較
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)
// 如果數(shù)組1還有剩余的沒有添加完，就全部追加到新數(shù)組最后
while (i < oneLen) {
result[k++] = one[i++]
}
// 如果數(shù)組2還有剩余的沒有添加完，就全部追加到新數(shù)組最后
while (j < twoLen) {
result[k++] = two[j++]
}
return result
}
/**
* 合并兩個已排序數(shù)組。
* 插入法，從第一個數(shù)組里取出一項，自前往后逐個與第二個數(shù)組項進(jìn)行比較，插入到第二個數(shù)組中
* @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++) {
// 從數(shù)組1里拿出一項來與數(shù)組2逐個(自前往后)進(jìn)行比較
// 當(dāng)遇到比它大的項時，則把它插入到數(shù)組2里該項的前面
// 同時數(shù)組2下標(biāo)與長度增加一位，跳出當(dāng)前循環(huán)，進(jìn)入下一輪比較
if (one[i] < two[j]) {
console.log(`insert ${one[i]} into two at ${j}`)
two.splice(j, 0, one[i])
twoLen++
break
} else {
// 如果全部比較完成，且數(shù)組2里面沒有比它還大的，則添加到最后
// 也可以一次性添加數(shù)組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
}
/**
* 合并兩個已排序數(shù)組。
* 插入法，從第一個數(shù)組里取出一項，自后往前逐個與第二個數(shù)組項進(jìn)行比較，插入到第二個數(shù)組中
* @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
// 拿數(shù)組1的一項作為比較項，逐個跟數(shù)組2里的項進(jìn)行比較
// 自后往前查找，直到找到比它小的位置，插入到該位置后面
// 如果沒有比它還小的，那么j無變化，就會插入到最后
while (one[i] < two[j]) {
j--
}
// 優(yōu)化點: 如果j的位置無變化，說明比較項是數(shù)組2里最大的，則可以一次性復(fù)制數(shù)組1后面全部的項
if (j === twoLen - 1) {
const remained = one.slice(i, oneLen)
console.log('concat remained:', remained)
two = two.concat(remained)
break
}
// 把比較項插入到第二個數(shù)組里比它小的位置后面
console.log(`insert ${one[i]} into two at ${j + 1}`)
two.splice(j + 1, 0, one[i])
twoLen++
}
return two
}
/**
* 合并兩個已排序數(shù)組。
* 新建數(shù)組push法，比較數(shù)組1和數(shù)組2的當(dāng)前項，將小的添加到新數(shù)組中
* @param {Arary} one
* @param {Array} two
*/
function mergeSorted4(one, two) {
const result = []
// 數(shù)組1下標(biāo)
let i = 0
// 數(shù)組2下標(biāo)
let j = 0
const oneLen = one.length
const twoLen = two.length
// 循環(huán)遍歷兩個數(shù)組，直到有1個數(shù)組里面的全部被比較過
while (i < oneLen && j < twoLen) {
// 逐個比較數(shù)組1和數(shù)組2的項，將小的項添加到新數(shù)組中，再繼續(xù)下個比較
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)
}
// 如果數(shù)組1還有剩余的沒有添加完，就全部追加到新數(shù)組最后
while (i < oneLen) {
result.push(one[i])
i++
}
// 如果數(shù)組2還有剩余的沒有添加完，就全部追加到新數(shù)組最后
while (j < twoLen) {
result.push(two[j])
j++
}
return result
}
/**
* 合并兩個已排序數(shù)組。
* 合并數(shù)組再采取普通排序法
* @param {Arary} one
* @param {Array} two
*/
function mergeSorted5(one, two) {
const oneLen = one.length
const twoLen = two.length
const result = one.concat(two)
// 從第2個數(shù)組開始遍歷，采用插入排序
for (let i = oneLen; i < oneLen + twoLen; i++) {
let j = i
const current = result[i]
// 如果當(dāng)前項小于已排序的項，則逐個右移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
