快速排序无法正常工作与交换功能没有临时变量

问题描述：

我一直在使用排序算法，我发现快速排序无法正确使用交换功能没有临时变量。我附上了下面的代码。你可以在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)

我的猜测是，有时a和b指向相同的元素。使用“智能”算法是许多程序员的陷阱。使用临时变量或甚至swift本地交换功能会更好。魔术交换有很多问题。浮点值会更危险。 – Sulthan

@Sulthan我不认为它的东西是随机的，因为在每次运行中输出都是一样的。我相信这与循环和交换功能有些相关。没有？ – va05

答

你的“交换没有临时变量”如果两个参数指向同一个数组元素不起作用：

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参数是未定义的行为。在斯威夫特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()方法（以两个指数作为参数）加入到MutableCollection in Swift 4.

请参阅SE-0176 Enforce Exclusive Access to Memory了解更多信息。

啊是的，就是这样。我的Mac需要一些修复，所以在windows笔记本电脑上工作，这就是为什么我没有得到这个警告。只是想确认swap（＆arr [i]，＆arr [j]）这段代码在我== j时没有正确启动！马丁？ – va05

我对algos有基本的经验，但我想开始新鲜，你能推荐一些有趣的算法书籍吗？ – va05

没有临时使用的经典交换使用XOR，它没有溢出问题，但在尝试交换相同元素时仍会失败。 – Sulthan

答

当a和b指向同一元素时，您的交换功能将会中断。首选版本的临时变量更具可读性，并且可以针对每种数据类型和每个值正确运行。

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

明白了，感谢您的帮助！ – va05

快速排序无法正常工作与交换功能没有临时变量

相关推荐