在没有临时变量的情况下，快速排序无法使用交换功能正常工作

Question

我一直在使用排序算法，我发现快速排序在没有临时变量的情况下不能与交换函数一起正常工作。我附上了下面的代码。您可以在 swift playground 中执行此代码，它是用 swift 编写的。 This is the link to execute this code online. 请让我知道解决此问题所需的任何其他信息。如果有人能解释一下，我将不胜感激。

注意 - 我已经评论了交换函数中的两种代码。一个没有临时变量，另一个是临时变量。此代码与带有临时变量的交换函数完美配合。

func swap(_ a:inout Int , _ b:inout Int)
{

   a = a+b
   b = a-b
   a = a-b

   /*

   let x = a
   a = b
   b = x
  */
 }

 func partition(_ arr : inout [Int], _ low : Int, _ high : Int )->Int
 {
    let pivot = arr[high]
    var i = low-1
    var j = low
    while(j<high)
    {
       if(arr[j]<=pivot)
       {
          i=i+1
          swap(&arr[i],&arr[j])
       }

       j = j+1
    }
    swap(&arr[i+1],&arr[high])
    return i+1
 }
 func quickSort(_ arr : inout [Int], _ low : Int, _ high : Int )
 {
    if low < high
    {
       let pi = partition(&arr,low,high)
       quickSort(&arr,low,pi-1)
       quickSort(&arr,pi+1,high)
    }
 }

 var arr = [11 , 40 ,50 ,20 ,30,77,90,77,14,8,897,765,34,0,89]
 print(arr)
 quickSort(&arr,0,arr.count-1)
 print(arr)

Answer 1

你的 "swap without temporary variable" 如果两者都无效参数指向相同的数组元素：

func swap(_ a:inout Int , _ b:inout Int) {
    a = a+b
    b = a-b
    a = a-b
}

var a = [5, 6, 7]
swap(&a[0], &a[0])
print(a) // [0, 6, 7]

请注意，即使传递相同数组的两个不同元素因为你的函数的 inout 参数是未定义的行为。在 Swift 4/Xcode 9 中，您会收到编译器警告：

var a = [5, 6, 7]
swap(&a[0], &a[1])
// warning: overlapping accesses to 'a', but modification requires exclusive access; consider copying to a local variable

和一个运行时错误：

Simultaneous accesses to 0x1005e4f00, but modification requires exclusive access.

这就是 swapAt() 方法的原因（以两个索引作为参数）已添加到 Swift 中的 MutableCollection 4.

有关详细信息，请参阅 SE-0176 Enforce Exclusive Access to Memory。

Answer 2

当 a 和 b 指向同一个元素时，您的交换功能将中断。更喜欢带有临时变量的版本，它更具可读性，并且适用于每种数据类型和每个值。

请注意，该函数在将两个高值相加时也可能会溢出，并且它可能会在浮点值上完全中断。

在没有临时变量的情况下，快速排序无法使用交换功能正常工作

Quick Sort isn't working correctly with swapping function without temporary variable

swap

quicksort

swift