10天光速入门go语言 常见排序算法

本文介绍了Go语言版经典的排序算法–快速排序、归并排序和堆排序。下面老男孩IT教育帮你解析一下。

排序算法

快速排序

func quickSort(data []int) {

if len(data) <= 1 {

return

}

base := data[0]

l, r := 0, len(data)-1

for i := 1; i <= r; {

if data[i] > base {

data[i], data[r] = data[r], data[i]

r--

} else {

data[i], data[l] = data[l], data[i]

l++

i++

}

}

quickSort(data[:l])

quickSort(data[l+1:])

}

func main() {

s := make([]int, 0, 16)

for i := 0; i < 16; i++ {

s = append(s, rand.Intn(100))

}

fmt.Println(s)

quickSort(s)

fmt.Println(s)

}

归并排序

func mergeSort(data []int) []int {

length := len(data)

if length <= 1 {

return data

}

num := length / 2

left := mergeSort(data[:num])

right := mergeSort(data[num:])

return merge(left, right)

}

func merge(left, right []int) (result []int) {

l, r := 0, 0

for l < len(left) && r < len(right) {

if left[l] < right[r] {

result = append(result, left[l])

l++

} else {

result = append(result, right[r])

r++

}

}

result = append(result, left[l:]...)

result = append(result, right[r:]...)

return

}

func main() {

s := make([]int, 0, 16)

for i := 0; i < 16; i++ {

s = append(s, rand.Intn(100))

}

fmt.Println(s)

s = mergeSort(s)

fmt.Println(s)

}

堆排序

Copy

func heapSort(array []int) {

m := len(array)

s := m / 2

for i := s; i > -1; i-- {

heap(array, i, m-1)

}

for i := m - 1; i > 0; i-- {

array[i], array[0] = array[0], array[i]

heap(array, 0, i-1)

}

}

func heap(array []int, i, end int) {

l := 2*i + 1

if l > end {

return

}

n := l

r := 2*i + 2

if r <= end && array[r] > array[l] {

n = r

}

if array[i] > array[n] {

return

}

array[n], array[i] = array[i], array[n]

heap(array, n, end)

}

func main() {

s := make([]int, 0, 16)

for i := 0; i < 16; i++ {

s = append(s, rand.Intn(100))

}

fmt.Println(s)

heapSort(s)

fmt.Println(s)

}