package main
import (
"fmt"
"math/rand"
"time"
)
/* global varialbe for heapsort*/
var arrLen int
// 初始化 array with num
func initArray(num int) []int {
if num < 1 {
panic("num must bigger than 1")
}
arr := make([]int, num)
middle := num / 2
// fmt.Println("middle :", middle)
for i, _ := range arr {
arr[i] = i - middle
}
return arr
}
// 比较 sort 前后数组是否相同
func compare(arr1 []int, arr2 []int) bool {
if len(arr1) != len(arr2) {
return false
}
for i, _ := range arr1 {
if arr1[i] != arr2[i] {
return false
}
}
return true
}
// 测试 sort func 是否有效
func test_func(num int, sort func(arr []int) []int) {
r := rand.New(rand.NewSource(time.Now().UnixNano()))
src := initArray(num)
dest := make([]int, len(src))
perm := r.Perm(len(src))
for i, v := range perm {
dest[v] = src[i]
}
// fmt.Println(src)
// fmt.Println(dest)
result := sort(dest)
// fmt.Println(result)
if compare(src, result) {
fmt.Println("Test passed")
} else {
fmt.Println("Test failed")
}
}
// bubble sort
func bubbleSort(arr []int) []int {
length := len(arr)
for i := 0; i < length; i++ {
for j := 0; j < length-1-i; j++ {
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
}
}
}
return arr
}
// selection sort
func selectionSort(arr []int) []int {
length := len(arr)
for i := 0; i < length-1; i++ {
min := i
for j := i + 1; j < length; j++ {
if arr[min] > arr[j] {
min = j
}
}
arr[i], arr[min] = arr[min], arr[i]
}
return arr
}
// insertion sort
func insertionSort(arr []int) []int {
for i := range arr {
preIndex := i - 1
current := arr[i]
for preIndex >= 0 && arr[preIndex] > current {
arr[preIndex+1] = arr[preIndex]
preIndex -= 1
}
arr[preIndex+1] = current
}
return arr
}
// shellsort
func shellSort(arr []int) []int {
length := len(arr)
gap := 1
for gap < gap/3 {
gap = gap*3 + 1
}
for gap > 0 {
for i := gap; i < length; i++ {
temp := arr[i]
j := i - gap
for j >= 0 && arr[j] > temp {
arr[j+gap] = arr[j]
j -= gap
}
arr[j+gap] = temp
}
gap = gap / 3
}
return arr
}
// merge sort
func mergeSort(arr []int) []int {
length := len(arr)
if length < 2 {
return arr
}
middle := length / 2
left := arr[0:middle]
right := arr[middle:]
return merge(mergeSort(left), mergeSort(right))
}
func merge(left []int, right []int) []int {
var result []int
for len(left) != 0 && len(right) != 0 {
if left[0] <= right[0] {
result = append(result, left[0])
left = left[1:]
} else {
result = append(result, right[0])
right = right[1:]
}
}
for len(left) != 0 {
result = append(result, left[0])
left = left[1:]
}
for len(right) != 0 {
result = append(result, right[0])
right = right[1:]
}
return result
}
// quicksort
func quickSort(arr []int) []int {
return _quickSort(arr, 0, len(arr)-1)
}
func _quickSort(arr []int, left, right int) []int {
if left < right {
partitionIndex := partition(arr, left, right)
_quickSort(arr, left, partitionIndex-1)
_quickSort(arr, partitionIndex+1, right)
}
return arr
}
func partition(arr []int, left, right int) int {
pivot := left
index := pivot + 1
for i := index; i <= right; i++ {
if arr[i] < arr[pivot] {
swap(arr, i, index)
index += 1
}
}
swap(arr, pivot, index-1)
return index - 1
}
// heap sort
func heapSort(arr []int) []int {
arrLen := len(arr)
buildMaxHeap(arr, arrLen)
for i := arrLen - 1; i >= 0; i-- {
swap(arr, 0, i)
arrLen -= 1
heapify(arr, 0, arrLen)
}
return arr
}
func buildMaxHeap(arr []int, arrLen int) {
for i := arrLen / 2; i >= 0; i-- {
heapify(arr, i, arrLen)
}
}
func heapify(arr []int, i, arrLen int) {
left := 2*i + 1
right := 2*i + 2
largest := i
if left < arrLen && arr[left] > arr[largest] {
largest = left
}
if right < arrLen && arr[right] > arr[largest] {
largest = right
}
if largest != i {
swap(arr, i, largest)
heapify(arr, largest, arrLen)
}
}
func swap(arr []int, i, j int) {
arr[i], arr[j] = arr[j], arr[i]
}
func main() {
num := 5000
test_func(num, bubbleSort)
test_func(num, selectionSort)
test_func(num, insertionSort)
test_func(num, shellSort)
test_func(num, mergeSort)
test_func(num, quickSort)
test_func(num, heapSort)
}