快速排序無法正常工作與交換功能沒有臨時變量

我一直在使用排序算法，我發現快速排序無法正確使用交換功能沒有臨時變量。我附上了下面的代碼。你可以在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)

來源

2017-10-13 va05

我的猜測是，有時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瞭解更多信息。

來源

2017-10-13 21:47:11

啊是的，就是這樣。我的Mac需要一些修復，所以在windows筆記本電腦上工作，這就是爲什麼我沒有得到這個警告。只是想確認swap（＆arr [i]，＆arr [j]）這段代碼在我== j時沒有正確啓動！馬丁？ – va05

我對algos有基本的經驗，但我想開始新鮮，你能推薦一些有趣的算法書籍嗎？ – va05

沒有臨時使用的經典交換使用XOR，它沒有溢出問題，但在嘗試交換相同元素時仍會失敗。 – Sulthan

當a和b指向同一元素時，您的交換功能將會中斷。首選版本的臨時變量更具可讀性，並且可以針對每種數據類型和每個值正確運行。

請注意，該函數在添加兩個較高值時也可能溢出，並且可能會在浮點值上完全中斷。

來源

2017-10-13 21:55:00 Sulthan

明白了，感謝您的幫助！ – va05

快速排序無法正常工作與交換功能沒有臨時變量

回答

相關問題