Swap整数算法

我正在学习算法，并尝试使用Swift交换到数组中的整数，我知道使用'swap'函数是有效的，但我尝试学习不同的方法。所以我尝试不同的方法，我不明白一两件事 - 我有200个整数数组，当我用这个方法：Swap整数算法

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) 
}

它只能运行198次1.3秒了吗？

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

来源

2016-06-08 Евгений Митько

你在两个例子中获得排序数组吗？它看起来像第二种方法删除其中一个值，并重复其他值，这意味着您的实现可能不正确。你会希望执行所提到的代码的次数更少，因为如果你复制数组中的每个值，它周围的谓词不会更经常。 – Glubus

经过进一步审查，我想我找到了问题。第一类将不得不多次移动该数字才能将其置于正确的位置。第二类同时移动多个号码，因为插入将推送数组中的其他号码。我用5个整数数组对它进行了测试。

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

注意如何3远离其正确位置，现在第一种方法排序一次后，数组现在看起来是这样

现在3处于正确的位置，但是4现在距离它的正确位置很远。它将不得不重复这个动作4次，直到它到达最终位置。接下来的交换看起来像这样

现在14在17，因为它应该前移动，但其仍远离其正确位置。所以它将不得不再次移动！

让我们看看第二种排序方法。

这里是什么样子的排序之前

和第一个交换后，它看起来像这样

现在你可以看到只有一个交换后，3 AND 4处于正确的位置。 3只移动了一次，正因为如此，它被移动到了4的前面，将4移到了正确的位置。

现在又一次交换...现在

你可以看到，它已经经过使用第二种方法2个互换正确排序，但它采取了第一种方法4个互换。只有当你有一个更大的阵列时，差异才会增长。

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

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

4是目前在索引0
17目前是在索引1目前
14是在索引2

如果我在第3插入E前...

3,4,17,14,3,20

现在删除以前的3 ...

3,4,17,14,20

4现在在索引1！
17现在在索引2！
14现在在索引3！

来源

2016-06-08 13:32:08

他正在使用一个插入并删除每次，这保持阵列数相同 – Scriptable

@Scriptable你是对的。我错了，我编辑了我的答案。我认为我发现问题 –

良好的调查，代码读取像它的完全相同的功能，但它不是。对我来说，它仍然没有多大意义，它是如何移动多个数字：（ – Scriptable

方法有很大不同。

第一个按照您的预期每次都会进行简单的交换array[j] < array[i]。

第二个，当array[j] < array[i]是真实的，它移动array[j]到i个位置和由一个位置移动所述阵列的其余部分。

话虽这么说，我有一点时间在我的手上，所以我决定写在斯威夫特3的算法（请注意，您如何避免使用temp）：

func selectionSort(_ array: [Int]) { 
    var array = array 
    for i in 0..<array.count { 
    for j in i+1..<array.count { 
     if array[j] < array[i] { 
     (array[j], array[i]) = (array[i], array[j]) 
     } 
    } 
    } 
    print(array) 
} 

func selectionSort2(_ array: [Int]) { 
    var array = array 
    for i in 0..<array.count { 
    for j in i+1..<array.count { 
     if array[j] < array[i] { 
     array.insert(array[j], at: i) 
     array.remove(at: j+1) 
     } 
    } 
    } 
    print(array) 
}

干杯！

来源

2016-07-01 11:01:54

Swap整数算法

回答

相关问题