常见排序算法

1. 插入排序

package main

import (
	"fmt"
	"math/rand"
	"time"
)

func main() {
	r := rand.New(rand.NewSource(time.Now().UnixNano()))
	var list []int
	for i := 0; i < 100; i++ {
		list = append(list, r.Intn(100))
	}
	fmt.Println(insertSort(list))
}

//插入排序
func insertSort(arr []int) []int {
	if len(arr) < 1 {
		return arr
	}
	for i := 1; i < len(arr); i++ {
		tmp := arr[i]
		j := i - 1
		for j >= 0 && tmp < arr[j] {
			arr[j+1] = arr[j]
			j--
		}
	}
	return arr
}

2. 快速排序

package main

import (
	"fmt"
)

func main() {
	arr := []int{3, 7, 9, 8, 38, 93, 12, 222, 45, 93, 23, 84, 65, 2}
	quickSort(arr, 0, len(arr)-1)
	fmt.Println(arr)
}

//golang实现快速排序
func quickSort(arr []int, start int, end int) {
	if start < end { //不加 = ？
		i, j := start, end
		key := arr[(start+end)/2]
		for i <= j { //加 = ?
			for arr[i] < key {
				i++
			}
			for arr[j] > key {
				j--
			}
			if i <= j { //加 = ?
				arr[i], arr[j] = arr[j], arr[i]
				i++
				j--
			}
		}
		if start < j { //不加 = ?
			quickSort(arr, start, j)
		}
		if end > i {
			quickSort(arr, i, end)
		}
	}
}