golang實作基本排序算法

package main

import (
	"fmt"
)

func main() {
	arr := []int{10, 9, 5, 7, 3, 5, 2, 9, 4, 6, 10}

	//res := SelectionSort(arr)// 選擇排序
	//res := InsertionSort(arr) // 插入排序
	//res := InsertionSortPro(arr) // 插入排序優化版
	//res := BubbleSort(arr) // 冒泡排序
	//res := MergeSort(arr) // 歸并排序
	//res := QuickSort(arr) // 快速排序
	fmt.Print(res)
}

//選擇排序
//思路：每次循環找出最小的數，跟數組第一個數交換順序，接下來在剩餘的數裡重複以上邏輯
func SelectionSort(arr [11]int) [11]int {
	length := len(arr)
	for i := 0; i < length; i++ {
		min := i
		for j := i + 1; j < length; j++ {
			//隻要找到比要比較的值小的值，就更新min的位置，循環一圈就能找到最小的值的位置
			if arr[j] < arr[min] {
				min = j
			}
		}
		//交換最小值與這一次循環最左邊值的位置
		arr[i], arr[min] = arr[min], arr[i]
	}
	return arr
}

//插入排序，類似撲克牌起牌，将未排序的資料插入到已排序的資料中
func InsertionSort(arr [11]int) [11]int {
	length := len(arr)
	for i := 1; i < length; i++ {
		for j := i; j > 0; j-- {
			//如果要比較的資料小于左邊的資料，則交換位置
			if arr[j-1] > arr[j] {
				arr[j], arr[j-1] = arr[j-1], arr[j]
			} else {
				break
			}
		}
	}
	return arr
}

//插入排序優化版，用指派代替交換操作
func InsertionSortPro(arr [11]int) [11]int {
	length := len(arr)
	for i := 1; i < length; i++ {
		temp := arr[i] //複制一份待比較的值
		var j int
		for j = i; j > 0; j-- {
			//如果左邊資料大于待比較待值，則将左邊資料指派給右邊的（往右挪一位），否則停止比較
			if arr[j-1] > temp {
				arr[j] = arr[j-1]
			} else {
				break
			}
		}
		arr[j] = temp //找到合适的位置了（左邊不再比該值大），将剛剛待比較的值指派給這個元素
	}
	return arr
}

//冒泡排序，每次和相鄰的元素比較，内層每循環一次會把最大的循環到最後
func BubbleSort(arr [11]int) [11]int {
	length := len(arr)
	for i := 0; i < length; i++ {
		//j < length -i -1 原因：每循環一次，最後一位數已排好，不用再比
		for j := 0; j < length-i-1; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
		}
	}
	return arr
}

//冒泡排序優化版，如果某次循環發現沒有需要交換的元素，則認為整個排序已完成
func BubbleSortPro(arr [11]int) [11]int {
	length := len(arr)
	for i := 0; i < length; i++ {
		over := false
		for j := 0; j < length-i-1; j++ {
			if arr[j] > arr[j+1] {
				over = true
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
		}
		if over == false {
			break
		}
	}
	return arr
}


//歸并排序
func MergeSort(arr []int) []int {
	length := len(arr)
	if length < 2 {
		return arr
	}
	i := length / 2
	left := MergeSort(arr[0:i])
	right := MergeSort(arr[i:])
	res := merge(left, right)
	return res
}

//合并數組
func merge(left, right []int) []int {
	result := make([]int, 0)
	m, n := 0, 0
	l, r := len(left), len(right)
	//比較兩個數組，誰小把元素值添加到結果集内
	for m < l && n < r {
		if left[m] > right[n] {
			result = append(result, right[n])
			n++
		} else {
			result = append(result, left[m])
			m++
		}
	}
	//如果有一個數組比完了，另一個數組還有元素的情況，則将剩餘元素添加到結果集内
	result = append(result, right[n:]...)
	result = append(result, left[m:]...)
	return result
}

//快排，以第一個值為标準，小于此值的放左邊，大于此值放右邊，将第一個值放中間，在分好的數組裡如此往複
func QuickSort(arr []int) []int {
	length := len(arr)
	if length <= 1 {
		return arr
	}
	p := 0
	res := quickSort(arr, p, length-1)
	return res
}

//遞歸方法
func quickSort(arr []int, p int, r int) []int {
	if p >= r {
		return arr
	}
	q := partition(arr, p, r)
	quickSort(arr, p, q-1)
	quickSort(arr, q+1, r)
	return arr
}

//排序并傳回pivot
func partition(arr []int, p int, r int) int {
	k := arr[p]
	j := p
	for i := p; i < r; i++ {
		if k > arr[i] {
			arr[i], arr[j] = arr[j], arr[i]
			j++
		}
	}
	arr[r], arr[j] = arr[j], arr[r]
	return j
}
      

　　

作者：郁冬

出處：http://www.cnblogs.com/lamp01/

本文版權歸作者和部落格園共有，如需轉載，請注明出處。