目标：将数组从低到高（或从高到低）排序
merge-sort是1945年由John von Neumann发明的，是一种有效的算法，具有最佳，最差和平均时间复杂度O(n log n)。
合并排序算法使用分而治之的方法，即将一个大问题分解为较小的问题并解决它们。我认为合并排序算法首先拆分，然后合并。
假设您需要按正确的顺序对n个数字的数组进行排序。合并排序算法的工作原理如下：
- 将数字放在未分类的堆中。
- 将堆分成两部分。现在，你有两堆未分类的数字。
- 保持分裂所产生的堆，直到你不能分裂为止。最后，你将有n堆，每堆中有一个数字。
- 开始通过顺序配对将它们合并在一起。在每次合并期间，将内容按排序顺序排列。这很容易，因为每个单独的堆已经排序。
一个例子
拆分
假设您将得到的数组ñ数字作为[2, 1, 5, 4, 9]。这是一堆未分类的。目标是不断分裂堆，直到你不能分裂为止。
首先，将阵列分成两半：[2, 1]和[5, 4, 9]。你能继续拆分吗？是的你可以！
专注于左桩。拆分[2, 1]成[2]和[1]。你能继续拆分吗？没时间检查另一堆。
拆分[5, 4, 9]成[5]和[4, 9]。不出所料，[5]不能再分裂，但[4, 9]可以拆分成[4]和[9]。
分裂过程以下列结束：[2] [1] [5] [4] [9]。请注意，每个桩只包含一个元素。
合并
现在您已经拆分了数组，您应该在对它们进行排序时将这些堆合并在一起。请记住，这个想法是解决许多小问题而不是大问题。对于每次合并迭代，您必须关注将一堆与另一堆合并。
鉴于桩[2] [1] [5] [4] [9]，第一遍将导致[1, 2]和[4, 5]和[9]。因为[9]是奇怪的，所以在这个过程中你不能将它与任何东西合并。
下一阶段将合并[1, 2]和[4, 5]在一起。这导致[1, 2, 4, 5]，与[9]再次离开，因为它是和大家格格不入。
你留下了只有两桩[1, 2, 4, 5]和[9]，终于得到了机会，合并，导致排序数组在[1, 2, 4, 5, 9]。
自上而下的实施
这是Swift中合并排序的样子：
func mergeSort(_ array: [Int]) -> [Int] {
guard array.count > 1 else { return array } // 1
let middleIndex = array.count / 2 // 2
let leftArray = mergeSort(Array(array[0..<middleIndex])) // 3
let rightArray = mergeSort(Array(array[middleIndex..<array.count])) // 4
return merge(leftPile: leftArray, rightPile: rightArray) // 5
}
有关代码如何工作的逐步说明：
-
如果数组为空或包含单个元素，则无法将其拆分为更小的部分。你必须只返回数组。
-
找到中间指数。
-
使用上一步中的中间索引，递归地分割数组的左侧。
-
此外，递归地分割数组的右侧。
-
最后，将所有值合并在一起，确保它始终排序。
这是合并算法：
func merge(leftPile: [Int], rightPile: [Int]) -> [Int] {
// 1
var leftIndex = 0
var rightIndex = 0
// 2
var orderedPile = [Int]()
// 3
while leftIndex < leftPile.count && rightIndex < rightPile.count {
if leftPile[leftIndex] < rightPile[rightIndex] {
orderedPile.append(leftPile[leftIndex])
leftIndex += 1
} else if leftPile[leftIndex] > rightPile[rightIndex] {
orderedPile.append(rightPile[rightIndex])
rightIndex += 1
} else {
orderedPile.append(leftPile[leftIndex])
leftIndex += 1
orderedPile.append(rightPile[rightIndex])
rightIndex += 1
}
}
// 4
while leftIndex < leftPile.count {
orderedPile.append(leftPile[leftIndex])
leftIndex += 1
}
while rightIndex < rightPile.count {
orderedPile.append(rightPile[rightIndex])
rightIndex += 1
}
return orderedPile
}
这种方法可能看起来很可怕，但它非常简单：
-
在合并时，您需要两个索引来跟踪两个阵列的进度。
-
这是合并的数组。它现在是空的，但是你将通过附加其他数组中的元素在后续步骤中构建它。
-
这个while循环将比较左侧和右侧的元素并将它们附加到
orderedPilewhile中，同时确保结果保持有序。 -
如果从以前的while循环控制退出，这意味着，无论是
leftPile或rightPile有其内容完全并入orderedPile。此时，您不再需要进行比较。只需追加另一个数组的其余内容，直到没有其他内容可以追加。
作为工作方式的一个例子merge()，假设我们有以下几堆：leftPile = [1, 7, 8]和rightPile = [3, 6, 9]。请注意，这些桩中的每一个都已单独排序 - 对于合并排序始终为真。这些在以下步骤中合并为一个更大的排序堆：
左侧索引（此处表示为l）指向左侧桩的第一个项目1。正确的指数r，指向3。因此，我们添加的第一项orderedPile是1。我们还将左侧索引移动l到下一个项目。
现在l指向7但r仍然在3。我们将最小的项添加到有序堆中，这样就可以了3。现在的情况是：
这个过程重复。在每一步中，我们选择无论从最小的项目leftPile或者rightPile添加项目到orderedPile：
现在，左堆中没有更多物品了。我们只需从正确的堆中添加剩余的项目，我们就完成了。合并后的桩是[ 1, 3, 6, 7, 8, 9 ]。
请注意，此算法非常简单：它从左向右移动通过两个桩，并在每个步骤选择最小的项目。这是有效的，因为我们保证每个桩都已经排序。
自下而上的实施
到目前为止你看到的合并排序算法的实现被称为“自上而下”的方法，因为它首先将数组拆分成更小的堆然后合并它们。排序数组（而不是链接列表）时，实际上可以跳过拆分步骤并立即开始合并各个数组元素。这被称为“自下而上”的方法。
是时候加强游戏了。:-)这是Swift中一个完整的自下而上的实现：
func mergeSortBottomUp<T>(_ a: [T], _ isOrderedBefore: (T, T) -> Bool) -> [T] {
let n = a.count
var z = [a, a] // 1
var d = 0
var width = 1
while width < n { // 2
var i = 0
while i < n { // 3
var j = i
var l = i
var r = i + width
let lmax = min(l + width, n)
let rmax = min(r + width, n)
while l < lmax && r < rmax { // 4
if isOrderedBefore(z[d][l], z[d][r]) {
z[1 - d][j] = z[d][l]
l += 1
} else {
z[1 - d][j] = z[d][r]
r += 1
}
j += 1
}
while l < lmax {
z[1 - d][j] = z[d][l]
j += 1
l += 1
}
while r < rmax {
z[1 - d][j] = z[d][r]
j += 1
r += 1
}
i += width*2
}
width *= 2
d = 1 - d // 5
}
return z[d]
}
它看起来比自上而下的版本更令人生畏，但请注意主体包含相同的三个while循环merge()。
值得注意的要点：
-
Merge-sort算法需要一个临时工作数组，因为您无法合并左右桩并同时覆盖其内容。因为为每个合并分配一个新数组是浪费，我们使用两个工作数组，我们将使用值
d0或1 在它们之间切换。数组z[d]用于读取，z[1 - d]用于写入。这称为双缓冲。 -
从概念上讲，自下而上的版本与自上而下的版本的工作方式相同。首先，它合并每个元素的小堆，然后它合并每个堆两个元素，然后每个堆成四个元素，依此类推。桩的大小由下式给出
width。最初，width是1但在每次循环迭代的结尾，我们乘以2，所以该外回路确定桩的尺寸被合并，和子阵列合并成为在每个步骤中大。 -
内环逐步穿过桩并将每对桩合并成一个较大的桩。结果写在由给定的数组中
z[1 - d]。 -
这与自上而下版本中的逻辑相同。主要区别在于我们使用双缓冲，因此读取
z[d]和写入值z[1 - d]。它还使用isOrderedBefore函数来比较元素而不仅仅是<，因此这种合并排序算法是通用的，您可以使用它来对任何类型的对象进行排序。 -
在这点上，尺寸的桩
width从阵列z[d]已经被合并到尺寸较大的桩width * 2在阵列z[1 - d]。在这里，我们交换活动数组，以便在下一步中我们将从我们刚刚创建的新堆中读取。
此函数是通用的，因此您可以使用它来对所需的任何类型进行排序，只要您提供适当的isOrderedBefore闭包来比较元素即可。
如何使用它的示例：
let array = [2, 1, 5, 4, 9]
mergeSortBottomUp(array, <) // [1, 2, 4, 5, 9]
性能
合并排序算法的速度取决于它需要排序的数组的大小。阵列越大，它需要做的工作就越多。
初始数组是否已经排序不会影响合并排序算法的速度，因为无论元素的初始顺序如何，您都将进行相同数量的拆分和比较。
因此，最佳，最差和平均情况的时间复杂度将始终为O（n log n）。
合并排序算法的一个缺点是它需要一个临时的“工作”数组，其大小与被排序的数组相同。它不是就地排序，不像快速排序。
合并排序算法的大多数实现产生稳定的排序。这意味着具有相同排序键的数组元素在排序后将保持相对于彼此的相同顺序。这对于数字或字符串等简单值并不重要，但在排序更复杂的对象时可能会出现问题。
网友评论