クイックソート
分割統治法（再帰的に細かく問題を分割して解いて、再結集させて全体の答えとする）を使ったアルゴリズム
ピボット(pivot)と呼ばれる要素との大小比較により整列
選択されるピボットが各列の中央値であれば
アルゴリズム計算量はO(n・log2n)となる
ピボットが各列の最大値または最小値になっ た場合は，最悪O(n2)になってしまう
ピボットの決定方法が重要
Goで書くと以下
code:go
package sort
type Order string
const (
ASC Order = "ASC"
DESC Order = "DESC"
)
func QuickSort(arr []int, order Order) {
copy(arr, quickSort(arr, order))
}
func quickSort(arr []int, order Order) []int {
if len(arr) < 2 {
return arr
}
pivot := arr0
var left, right []int
if order == DESC {
for i := 1; i < len(arr); i++ {
if arri >= pivot {
left = append(left, arri)
} else {
right = append(right, arri)
}
}
} else {
for i := 1; i < len(arr); i++ {
if arri <= pivot {
left = append(left, arri)
} else {
right = append(right, arri)
}
}
}
var result []int
result = append(result, quickSort(left, order)...)
result = append(result, pivot)
result = append(result, quickSort(right, order)...)
return result
}