GO 語言常用排序

1. 冒泡排序（bubble sort）的基本思想：比較相鄰兩個 元素的關鍵字值，如果反序，則交換

func BubbleSort(arr []int) {	flag := false	//外層控制行	for i := 0; i < len(arr)-1; i++ {		//內層控制列		for j := 0; j < len(arr)-1-i; j++  {			//比較兩個相鄰元素			if arr[j] > arr[j+1] {				//交換資料				arr[j], arr[j+1] = arr[j+1], arr[j]				flag = true			}		}		//判斷資料是否是有序		if !flag {			return		} else {			flag = false		}	}}

 2. 快速排序

快速排序（quick sort）是一種磁區交換排序演算法.

它的基本思想：在資料序列中選擇一個值作為比較的基準值， 每趟從資料序列的兩端開始交替進行，將小于基準值的元素交換到序列前端，將大于基準值的元素交換到序列后端， 介于兩者之間的位置則成為基準值的最終位置，

func QuickSort(arr []int, left int, right int) {	//設定基準值	temp := arr[left]	index := left	i := left	j := right	for i <= j {		//從右面找到比基準值小的資料		for j >= index && arr[j] >= temp {			j--		}		//獲取基準值合適下標		if j > index {			arr[index] = arr[j]			index = j		}		//從左面找比基準值大的資料		for i <= index && arr[i] <= temp {			i++		}		//獲取基準值合適下標		if i <= index {			arr[index] = arr[i]			index = i		}	}	//將基準值放在合適位置	arr[index] = temp	//遞回呼叫 分步處理資料	if index-left > 1 {		QuickSort(arr, left, index-1)	}	if right-index > 1 {		QuickSort(arr, index+1, right)	}}

3. 直接選擇排序

直接選擇排序（straight select sort）的基本思想：第一趟從n個元素的資料序列中選出關鍵字最小（或最大）的元素并放到最前（或最后）位置，下一趟再從n-1個元素中選出最小（大）的元素并放到次前（后）位置，以此類推，經過n-1趟完成排序，

func SelectSort(arr []int) {	//外層控制行	for i := 0; i < len(arr); i++ {		//記錄最大值下標		index := 0		//內層控制列		//遍歷資料 查找最大值		for j := 1; j < len(arr)-i; j++ {			if arr[j] > arr[index] {				//記錄下標				index = j			}		}		//交換資料		arr[index], arr[len(arr)-1-i] = arr[len(arr)-1-i], arr[index]	}}

4.堆排序

堆排序（heap sort）是完全二叉樹的應用，它的基本思想：將資料序列“堆”成樹狀，每趟只遍歷樹中的一條路徑，

//初始化堆func HeapInit(arr []int) {	//將切片轉成二叉樹模型  實作大根堆	length := len(arr)	for i := length/2 - 1; i >= 0; i-- {		HeapSort(arr, i, length-1)	}	//根節點存盤最大值	for i := length - 1; i > 0; i-- {		//如果只剩下根節點和跟節點下的左子節點		if i == 1 && arr[0] <= arr[i] {			break		}		//將根節點和葉子節點資料交換		arr[0], arr[i] = arr[i], arr[0]		HeapSort(arr, 0, i-1)	}}//獲取堆中最大值  放在根節點func HeapSort(arr []int, startNode int, maxNode int) {	//最大值放在根節點	var max int	//定義做左子節點和右子節點	lChild := startNode*2 + 1	rChild := lChild + 1	//子節點超過比較范圍 跳出遞回	if lChild >= maxNode {		return	}	//左右比較  找到最大值	if rChild <= maxNode && arr[rChild] > arr[lChild] {		max = rChild	} else {		max = lChild	}	//和跟節點比較	if arr[max] <= arr[startNode] {		return	}	//交換資料	arr[startNode], arr[max] = arr[max], arr[startNode]	//遞回進行下次比較	HeapSort(arr, max, maxNode)}

5. 插入排序

func InsertSort(arr []int) {	for i := 1; i < len(arr); i++ {		//如果當前資料小于有序資料		if arr[i] < arr[i-1] {			j := i - 1			//獲取有效資料			temp := arr[i]			//一次比較有序資料			for j >= 0 && arr[j] > temp {				arr[j+1] = arr[j]				j--			}			arr[j+1] = temp		}	}}

 6. 希爾排序

希爾排序（shell sort）又稱縮小增量排序，它的基本思想：分組的直接插入排序，

func ShellSort(arr []int) {	//根據增量（len(arr)/2）每次變成上一次的1/2	for inc := len(arr) / 2; inc > 0; inc /= 2 {		for i := inc; i < len(arr); i++ {			temp := arr[i]			//根據增量從資料到0進行比較			for j := i - inc; j >= 0; j -= inc {				//滿足條件交換資料				if temp < arr[j] {					arr[j], arr[j+inc] = arr[j+inc], arr[j]				} else {					break				}			}		}	}}

 7. 二分查找 BinarySearch(資料，元素) 回傳值為下標

package mainimport "fmt"func BinarySearch(arr []int, num int) int {	//定義起始下標	start := 0	//定義結束下標	end := len(arr) - 1	//中間基準值	mid := (start + end) / 2	for i := 0; i < len(arr); i++ {		//基準值為查找值		if num == arr[mid] {			return mid		} else if num > arr[mid] {			//比基準值大  查找右側			start = mid + 1		} else {			//比基準值小  查找左側			end = mid - 1		}		//再次設定中間基準值位置		mid = (start + end) / 2	}	return -1}func main() {	//前提必須是 "有序資料"	arr := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}	num := 666	index := BinarySearch(arr, num)	fmt.Println(index)}

 8. 變相排序

變相排序  基于大量重復 在某一個范圍內

func main02() {	//亂數種子	rand.Seed(time.Now().UnixNano())	s := make([]int, 0)	for i := 0; i < 10000; i++ {		s = append(s, rand.Intn(1000)) //0-999	}	fmt.Println(s)	//統計資料集合中資料出現的次數	m := make(map[int]int)	for i := 0; i < len(s); i++ {		m[s[i]]++	}	//fmt.Println(m)	//排序	for i := 0; i < 1000; i++ {		for j := 0; j < m[i]; j++ {			fmt.Print(i, " ")		}	}}

標籤：Go

上一篇：go 語言實作堆疊原理

下一篇：go語言 二叉樹