主流排序算法

按照排序的依据，可以分为两类，比较类排序与非比较类排序

比较类排序是通过比较决定次序，快排，选择排序，插入排序都属于此类，比较类排序的优势是适用性，它不在乎数据的分布，只要能比较就能排，但是比较类排序的速度有上限，时间复杂度下界是 $O(N logN)$

非比较类排序包括，计数排序，桶排序，基数排序，不通过排序进行比较，这类算法的时间复杂度为 $O(n)$ ，但是对数据类型限制比较大，而且因为用空间换时间，所以对数据的规模也有一定要求，此外，对数据的分布硬额比较敏感，如果分布不均匀（有的桶是空的，有的桶是满的），效率就会降低

冒泡排序

原理：依次比较两个元素，顺序错误就交换，直到没有交换的为止
代码实现：

func bubble(nums []int) []int {
    l := len(nums)
    //排序l - 1轮
    for i := 0; i < l - 1; i++ {
        swapped := flase
        //每轮的比较次数，前有的i轮让i和元素有序了
        for j := 0; j < l - i - 1; j++ {
            if nums[j] > nums[j + 1] {
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
                swapped = true
            }
        }
        //某轮没有交换说明已经完成
        if !swapped {
            break
        }
    }
    return nums
}

时间复杂度：最快是 $O(n)$ ，即数组本身就是排好的，最差是 $O(n^2)$

插入排序

原理：扑克牌插牌的逻辑，把元素依次与已排序部分比较，插入合适的位置
代码实现：

func insert(nums []int) []int {
    for i := 1; i < len(nums); i++ {
        cur := nums[i]
        j := i - 1
        for j >= 0 && nums[j] > cur {
            nums[j + 1] = nums[j]
            j--
        }
        nums[j + 1] = cur
    }
    return nums
}

选择排序

原理：在未排序的序列找到最小的，放到未排序序列的起始位置，重复这个过程，直到所有都排序完
代码实现

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

一般不会使用，无论是什么样的数据，它的时间复杂度都是 $O(n)$ ，唯一的好处是不占用额外的空间

希尔排序

归并排序

原理：分治法，把长度为N的序列分为N/2的两个序列，对这两个子序列进行排序，最后在合并为最终的序列
代码实现：

func mergeSort(arr []int) []int {
    if len(arr) < 2 {
        return arr
    }
    mid := len(arr) / 2
    left := mergeSort(arr[:mid])
    right := mergeSort(arr[mid:])
    return merge(left, right)
}
func merge(left, right []int) []int {
    res := make([]int, 0)
    i, j := 0, 0
    for i < len(left) && j < len(right) {
        if left[i] <= right[j] {
            res = append(res, left[i])
            i++
        } else {
            res = append(res, right[j])
            j++
        }
    }
    res = append(res, left[i:]...)
    res = append(res, right[j:]...)
    return res
}

时间复杂度是 $O(N log N)$ ,空间复杂度是 $O(N)$ , 合并的时候需要一个数组存放临时数据

快速排序

原理：也是分治法，从数组中选一个元素作为基准，重新排列，比基准小的放前面，大的放后面
代码实现：

func QuickSort(arr []int, left, right int) {
    if left < right {
        pivotIdx := partition(arr, left, right)
        QuickSort(arr, left, pivotIdx - 1)
        QuickSort(arr, pivotIdx + 1, right)
    }
}
func partition(arr []int, left, right int) int {
	//随机选择 pivot 并交换到最右端
	randomIndex := left + rand.Intn(right-left+1)
	arr[randomIndex], arr[right] = arr[right], arr[randomIndex]

	pivot := arr[right]
	i := left
	for j := left; j < right; j++ {
		if arr[j] < pivot {
			arr[i], arr[j] = arr[j], arr[i]
			i++
		}
	}
	arr[i], arr[right] = arr[right], arr[i]
	return i
}

时间复杂度：平均： $O(N \log N)$ 。最坏： $O(N^2)$ （当数组有序且每次选第一个数为基准时，退化为冒泡）