Go データ構造とアルゴリズムの基本クイックソート

[[411577]]

この記事はWeChatの公開アカウント「Light City」から転載したもので、著者はlightcityです。この記事を転載する場合は、Guangcheng公式アカウントまでご連絡ください。

最近、アルゴリズムを再検討し、acwing を最初からフォローして、Go で実装する予定です。

今日の目標は、Go で書かれたクイックソートを学ぶことです。

acwingから学びました。

入力：

 3
 1 3 2

出力：

 1 2 3

ちょっとした考察:

1. ピボットを定義する

2. ピボットに従って間隔を分割する

3. 再帰的な部分問題

ピボットはランダムに選択できます。例: arr[l]、arr[r]など。

再帰時には 2 つのオプションがあります。1 つは j を取ることですが、無限ループを防ぐために pivot が arr[r] を取らないようにする必要があります。

この記事ではこれを実装します:

ピボット := arr[(l+r)>>1]
クイックソート(arr, l, j)
クイックソート(arr, j+1, r)

もう 1 つの方法は、i を取ることです。無限ループを防ぐために、pivot が arr[l] を取らないようにする必要があります。同時に、arr[(l+r)>>1] を使用することはできず、切り上げる必要があります。たとえば、arr[(l+r+1)>>1] です。

この記事ではこれを実装します:

ピボット := arr[(l+r+1)>>1]
クイックソートI(arr, l, i-1)
クイックソートI(arr, i, r)

最後に、囲碁の知識を追加します。

1. 入力

go で入力を処理するには、fmt.Scan を使用してアドレスを渡します。ここでは、後で直接再利用できる関数を実装しました。

 // DoBlackInputはスペース入力を配列として処理します
DoBlackInput関数(n int ) [] int {
 arr := make([] int , n)
 i := 0; i < n; i++ {
  fmt.Scan(&arr[i])
 }
リターン
}

2. 交換

2 つの要素をすばやく交換する方法。

 a, b = b, a

これにより、素早い交換が可能になります。

3.do...while{}

以下を使用できます:

のために{
    // 何かをする
    真の場合{
      壊す
    }
  }

4.i++ と ++i

++i と --i はサポートされていません。

最終的に、完全なコードは次のようになります。

パッケージメイン
 
 「fmt」をインポートする  
 
 // DoBlackInputはスペース入力を配列として処理します
DoBlackInput関数(n int ) [] int {
 arr := make([] int , n)
 i := 0; i < n; i++ {
  fmt.Scan(&arr[i])
 }
リターン
} 
 
 // クイックソートフェッチ j
 func quickSort(arr [] int , l int , r int ) {
 l >= r の場合 {
戻る 
 }
 ピボット := arr[(l+r)>>1]
 私 := l - 1
 j := r + 1
 i < j {に対して
のために{
   私は++
   arr[i] >= pivot の場合 {
    壊す
   }
  }
のために{
   j --  
   arr[j] <= pivot の場合 {
    壊す
   }
  }
  i < j {の場合
   arr[i]、arr[j] = arr[j]、arr[i]
  }
 }
 クイックソート(arr, l, j)
 クイックソート(arr, j+1, r)
 } 
 
 // クイックソートフェッチ i
 func quickSortI(arr [] int , l int , r int ) {
 l == r の場合
戻る 
 }
 ピボット := arr[(l+r+1)>>1]
 私 := l - 1
 j := r + 1
 i < j {に対して
のために{
   私は++
   arr[i] >= pivot の場合 {
    壊す
   }
  }
のために{
   じ --  
   arr[j] <= pivot の場合 {
    壊す
   }
  }
  i < j {の場合
   arr[i]、arr[j] = arr[j]、arr[i]
  }
 }
 クイックソートI(arr, l, i-1)
 クイックソートI(arr, i, r)
 }
関数main() {
 var n int  
 fmt.Scan(&n)
 arr := DoBlackInput(n)
 クイックソート(arr, 0, n-1)
 _の場合、v := 範囲 arr {
  fmt.Printf( "%d" , v)
 }
 }