交换整数算法

Question

我正在学习算法并尝试使用Swift交换到数组中的整数,我知道使用'swap'函数是有效的,但我尝试学习不同的方法.所以我尝试了不同的方法,我不明白一件事 - 我有一个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！