Golang实现常见排序算法

package sort

// 1、冒泡排序
func BubbleSort(arr []int) {
	n := len(arr)
	flag := true
	for i := 0; i < n && flag; i++ {
		flag = false
		for j := 0; j < n-i-1; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
				flag = true
			}
		}
	}
}

// 2、选择排序
func SelectSort(arr []int) {
	n := len(arr)
	for i := 0; i < n; i++ {
		minIndex := i
		for j := i+1; j < n; j++ {
			if arr[j] < arr[minIndex] {
				minIndex = j
			}
		}
		if minIndex != i {
			arr[minIndex], arr[i] = arr[i], arr[minIndex]
		}
	}
}

// 3、插入排序
func InsertSort(arr []int) {
	n := len(arr)
	for i := 0; i < n-1; i++ {
		if arr[i+1] < arr[i] {
			for j := i+1; j > 0 && arr[j] < arr[j-1]; j-- {
				arr[j], arr[j-1] = arr[j-1], arr[j]
			}
		}
	}
}

// 4、希尔排序
func ShellSort(arr []int) {
	n := len(arr)
	increment := n
	for true {
		increment = increment/3 + 1
		for i := 0; i < increment; i++ {
			for j := i + increment; j < n; j+=increment {
				for k := j; k > i && arr[j] < arr[j-increment]; k-=increment {
					arr[k], arr[k-increment] = arr[k-increment], arr[k]
				}
			}
		}
		if increment == 1{
			break
		}
	}
}

// 5、快速排序
func QuickSort(arr []int, left, right int) {
	if left < right {
		i, j := left, right
		pivot := arr[left]
		for i < j {
			for i < j && arr[j] > pivot {
				j--
			}
			if i<j {
				arr[i] = arr[j]
				i++
			}
			for i < j && arr[i] <= pivot {
				i++
			}
			if i < j {
				arr[j] = arr[i]
				j--
			}
		}
		if left != i {
			arr[i] = pivot
		}
		QuickSort(arr, left, i-1)
		QuickSort(arr, i+1, right)
	}
}

// 6、归并排序
func MergeSort(arr []int) []int {
	length := len(arr)
	if length < 2 {
		return arr
	}
	mid := length/2
	left := MergeSort(arr[:mid])
	right := MergeSort(arr[mid:])
	return Merge(left, right)
}

func Merge(left, right []int) []int {
	var result []int
	leftStart, leftEnd, rightStart, rightEnd := 0, len(left), 0, len(right)
	for leftStart < leftEnd && rightStart < rightEnd {
		if left[leftStart] < right[rightStart] {
			result = append(result, left[leftStart])
			leftStart++
		} else {
			result = append(result, right[rightStart])
			rightStart++
		}
	}
	result = append(result, left[leftStart:]...)
	result = append(result, right[rightStart:]...)
	return result
}

// 7、堆排序
func HeapSort(arr []int)  {
	len := len(arr)
	for i := len/2-1; i >= 0; i-- {
		HeapAdjust(arr, len, i)
	}
	for i := len -1; i > 0; i-- {
		arr[i], arr[0] = arr[0], arr[i]
		HeapAdjust(arr, i, 0)
	}
}

func HeapAdjust(arr []int, len, index int) {
	leftChild := 2*index + 1
	rightChild := 2*index + 2
	max := index
	if leftChild < len && arr[leftChild] > arr[max] {
		max = leftChild
	}
	if rightChild < len && arr[rightChild] > arr[max] {
		max = rightChild
	}
	if index != max {
		arr[index], arr[max] = arr[max], arr[index]
		HeapAdjust(arr, len, max)
	}
}


// 8、桶排序
func BucketSort(arr []int) []int {
	tmp := make([]int, 100)
	for _, v := range arr {
		tmp[v] += 1
	}
	var result []int
	for k, v := range tmp {
		if v > 0 {
			for i := 0; i < v; i++ {
				result = append(result, k)
			}
		}
	}
	return result
}

// 9、二分查找法，返回索引
func BinarySearch(arr []int, val int) int {
	l, r := 0, len(arr)-1
	for l <= r {
		mid := (l + r)/2
		tmp := arr[mid]
		if tmp == val {
			return mid
		} else if val < tmp {
			r = mid - 1
		} else {
			l = mid + 1
		}
	}
	return -1
}