各种排序算法

```
// 冒泡排序
func bubbleSort(nums []int) {
	size := len(nums)
	for i := 0; i < size - 1; i++ {
		for j := i + 1; j < size; j++ {
			if nums[j] < nums[i] {
				nums[i], nums[j] = nums[j], nums[i]
			}
		}
	}
}
// 选择排序
func selectSort(nums []int) {
	size := len(nums)
	idx := 0
	for i := 0; i < size - 1; i++ {
		idx = i
		for j := i + 1; j < size; j++ {
			if nums[j] < nums[idx] {
				idx = j
			}
		}
		if idx != i {
			nums[i], nums[idx] = nums[idx], nums[i]
		}
	}
}
// 快速排序
func quickSort(nums []int, left, right int) {
	tmp := nums[left]
	i, j := left, right
	for i < j {
		for i < j && nums[j] >= tmp {
			j--
		}
		nums[i] = nums[j]
		for i < j && nums[i] <= tmp {
			i++
		}
		nums[j] = nums[i]
	}
	nums[i] = tmp
	if i > left + 1 {
		quickSort(nums, left, i - 1)
	}
	if i < right - 1 {
		quickSort(nums, i + 1, right)
	}
}
// 插入排序
func insertSort(nums []int, left, right int) {
	for i := left + 1; i <= right; i++ {
		j := left
		for j = left; j < i; j++ {
			if nums[j] >= nums[i] {
				tmp := nums[i]
				for k := i; k > j; k-- {
					nums[k] = nums[k - 1]
				}
				nums[j] = tmp
				break
			}
		}
	}
}
// 希尔排序 
func shellSort(nums []int) {
	size := len(nums)
    for step := size / 2; step > 0; step /= 2 {
        for i := 0; i < step; i++ {
            for j := i + step; j < size; j += step {
                for k := i; k < j; k += step {
                    if nums[j] <= nums[k] {
                        tmp := nums[j]
                        for l := j; l > k; l -= step {
                            nums[l] = nums[l - step]
                        }
                        nums[k] = tmp
                        break
                    }
                }
            }
		}
    }
}
// 桶排序
func bucketSort(nums []int) {
	min, max := 0, 0
	for i := 0; i < len(nums); i++ {
		if min > nums[i] {
			min = nums[i]
		} else if max < nums[i] {
			max = nums[i]
		}
	}
	newsize := max - min + 1
	arr := make([]int, newsize)
	for i := 0; i < len(nums); i++ {
		arr[nums[i] - min]++
	}
	pos := 0
	for i := 0; i < newsize; i++ {
		for arr[i] > 0 {
			nums[pos] = i + min
			pos++
			arr[i]--
		}
	}
}
// 归并排序
func mergeArray(nums []int, left, mid, right int) {
	idxL, idxR := left, mid
	tmp := make([]int, right - left + 1)
	pos := 0
	for idxL < mid && idxR <= right {
		if nums[idxL] > nums[idxR] {
			tmp[pos] = nums[idxR]
			idxR++
		} else {
			tmp[pos] = nums[idxL]
			idxL++
		}
		pos++
	}
	for idxL < mid {
		tmp[pos] = nums[idxL]
		idxL++
		pos++
	}
	for idxR <= right {
		tmp[pos] = nums[idxR]
		idxR++
		pos++
	}
	for i := 0; i < right - left + 1; i++ {
		nums[left + i] = tmp[i]
	}
}
func mergeSort(nums []int, left, right int) {
	if left > (right - 1) {
		return
	}
	mid := (left + right) / 2
	mergeSort(nums, left, mid)
	mergeSort(nums, mid + 1, right)
	mergeArray(nums, left, mid + 1, right)
}
```

我的文档笔记