常用排序算法的Golang实现

最近在学习Golang，就把之前写过的排序算法拿golang复刻一下吧。

实现思路可以看python篇哈。

冒泡排序

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

选择排序

func selectSort(nums []int) {
	n := len(nums)

	for i := n; i > 0; i-- {
		pos := 0
		for j := 0; j < i; j++ {
			if nums[j] > nums[pos] {
				pos = j
			}
		}
		nums[i-1], nums[pos] = nums[pos], nums[i-1]
	}
}

插入排序

func insertSort(nums []int) {
	n := len(nums)
	for i := 1; i < n; i++ {
		cur := nums[i]
		pos := i
		for pos > 0 && cur < nums[pos-1] {
			nums[pos] = nums[pos-1]
			pos -= 1
		}
		nums[pos] = cur
	}
}

希尔排序

func shellSort(nums []int) {
	n := len(nums)
	gap := n / 2
	for gap >= 1 {
		insertByGap(nums, gap)
		gap /= 2
	}
}
func insertByGap(nums []int, gap int) {
	n := len(nums)
	for i := gap; i < n; i += gap {
		cur := nums[i]
		pos := i
		for pos > 0 && nums[pos-gap] > cur {
			nums[pos] = nums[pos-gap]
			pos -= gap
		}
		nums[pos] = cur
	}
}

归并排序

func mergeSort(nums []int) []int {
	n := len(nums)
	if n <= 1 {
		return nums
	}
	mid := n / 2
	left := mergeSort(nums[:mid])
	right := mergeSort(nums[mid:])
	var merged []int
	for len(left) > 0 && len(right) > 0 {
		if left[0] < right[0] {
			merged = append(merged, left[0])
			left = left[1:]
		} else {
			merged = append(merged, right[0])
			right = right[1:]
		}
	}
	if len(left) > 0 {
		merged = append(merged, left...)
	}
	if len(right) > 0 {
		merged = append(merged, right...)
	}
	return merged

}

快速排序

func quickSort(nums []int) {
	quickSortHelper(nums, 0, len(nums)-1)
}
func quickSortHelper(nums []int, first, last int) {
	if first < last {
		splitPoint := partition(nums, first, last)
		quickSortHelper(nums, first, splitPoint-1)
		quickSortHelper(nums, splitPoint+1, last)
	}
}
func partition(nums []int, first, last int) int {
	pivotValue := nums[first]
	leftMark := first + 1
	rightMark := last
	done := false
	for !done {
		for leftMark <= rightMark && nums[leftMark] <= pivotValue {
			leftMark += 1
		}
		for leftMark <= rightMark && nums[rightMark] >= pivotValue {
			rightMark -= 1
		}
		if leftMark > rightMark {
			done = true
		} else {
			nums[leftMark], nums[rightMark] = nums[rightMark], nums[leftMark]
		}
	}
	nums[first], nums[rightMark] = nums[rightMark], pivotValue
	return rightMark
}

现在这个是移动数据的位置，还有一个更简洁的实现方式，直接赋值，但是可能理解起来没那么容易：

func quickSortSimple(nums []int) {
	var helper func([]int, int, int)
	helper = func(arr []int, begin int, end int) {
		if begin < end {
			i := begin
			j := end
			empty := arr[begin]
			for i < j {
				for i < j && arr[j] > empty {
					j--
				}
				arr[i] = arr[j]
				for i < j && arr[i] < empty {
					i++
				}
				arr[j] = arr[i]
			}
			arr[i] = empty
			helper(arr, begin, i-1)
			helper(arr, i+1, end)
		} else {
			return
		}
	}
	helper(nums, 0, len(nums)-1)
}

计数排序

接收一个数组和数组中的最大值，统计每一个数字的个数，然后排序。

func countingSort(arr []int, maxValue int) []int {
	bucketLen := maxValue + 1
	bucket := make([]int, bucketLen)
	sortedIndex := 0
	length := len(arr)
	// 统计arr中每一个数字出现的次数
	for i := 0; i < length; i++ {
		bucket[arr[i]] += 1
	}

	for j := 0; j < bucketLen; j++ {
		for bucket[j] > 0 {
			arr[sortedIndex] = j
			sortedIndex += 1
			bucket[j] -= 1
		}
	}
	return arr
}