常见的排序算法golang实现

常见排序算法包括冒泡、选择、插入、快排、归并、等，其中快排为官方包sort的默认排序方式，那我们先来看一下官方快拍实现方式吧：

func quickSort(data Interface, a, b, maxDepth int) {
	for b-a > 12 { // Use ShellSort for slices <= 12 elements
		if maxDepth == 0 {
			heapSort(data, a, b)
			return
		}
		maxDepth--
		mlo, mhi := doPivot(data, a, b)
		// Avoiding recursion on the larger subproblem guarantees
		// a stack depth of at most lg(b-a).
		if mlo-a < b-mhi {
			quickSort(data, a, mlo, maxDepth)
			a = mhi // i.e., quickSort(data, mhi, b)
		} else {
			quickSort(data, mhi, b, maxDepth)
			b = mlo // i.e., quickSort(data, a, mlo)
		}
	}
	if b-a > 1 {
		// Do ShellSort pass with gap 6
		// It could be written in this simplified form cause b-a <= 12
		for i := a + 6; i < b; i++ {
			if data.Less(i, i-6) {
				data.Swap(i, i-6)
			}
		}
		insertionSort(data, a, b)
	}
}

首先他区分了我们数组大小，如果小于12的话他会以6位分割点依次去对比前后两部分的大小，如果i小于i-6则交换(从小到达排序)这部分源码展示：

然后会使用插入排序的方式进行排序输出

如果数组长度大于12的话进行执行doPivot方法及下边方式进行数据分割迭代排序。

这里我们自己也实现了一些简单方式的排序代码：

主函数代码展示：

package main

import (
	"fmt"
	"math/rand"
	"sort"
	"sortmain/adjustheapSort"
	"time"
)

const (
	num = 10000        //测试数组长度
	rangeNum = 100000  //数组元素大小范围
)

func GenerateRand() []int {
	randSeed := rand.New(rand.NewSource(time.Now().Unix()+time.Now().UnixNano()))
	arr := make([]int,num)
	for i :=0;i<num;i++{
		arr[i] = randSeed.Intn(rangeNum)
	}
	return arr
}

func IsSame(slice1, slice2 []int) bool {
	if len(slice1) != len(slice2) {
		return false
	}
	if (slice1 == nil) != (slice2 ==nil) {
		return false
	}
	for i, num := range slice1{
		if num != slice2[i] {
			return false
		}
	}
	return true
}

func main() {
	arr := GenerateRand()
	org_arr := make([]int,num)
	copy(org_arr,arr)
	//冒泡排序
	//bubbleSort.BubbleSort(arr)
	//选择排序
	//selectSort.SelectSort(arr)
	//插入排序
	//insertSort.InsertSort(arr)
	//快排
	//quickSort.QuickSort(arr,0,len(arr)-1)
	//归并排序
	//mergeSort.MergeSort(arr,0,len(arr)-1)
	//堆排序
	adjustheapSort.HeapSort(arr)
	sort.Ints(org_arr)
	fmt.Println(arr[:15],org_arr[:15],IsSame(arr,org_arr))
}

冒泡排序代码：

package bubbleSort

//冒泡排序：
//通过对序列从后往前,依次比较相邻元素的排序码，若发现逆序则交换，使排序码较小的元素逐渐从后向前移动。


func BubbleSort(arr []int) {
	lenArr := len(arr)
	for i:=0;i<lenArr-1;i++ {
		for j:=0;j<lenArr-i-1;j++ {
			if (arr)[j] > (arr)[j+1] {
				(arr)[j],(arr)[j+1] = (arr)[j+1],(arr)[j]
			}
		}
	}
}

选择排序代码：

package selectSort

func SelectSort(arr []int)  {
	for i :=0;i<len(arr)-1;i++ {
		for j :=i+1; j<=len(arr)-1;j++{
			if (arr)[j] < (arr)[i] {
				(arr)[j],(arr)[i] = (arr)[i],(arr)[j]
			}
		}
	}
}

插入排序代码：

package insertSort

func InsertSort(arr []int)  {
	for i := 1;i<len(arr)-1;i++{
		for j:=i;j>0;j-- {
			if arr[j-1] >arr[j] {
				arr[j-1],arr[j] = arr[j],arr[j-1]
			}
		}
	}
}

快速排序代码：

package quickSort

//快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，
//其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，
//整个排序过程可以递归进行，以此达到整个数据变成有序序列。

func QuickSort(arr []int, first, last int) {
	flag := first
	left := first
	right := last
	if first >= last {
		return
	}
	// 将大于arr[flag]的都放在右边，小于的，都放在左边
	for first < last {
		// 如果flag从左边开始，那么是必须先从有右边开始比较，也就是先在右边找比flag小的
		for first < last {
			if arr[last] >= arr[flag] {
				last--
				continue
			}
			// 交换数据
			arr[last], arr[flag] = arr[flag], arr[last]
			flag = last
			break
		}
		for first < last {
			if arr[first] <= arr[flag] {
				first++
				continue
			}
			arr[first], arr[flag] = arr[flag], arr[first]
			flag = first
			break
		}
	}
	QuickSort(arr, left, flag-1)
	QuickSort(arr, flag+1, right)
}

归并排序代码：

package mergeSort

//合并
func Merge(arr []int, l, mid, r int) {
	// 分别复制左右子数组
	n1, n2 := mid-l+1, r-mid
	left, right := make([]int, n1), make([]int, n2)
	copy(left, arr[l:mid+1])
	copy(right, arr[mid+1:r+1])
	i, j := 0, 0
	k := l
	for; i < n1 && j < n2; k++ {
		if left[i] <= right[j] {
			arr[k] = left[i]
			i++
		} else {
			arr[k] = right[j]
			j++
		}
	}
	for; i < n1; i++ {
		arr[k] = left[i]
		k++
	}
	for; j < n2; j++ {
		arr[k] = right[j]
		k++
	}
}

//分治
func MergeSort(arr []int, l, r int) {
	if l < r {
		mid := (l + r - 1) / 2
		MergeSort(arr, l, mid)
		MergeSort(arr, mid+1, r)
		Merge(arr, l, mid, r)
	}
}

堆排序代码：

package adjustheapSort

//堆调整
func adjust_heap(arr []int, i, size int) {
	if i <= (size-2)/2 {
		//左右子节点
		l, r := 2*i+1, 2*i+2
		m := i
		if l < size && arr[l] > arr[m] {
			m = l
		}
		if r < size && arr[r] > arr[m] {
			m = r
		}
		if m != i {
			arr[m], arr[i] = arr[i], arr[m]
			adjust_heap(arr, m, size)
		}
	}
}

//建堆
func build_heap(arr []int) {
	size := len(arr)
	//从最后一个子节点开始向前调整
	for i := (size - 2) / 2; i >= 0; i-- {
		adjust_heap(arr, i, size)
	}
}

func HeapSort(arr []int) {
	size := len(arr)
	build_heap(arr)
	for i := size - 1; i > 0; i-- {
		//顶部arr[0]为当前最大值,调整到数组末尾
		arr[0], arr[i] = arr[i], arr[0]
		adjust_heap(arr, 0, i)
	}
}