Go中的快速排序實現

我正在嘗試實現快速排序算法，僅用於學習目的。Go中的快速排序實現

到目前爲止，我想出了下面的代碼：

package main 

import (
    "fmt" 
) 

var arr = []int{20, 43, 52, -1, 43, 29, 34} 

func main() { 
    fmt.Println("Unsorted: ", arr) 
    quick_sort(arr) 
    fmt.Println("Sorted: ", quick_sort(arr)) 
} 

func quick_sort(arr []int) []int { 
    var recurse func(left int, right int) 
    var swap func(i int, j int) 
    var partition func(left int, right int, pivot int) int 

    swap = func(i int, j int) { 
     var temp = arr[i] 
     arr[i] = arr[j] 
     arr[j] = temp 
    } 

    partition = func(left int, right int, pivot int) int { 
     v := arr[pivot] 
     right-- 
     swap(pivot, right) 

     for i := left; i < right; i++ { 
      // arr[i] doesn't seem to be updating here 
      fmt.Println(arr, left, right, i, arr[i], v) 
      if arr[i] <= v { 
       left++ 
       swap(i, left) 
      } 
     } 

     swap(left, right) 
     return left 
    } 

    recurse = func(left int, right int) { 
     if left < right { 
      pivot := (right + left)/2 
      pivot = partition(left, right, pivot) 
      recurse(left, pivot) 
      recurse(pivot+1, right) 
     } 
    } 

    recurse(0, len(arr)) 
    return arr 
}

這是我以前寫的JavaScript代碼的直接翻譯：

function quick_sort(arr) { 

    function partition(left, right, pivot) { 
    var v = arr[pivot]; 
    swap(pivot, --right); 

    for (var i = left; i < right; i ++) { 
     console.log(arr, left, right, i, arr[i], v); 
     if (arr[i] <= v) { 
     swap(i, left++); 
     } 
    } 
    swap(left, right); 

    return left; 
    } 

    function swap(i, j) { 
    var temp = arr[i]; 

    arr[i] = arr[j]; 
    arr[j] = temp; 
    } 

    function recurse(left, right) { 
    if (left < right) { 
     var pivot = ~~((left + right)/2) 
     pivot = partition(left, right, pivot); 
     recurse(left, pivot); 
     recurse(pivot + 1, right); 
    } 
    } 

    recurse(0, arr.length) 
    return arr; 
} 

var arr = [20, 43, 52, -1, 43, 29, 34]; 

console.log(quick_sort(arr));

它就像一個魅力JS，但不知何故，我不能讓它工作。出於某種原因，在我的分區功能中，在我的for循環中，即使i正在更改，arr[i]的值也保持不變。

我花了相當多的時間試圖找出我做錯了什麼，但我無法弄清楚。

有沒有人看到我失蹤的東西？

來源

2014-12-26 Spearfisher

您可以刪除交換功能，因爲交換是一個襯墊。例如，swap（i，left）可以用arr [i]，arr [left] = arr [left]，arr [i] – Dippo

left++應該是swap()功能後，爲後續

if arr[i] <= v {   
     swap(i, left) 
     left++ 
    }

修復程序後，輸出

Unsorted: [20 43 52 -1 43 29 34] 
Sorted: [-1 20 29 34 43 43 52]

來源

2014-12-26 18:43:56 Alper

Go中的快速排序實現

回答

相關問題