go实现十大经典排序
排序代码：
package sort
import (
"math"
"math/rand"
"strconv"
"time"
)
func NewNums(length int, maxNum int) []int {
nums := make([]int, length)
rand.Seed(time.Now().UnixNano())
for i := 0; i < length; i++ {
nums[i] = rand.Intn(maxNum)
}
return nums
}
func BubbleSort(nums []int) []int {
if len(nums) < 2 {
return nums
}
for i:=0;i nums[j] {
nums[j-1], nums[j] = nums[j], nums[j-1]
}
}
}
return nums
}
func SelectSort(nums []int) []int {
if len(nums) < 2 {
return nums
}
for i:=0;i nums[j] {
nums[i], nums[j] = nums[j], nums[i]
}
}
}
return nums
}
func InsertSort(nums []int) []int {
if len(nums) < 2 {
return nums
}
for i:=1;i=0 && nums[j] > tmp {
nums[j+1] = nums[j]
j--
}
nums[j+1] = tmp
}
return nums
}
func HellSort(nums []int) []int {
if len(nums) < 2 {
return nums
}
for step:=len(nums)/2; step>0; step=step/2 {
for i:=step; i=0 && nums[j-step] > nums[j]; j=j-step {
nums[j-step], nums[j] = nums[j], nums[j-step]
}
}
}
return nums
}
func MergeSort(nums []int) []int {
if len(nums) < 2 {
return nums
}
merge := func(left []int, right []int) []int {
res := make([]int, len(left)+len(right))
var lIndex, rIndex, index int
for lIndex < len(left) && rIndex < len(right) {
if left[lIndex] < right[rIndex] {
res[index] = left[lIndex]
lIndex++
} else {
res[index] = right[rIndex]
rIndex++
}
index++
}
copy(res[index:], left[lIndex:])
copy(res[index+len(left)-lIndex:], right[rIndex:])
return res
}
var sort func(nums []int) []int
sort = func(nums []int) []int {
if len(nums) <= 1 {
return nums
}
mid := len(nums)/2
left := sort(nums[:mid])
right := sort(nums[mid:])
return merge(left, right)
}
return sort(nums)
}
func MergeSortII(nums []int) []int {
if len(nums) < 2 {
return nums
}
merge := func(left []int, right []int) []int {
res := make([]int, len(left)+len(right))
var lIndex, rIndex, index int
for lIndex < len(left) && rIndex < len(right) {
if left[lIndex] < right[rIndex] {
res[index] = left[lIndex]
lIndex++
} else {
res[index] = right[rIndex]
rIndex++
}
index++
}
copy(res[index:], left[lIndex:])
copy(res[index+len(left)-lIndex:], right[rIndex:])
return res
}
var sort_iter func(nums []int) []int
sort_iter = func(nums []int) []int {
i := 1 //子序列大小初始1
res := make([]int, 0)
// i控制每次划分的序列长度
for i < len(nums) {
// j根据i值执行具体的合并
j := 0
// 按顺序两两合并，j用来定位起始点
// 随着序列翻倍，每次两两合并的数组大小也翻倍
for j < len(nums) {
if j+2*i > len(nums) {
res = merge(nums[j:j+i], nums[j+i:])
} else {
res = merge(nums[j:j+i], nums[j+i:j+2*i])
}
// 通过index控制每次将合并的数据填入nums中
// 重填入的次数和合并及二叉树的高度相关
index := j
for _, v := range res {
nums[index] = v
index++
}
j = j + 2*i
}
i *= 2
}
return nums
}
return sort_iter(nums)
}
func QuickSort(nums []int) []int {
if len(nums) < 2 {
return nums
}
var quick func(left int, right int) []int
quick = func(left int, right int) []int {
if left > right {
return nil
}
i, j, pivot := left, right, nums[left]
for i < j {
for i= pivot {
j--
}
for i end {
return
}
if child < end && nums[child] <= nums[child+1] {
child++
}
if nums[root] > nums[child] {
return
}
nums[root], nums[child] = nums[child], nums[root]
root = child
}
}
end := len(nums)-1
for i:=end/2;i>=0;i-- {
heapify(nums, i, end)
}
for i:=end;i>0;i-- {
nums[0], nums[i] = nums[i], nums[0]
end--
heapify(nums, 0, end)
}
return nums
}
func SmallHeapSort(nums []int) []int {
if len(nums) < 2 {
return nums
}
// min heap
heapify := func(nums []int, root int, end int) {
for {
child := root*2 + 1
if child > end {
return
}
if child < end && nums[child] >= nums[child+1] {
child++
}
if nums[root] < nums[child] {
return
}
nums[root], nums[child] = nums[child], nums[root]
root = child
}
}
end := len(nums)-1
for i:=end/2;i>=0;i-- {
heapify(nums, i, end)
}
for i:=end;i>=0;i-- {
nums[0], nums[i] = nums[i], nums[0]
end--
heapify(nums, 0, end)
}
return nums
}
func TopKHeap(nums []int, k int) []int {
if len(nums) < 2 {
return nums
}
heapify := func(nums []int, root int, end int) {
for {
child := root*2 + 1
if child > end {
return
}
if child < end && nums[child] >= nums[child+1] {
child++
}
if nums[root] < nums[child] {
return
}
nums[root], nums[child] = nums[child], nums[root]
root = child
}
}
heap := nums[:k]
end := len(nums)-1
for i:=k/2;i>=0;i-- {
heapify(heap, i, k-1)
}
for i:=k;i<=end;i++ {
if nums[i] > heap[0] {
heap[0] = nums[i]
heapify(heap, 0, k-1)
}
}
for i:=k-1;i>=0;i-- {
heap[0], heap[i] = heap[i], heap[0]
k--
heapify(heap, 0, k)
}
return heap
}
func CountSort(nums []int) []int {
if len(nums) < 2 {
return nums
}
findMinMax := func(nums []int) (int, int) {
min, max := nums[0], nums[0]
for i:=0;i max {
max = nums[i]
}
if nums[i] < min {
min = nums[i]
}
}
return min, max
}
min, max := findMinMax(nums)
tmpNums := make([]int, max-min+1)
for i:=0;i max {
max = nums[i]
}
}
for i:=0;i max {
max = nums[i]
}
if nums[i] < min {
min = nums[i]
}
}
bucketSize := 5
bucketCap := (max-min)/bucketSize + 1
buckets := make([][]int, bucketCap)
for i:=0;i=0 && nums[j] > tmp {
nums[j+1] = nums[j]
j--
}
nums[j+1] = tmp
}
return nums
}(bucket)
for _, num := range bucket {
nums[index] = num
index++
}
}
return nums
}
单元测试代码：
package sort
import (
"log"
"sort"
"testing"
)
func TestBubbleSort(t *testing.T) {
nums := NewNums(10, 100)
log.Printf("origin nums: %v\n", nums)
numsCp := make([]int, len(nums))
copy(numsCp, nums)
sort.Ints(nums)
log.Printf("system sorted nums: %v\n", nums)
numsCp = BubbleSort(numsCp)
log.Printf("Bubble sorted nums: %v\n", numsCp)
for i:=0;i nums[j]
})
log.Printf("system sorted nums: %v\n", nums)
numsCp = SmallHeapSort(numsCp)
log.Printf("Heap sorted nums: %v\n", numsCp)
for i:=0;i nums[j]
})
log.Printf("system sorted nums: %v\n", nums)
numsCp = TopKHeap(numsCp, 10)
log.Printf("TopHeap sorted nums: %v\n", numsCp)
}
func TestCountSort(t *testing.T) {
nums := NewNums(10, 100)
log.Printf("origin nums: %v\n", nums)
numsCp := make([]int, len(nums))
copy(numsCp, nums)
sort.Slice(nums, func(i, j int) bool {
return nums[i] < nums[j]
})
log.Printf("system sorted nums: %v\n", nums)
numsCp = CountSort(numsCp)
log.Printf("Count sorted nums: %v\n", numsCp)
for i:=0;i