以下合併排序算法有什麼問題？

正如問題所述，我無法找到以下算法中問題的位置。它是mergesort的aux函數，即用於組合排序數組的一個函數。以下合併排序算法有什麼問題？

func Merge(toSort *[]int, p, q, r int) { 
    arr := *toSort 
    L := arr[p:q] 
    R := arr[q:r+1] 
    fmt.Println(L) 
    fmt.Println(R) 
    i := 0 
    j := 0 

    for index := p; index <= r; index++ { 
     if i >= len(L) { 
      arr[index] = R[j] 
      j += 1 
      continue 
     } else if j >= len(R) { 
      arr[index] = L[i] 
      i += 1 
      continue 
     } 

     if L[i] > R[j] { 
      fmt.Println("right smaller") 
      arr[index] = R[j] 
      j += 1 
      continue 
     } 
     if L[i] <= R[j] { 
      fmt.Println("left smaller") 
      arr[index] = L[i] 
      i += 1 
      continue 
     } 

    } 

}

對於arr := []int{1,7,14,15,44,65,79,2,3,6,55,70}它給作爲輸出[1 2 2 2 2 2 2 2 3 6 55 70]。

Golang Play link

中的JavaScript相當於該功能正常工作，但我不知道爲什麼它不在Go

工作謝謝

來源

2014-03-28 eAbi

Golang切片按引用傳遞。所以你不需要首先傳遞一個指針到函數中，但是你需要做需要採取L和R的明確副本，否則完全合併到不同的片中。您目前正在寫入相同的底層內存，從中獲得您的價值。

來源

2014-03-28 00:58:49 Evan

謝謝。我知道我在使用該語言時做錯了什麼，因爲js vesion工作得很好。雖然，據我所知，在js中它也是通過引用傳遞的。但我認爲array.splice函數會創建底層數組的副本。 – eAbi

類似的代碼L := arr[p:q]不不創建一個副本。我想你在arr的任務中覆蓋你的L和R部分。看看http://blog.golang.org/slices瞭解切片如何工作。（例如，你基本上從來不寫這樣的東西作爲toSort *[]int是[]int幾乎有點指針）

這似乎工作：http://play.golang.org/p/vPo2ZKXtI9

來源

2014-03-28 00:57:50 Volker

我有2個答案接受，這很難，好的，你也修改了我在操場上的節目，但他有很多較小的代表點。無論如何，謝謝！ – eAbi

你不需要所有的索引：切片已經是數組的視圖。這裏有一個完整的例子，使用純粹的切片操作：

package main 

import "fmt" 

// Merge takes two sorted, increasing slices of ints and 
// returns a slice combining them into a single sorted, increasing 
// slice. 
func Merge(a, b []int) []int { 
    res := make([]int, 0, len(a)+len(b)) 
    for len(a) > 0 || len(b) > 0 { 
     if len(b) == 0 || len(a) > 0 && a[0] <= b[0] { 
      res = append(res, a[0]) 
      a = a[1:] 
     } else { 
      res = append(res, b[0]) 
      b = b[1:] 
     } 
    } 
    return res 
} 

func main() { 
    a := []int{1, 2, 5, 6, 3, 4, 7, 9} 
    fmt.Println(Merge(a[:4], a[4:])) 
}

來源

2014-03-28 06:28:05

以下合併排序算法有什麼問題？

回答

相關問題