arrays - 交换整数算法

Question

我正在学习算法并尝试使用 Swift 交换数组中的整数，我知道使用“交换”函数很有效，但我尝试学习不同的方法。所以我尝试了不同的方法，但我不明白一件事 - 我有一个 200 个整数的数组，当我使用这种方法时:

func selectionSort(var array: [Int]) {
 print("Selection Sort")
 for i in 0..<array.count {
    for j in i+1..<array.count {
        if array[j] < array[i] {
            let temp = array[j] //runs 7282 times
            array[j] = array[i] // runs 7282 times
            array[i] = temp     // runs 7282 times
        }
    }
 }
 print(array)
}

它运行了 7 秒，交换代码运行了 7282(左右)次，但是当我使用它时:

func selectionSort(var array: [Int]) {
  print("Selection Sort")
  for i in 0..<array.count {
    for j in i+1..<array.count {
        if array[j] < array[i] {
            array.insert(array[j], atIndex: i)
            array.removeAtIndex(j+1)

        }
    }
  }
  print(array)
}

它在 1.3 秒内只运行了 198 次？

我不明白为什么运行次数如此不同？它只出现在选择排序中。如果我使用例如冒泡排序，运行次数就没有这样的差异。

Answer 1

经过进一步审查，我想我发现了问题所在。第一种排序必须多次移动数字才能将其放在正确的位置。第二种排序同时移动多个数字，因为插入操作会将数组中的其他数字向前推。我用 5 个整数的数组对其进行了测试。

这是第一个排序方法开始之前的调试器:

注意 3 离它的正确位置有多远，现在在第一个方法排序一次后，数组现在看起来像这样

现在 3 在正确的位置，但 4 现在离正确的位置很远。它必须重复此操作并移动 4 次，直到到达最终位置。下一个交换看起来像这样

现在 14 应该移动到 17 的前面，但它离正确的位置还很远。所以它必须再次移动!

---

我们来看第二种排序方式。

这是排序前的样子

在第一次交换后它看起来像这样

现在您可以看到，仅交换一次后，3 和 4 就处于正确的位置。 3 只移动了一次，因此，它被移动到 4 的前面，从而将 4 移动到正确的位置。

现在再交换一次...

现在您可以看到，在使用第二种方法进行 2 次交换后，它已经正确排序，但第一种方法进行了 4 次交换。只有当您拥有更大的阵列时，差异才会增加。

第二种方法通过每次插入时将数字推回一个索引来移动多个数字...

一个例子:4,17,14,3,20

• 4 当前位于索引 0
• 17 目前在索引 1
• 14 目前在索引 2

如果我在前面插入3...

3,4,17,14,3,20

现在删除前面的 3...

3,4,17,14,20

• 4 现在在索引 1 上!
• 17 现在在索引 2 处!
• 14 现在在索引 3 处!