霍爾的分區方案golang

快速排序與霍爾的分區霍爾的分區方案golang

// Hoare's partitioning scheme 
func PartitionHoare(arr []int, low, high int) int { 
    length := len(arr) 

    if length == 0 { 
     panic("Array size is 0") 
    } 

    pivot := arr[low] 
    i := low - 1 
    j := high + 1 

    for { 
     for { 
      j-- 
      if arr[j] > pivot { 
       break 
      } 
     } 

     for { 
      i++ 
      if arr[i] < pivot { 
       break 
      } 
     } 

     if i < j { 
      Swap(&arr, i, j) 
     } else { 
      return j 
     } 
    } 
} 

// Sort 
func SortHoare(arr []int, low, high int) { 
    if low < high { 
     p := PartitionHoare(arr, low, high) 
     SortHoare(arr, low, p) 
     SortHoare(arr, p+1, high) 
    } 
} 


// Swap i <--> j 
func Swap(arr *[]int, i, j int) { 
    (*arr)[i], (*arr)[j] = (*arr)[j], (*arr)[i] 
}

嘗試使用霍爾的分區來實現快速排序，但不能找出我做錯了。它是停留在一個無限循環，始終運行了內存

fatal error: runtime: out of memory

來源

2017-09-03 harsh_v

你爲什麼不看看這個實現。 ...也就是爲什麼你的內存不足是因爲你的遞歸函數SortHoare（）從來沒有它的轉義邏輯執行'低<高' https://github.com/gersakbogdan/golang-hackerrank/blob/master /quicksort.go SortHoare應該返回'low'和'high'，因爲這個值沒有被更新...... primary，因爲low和high沒有被引用傳遞...... SortHoare實際上並沒有做任何有用的事情。 – reticentroot

同時尋找我的位置和j做交換，您應該使用非嚴格的不平等。因此，而不是

 if arr[j] > pivot { 
      break 
     }

你應該有

 if arr[j] >= pivot { 
      break 
     }

與同爲我。取而代之的

 if arr[i] < pivot { 
      break 
     }

使用

 if arr[i] <= pivot { 
      break 
     }

而且我不知道這是否是有意還是無意的，但目前的算法降序排序。如果要按升序排序，請將i和j之間的比較交換。所以：

if arr[j] <= pivot { 
     break 
    }

和

if arr[i] >= pivot { 
     break 
    }

來源

2017-09-03 17:41:03 mateuszlo

非常感謝！就是這樣，等號'='運算符。非常感謝'ascending'的信息 –

霍爾的分區方案golang

回答

相關問題