作者：嗳__霞骸 | 来源：互联网 | 2024-12-02 13:46
最近阅读了Nicholas在其JS算法博客中关于归并排序的实现（原文链接：Computer science in Javascript: Merge sort）。他在文章中展示了两种归并排序的方法：一种是非原地排序，另一种则是原地排序。我注意到，虽然两者在空间复杂度上看似相同，但它们之间的主要区别在于是否直接修改原数组。Nicholas指出，后者属于原地排序。然而，根据我之前的了解，原地排序的关键在于算法执行过程中使用的额外空间非常有限或几乎不使用额外空间。那么，在这个上下文中，原地排序的具体含义是什么？是否可以简单地认为，只要操作是在原数组上进行的，就可以称之为原地排序呢？
为了更好地理解这一点，下面我们将详细分析两段代码示例。
非原地排序实现归并排序的代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| function merge(left, right) {
var result = [],
il = 0,
ir = 0;
while (il if (left[il] result.push(left[il++]);
} else {
result.push(right[ir++]);
}
}
return result.concat(left.slice(il)).concat(right.slice(ir));
} |
而原地排序的实现则有所不同，具体代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| function mergeSort(items) {
if (items.length <2) {
return items;
}
var middle = Math.floor(items.length / 2),
left = items.slice(0, middle),
right = items.slice(middle),
params = merge(mergeSort(left), mergeSort(right));
// 将参数添加以替换数组中从0到最后一项的所有元素
params.unshift(0, items.length);
items.splice.apply(items, params);
return items;
} |
上述代码中的merge函数用于合并两个已排序的子数组。在非原地排序版本中，每次合并都会创建一个新的数组；而在原地排序版本中，通过使用splice方法直接修改原数组，从而实现了对原数组的直接操作，这正是原地排序的核心特征之一。
京公网安备 11010802041100号