算法编程题-排序

比较型排序算法

所谓的比较型排序算法就是算法中会使用数据之间的比较，只能数组保存的是能相关比较大小的数据即可使用该类算法，相比于非比较型排序算法适用面更广。
在实现上进行了一定的封装，支持泛型和自定义排序规则，默认传入一个比较函数less，按照less指定的小于关系进行“从小到大”排序。抽象接口代码如下：

type Sorter[T any] struct {
	less func(item1, item2 T) bool
}

func NewSorter[T any](less func(item1, item2 T) bool) *Sorter[T] {
	return &Sorter[T]{less: less}
}

冒泡排序

冒泡排序如其名，就是排序的过程和冒泡有点像。一个气泡从水底浮向水面，其体积是越来越大的。那么同理，在排序的过程中，也可以让一个个大的元素浮上去，从而完成整个的排序。代码实现如下：

// BubbleSort 冒泡排序，时间复杂度：O(n^2) 空间复杂度：O(1), 稳定
func (s *Sorter[T]) BubbleSort(arr []T) {
	n := len(arr)
	for i := 0; i < n; i++ {
		var bubbleFlag bool // 是否有冒泡
		for j := i; j+1 < n; j++ {
			if s.less(arr[j+1], arr[j]) {
				arr[j], arr[j+1] = arr[j+1], arr[j]
				bubbleFlag = true
			}
		}
		if !bubbleFlag { // 无冒泡，说明已经排序完成，提前退出
			break
		}
	}
}

冒泡排序时间复杂度是$O(n^2)$，空间复杂度为$O(1)$。其是一种稳定的排序算法。在实现上可以记录一个标志，表明此一轮有没有发生冒泡，如果没有，说明数组已经完全有序，可以以前退出。

选择排序

选择排序同样也是人如其名，在每一轮中，选择剩余数组中的最小值，放入一个位置，经过n轮，完成排序。实现代码如下：

// SelectSort 选择排序，时间复杂度：(n ^ 2), 空间复杂度:O(1)，不稳定
func (s *Sorter[T]) SelectSort(arr []T) {
	n := len(arr)
	for i := 0; i < n; i++ {
		minPtr := i
		for j := i + 1; j < n; j++ {
			if s.less(arr[j], arr[minPtr]) {
				minPtr = j
			}
		}
		arr[minPtr], arr[i] = arr[i], arr[minPtr]
	}
}

选择排序时间复杂度$O(n^2)$，空间复杂度为$O(1)$，是一种不稳定的排序算法。

插入排序

插入排序的排序过程为：维护一个有序序列，然后将待排序的数字找到一个合适的位置，然后插入进去，这样还是一个有序序列，依次将所有元素完成这一个操作，即可完成数组的排序。实现代码如下：

// InsertSort 插入排序，时间复杂度:O(n^2) 空间复杂度:O(1), 稳定
func (s *Sorter[T]) InsertSort(arr []T) {
	n := len(arr)
	for i := 1; i < n; i++ {
		for j := i; j > 0; j-- {
			if s.less(arr[j], arr[j-1]) {
				arr[j], arr[j-1] = arr[j-1], arr[j]
			} else {
				break
			}
		}
	}
}

插入排序的时间复杂度平均为$O(n^2)$，但是对于一个基本有序的数组进行排序，时间复杂度可以达到$O(n)$，空间复杂度为$O(1)$，是一种稳定的排序算法。
优化插入排序，可以从两个方面入手，减少找位置的时间或者移动元素的时间，每一轮这两个的时间都是$O(n)$级别的，前者可以通过二分查找来优化，后者可以通过链表来优化，但是如何同时优化呢？笔者认为可以使用跳表，这样可以将插入排序的平均时间复杂度优化到$O(nlogn)$，但是缺点在于实现复杂，且空间开销较大，相比于快速排序堆排序等，有点得不偿失。

希尔排序

希尔排序其实就是对于插入排序的优化，前文提到，插入排序在基本有序的数组排序效率比较高，那么可以考虑对于数组的子序列进行排序，具体的思路就是将子数组分为多个子序列，在每一轮中只对子序列内部进行插入排序。子序列分组的规则是每隔gap个的元素作为一个子序列，gap值在轮数下不断减小，直到为一后相当于是对全部数据进行插入排序，由于此时数组已经基本有序，所以最后一轮插入排序的效率很高。

// 希尔排序，时间复杂度: O(n^(3 / 2)) 空间复杂度：O(1)， 不稳定
func (s *Sorter[T]) ShellSort(arr []T) {
	n := len(arr)
	gap := n >> 1
	for gap > 0 {
		for i := 0; i < gap; i++ {
			for j := i; j < n; j += gap {
				for k := i + gap; k < n; k += gap {
					if s.less(arr[k], arr[k-gap]) {
						arr[k], arr[k-gap] = arr[k-gap], arr[k]
					}
				}
			}
		}
		gap >>= 1
	}
}

希尔排序的时间复杂度为$O(n^{3/2})$，但是最坏情况下也可能恶化成$O(n^2)$，空间复杂度为$O(1)$，是一种不稳定的排序算法，适用于中等规模的数据集排序。

堆排序

堆排序就是基于堆这种数据结构的性质，往往使用一个最小堆，将堆顶的元素取出，然后将最后一个元素放到堆顶后，从上到下进行调整，重复这一个过程，就能完成数组的排序。

type Heap[T any] struct {
	less   func(item1, item2 T) bool
	array  []T
	length int // 标识实际长度
}

// NewHeap 构建一个空的堆
func NewHeap[T any](less func(item1, item2 T) bool) *Heap[T] {
	return &Heap[T]{less: less, array: make([]T, 0), length: 0}
}

// NewHeapWithArr 根据数组构建一个堆
func NewHeapWithArr[T any](less func(item1, item2 T) bool, arr []T) *Heap[T] {
	h := &Heap[T]{less: less, array: arr, length: len(arr)}
	for i := 1; i < len(arr); i++ {
		h.siftUp(i)
	}
	return h
}

// Push 往堆h中插入一个元素
func (h *Heap[T]) Push(v T) {
	h.pushBack(v)
	h.siftUp(h.length - 1)
}

// Top 返回堆顶的元素
func (h *Heap[T]) Top() T {
	return h.array[0]
}

// Pop 移除堆顶的元素并返回
func (h *Heap[T]) Pop() T {
	ret := h.array[0]
	h.array[0] = h.array[h.length-1]
	h.length--
	h.siftDown(0)
	return ret
}

func (h *Heap[T]) ToArr() []T {
	return h.array
}

func (h *Heap[T]) IsEmpty() bool {
	return h.length == 0
}

// pushBack 在尾部插入一个元素
func (h *Heap[T]) pushBack(v T) {
	if len(h.array) == h.length {
		h.array = append(h.array, v)
	} else {
		h.array[h.length] = v
	}
	h.length++
}

// siftUp 从pos位置处开始往上调整
func (h *Heap[T]) siftUp(pos int) {
	if pos < 0 || pos >= h.length {
		return
	}
	i := pos
	j := (pos - 1) / 2
	for j >= 0 && h.less(h.array[i], h.array[j]) {
		h.array[i], h.array[j] = h.array[j], h.array[i]
		i = j
		j = (i - 1) / 2
	}
}

// siftDown 从pos位置处开始往下调整
func (h *Heap[T]) siftDown(pos int) {
	if pos < 0 || pos >= len(h.array) {
		return
	}
	i := 0
	j1 := 2*i + 1
	j2 := 2*i + 2
	for j1 < h.length {
		if h.less(h.array[j1], h.array[i]) && ((j2 >= h.length) || h.less(h.array[j1], h.array[j2])) {
			h.array[i], h.array[j1] = h.array[j1], h.array[i]
			i = j1
		} else if h.less(h.array[j2], h.array[i]) {
			h.array[i], h.array[j2] = h.array[j2], h.array[i]
			i = j2
		} else {
			break
		}
		j1 = 2*i + 1
		j2 = 2*i + 2
	}
}

// HeapSort 堆排序，时间复杂度:O(nlogn), 空间复杂度：O(1), 不稳定
func (s *Sorter[T]) HeapSort(arr []T) {
	h := NewHeapWithArr(s.less, arr)
	k := len(arr) - 1
	for !h.IsEmpty() {
		arr[k] = h.Pop()
		k--
	}
	for i := 0; i < len(arr) / 2; i++ {
		arr[i], arr[len(arr) - 1 - i] = arr[len(arr) - 1 - i], arr[i]
	}
}

堆排序的时间复杂度为$O(nlogn)$，空间复杂度为$O(n)$，是一种不稳定的排序算法，适用于大数据量下且内存资源相对宝贵的条件下。

快速排序

快速排序是一种基于分制的思路，对于一个数组，从中选择一个基准点，以这个基准点，小于的数交换到左边取，大于的数交换到右边去，然后递归地对左边和右边的子数组进行同样的处理，从而完成整个排序过程。

// 快速排序实现，时间复杂度：O(nlogn)， 空间复杂度：O(1), 不稳定
func (s *Sorter[T]) QuickSort(arr []T) {
	s.quickSortV1(arr, 0, len(arr)-1)
}

// 递归形式的排序
func (s *Sorter[T]) quickSortV1(arr []T, left, right int) {
	if left >= right { // 递归终点
		return
	}
	base := arr[left]
	basePtr := left
	i := left + 1
	for i <= right {
		if s.less(arr[i], base) {
			basePtr++
			if basePtr != i {
				arr[basePtr], arr[i] = arr[i], arr[basePtr]
			}
		}
		i++
	}
	arr[left] = arr[basePtr]
	arr[basePtr] = base
	s.quickSortV1(arr, left, basePtr-1)
	s.quickSortV1(arr, basePtr+1, right)
}

以上实现版本的快速排序时间复杂度是$O(nlogn)$，空间复杂度为$O(1)$，是一种不稳定的排序算法，但是最坏情况下时间复杂度也会恶化到$O(n^2)$。比如上面的实现在数组基本有序的情况下，会化身为时间刺客，如下图。

一种常见的优化手段是从数组中取三个数字，然后以这三个数字的中位数作为基准点，如下为相关代码实现:

// quickSortV3优化实现，基准取头尾中三数中的平均数
func (s *Sorter[T]) quickSortV3(arr []T, left, right int) {
	if left >= right { // 递归终点
		return
	}
	s.adjustBase(arr, left, right)
	base := arr[left]
	basePtr := left
	i := left + 1
	for i <= right {
		if s.less(arr[i], base) {
			basePtr++
			if basePtr != i {
				arr[basePtr], arr[i] = arr[i], arr[basePtr]
			}
		}
		i++
	}
	arr[left] = arr[basePtr]
	arr[basePtr] = base
	s.quickSortV3(arr, left, basePtr-1)
	s.quickSortV3(arr, basePtr+1, right)
}

// adjustBase 调整基准值，将头尾中三数中的平均数放在头部作为基准
func (s *Sorter[T]) adjustBase(arr []T, left, right int) {
	basePtrs := []int{left, right, (left + right) / 2}
	s1 := NewSorter(func(i, j int) bool {
		return s.less(arr[i], arr[j])
	})
	s1.InsertSort(basePtrs)
	arr[left], arr[basePtrs[1]] = arr[basePtrs[1]], arr[left]
}

但是以上方法对于一个全是相同数字的数组还是会恶化成$O(n^2)$。
在某些面试中，可能有些面试官要求实现一些递归算法的非递归版本，比如实现非递归版本的快速排序。递归在编程语言中的实质就是借助栈来实现的，所以这种题目本质上就是在模拟递归，代码实现如下：

// 非递归实现，借助栈来模拟递归
func (s *Sorter[T]) quickSortV2(arr []T, left, right int) {
	stack := NewStack[[2]int]()
	stack.Push([2]int{left, right})
	for !stack.IsEmpty() {
		state := stack.Pop()
		left, right := state[0], state[1]
		if left >= right {
			continue
		}
		base := arr[left]
		basePtr := left
		i := left + 1
		for i <= right {
			if s.less(arr[i], base) {
				basePtr++
				if basePtr != i {
					arr[basePtr], arr[i] = arr[i], arr[basePtr]
				}
			}
			i++
		}
		arr[left] = arr[basePtr]
		arr[basePtr] = base
		stack.Push([2]int{left, basePtr - 1})
		stack.Push([2]int{basePtr + 1, right})
	}
}

实际上，也可以不使用栈，使用队列或者其他的数据结构都是可以的。

归并排序

归并排序的重点在于归并上，对于两个已经有序的数组而言，可以合并到一个有序的数组中，时间复杂度为$O(n)$，这样，最小的段即一个数的数组，必然是有序的，小段合成大段，最后合并完成整个数组的排序。

// MergeSort 归并排序，时间复杂度：O(nlogn), 空间复杂度：O(n), 稳定
func (s *Sorter[T]) MergeSort(arr []T) []T {
	return s.mergeSortV1(arr)
}

// 递归形式的归并排序
func (s *Sorter[T]) mergeSortV1(arr []T) []T {
	if len(arr) <= 1 { // 递归终点
		return arr
	}
	// 递归过程
	leftArr := s.mergeSortV1(append([]T(nil), arr[:len(arr)/2]...))
	rightArr := s.mergeSortV1(append([]T(nil), arr[len(arr)/2:]...))
	// 合并
	i := 0
	j := 0
	k := 0
	for i < len(leftArr) || j < len(rightArr) {
		if i >= len(leftArr) || (j < len(rightArr) && s.less(rightArr[j], leftArr[i])) {
			arr[k] = rightArr[j]
			j++
			k++
		} else {
			arr[k] = leftArr[i]
			i++
			k++
		}
	}
	return arr
}

归并排序也可以实现非递归的形式，如下：

// 非递归形式的归并排序
func (s *Sorter[T]) mergeSortV2(arr []T) []T {
	segLen := 1 // 比较的段长
	for segLen < len(arr) {
		for p := 0; p < len(arr); p += 2 * segLen {
			leftArr := append([]T(nil), arr[p:min(p+segLen, len(arr))]...)
			rightArr := append([]T(nil), arr[min(p+segLen, len(arr)):min(p+2*segLen, len(arr))]...)
			// 合并
			i := 0
			j := 0
			k := 0
			for i < len(leftArr) || j < len(rightArr) {
				if i >= len(leftArr) || (j < len(rightArr) && s.less(rightArr[j], leftArr[i])) {
					arr[p+k] = rightArr[j]
					j++
					k++
				} else {
					arr[p+k] = leftArr[i]
					i++
					k++
				}
			}
		}
		segLen *= 2
	}
	return arr
}

归并排序时间复杂度为$O(nlogn)$，空间复杂度为$O(n)$，是一种稳定的排序算法。归并排序适用于大数据量且要求稳定的场景，毕竟同时间复杂度的排序算法快速排序和堆排序都是不稳定的。

非比较型排序算法

可以注意到以上的排序算法都需要通过比较元素的大小来交换位置或者其他的操作，这类算法统称为比较型排序算法。另外一类非比较型排序算法，不需要比较大小，但是其适用面比较小。

计数排序

所谓的计数排序就是维护一个数组，用来表示每一个元素出现的次数，然后遍历数组，将各个数字取出即可。

type IntSorter struct {
}

func NewIntSorter() *IntSorter {
	return &IntSorter{}
}

// 计数排序，时间复杂度：O(n+k) k为数据范围 空间复杂度：O(k) 稳定
// 适用于数据范围不大的情况下
func (s *IntSorter) CountSort(arr []int64) {
	minv := arr[0]
	maxv := arr[0]
	for _, item := range arr {
		minv = min(minv, item)
		maxv = max(maxv, item)
	}
	counts := make([]int64, maxv-minv+1)
	for _, item := range arr {
		counts[item-minv]++
	}
	k := 0
	for i := int64(0); i < maxv-minv+1; i++ {
		for j := int64(0); j < counts[i]; j++ {
			arr[k] = i + minv
			k++
		}
	}
}

计数排序的时间复杂度为$O(n)$级别，空间复杂度为$O(m)$，其中m为数组中最大数减去最小数，可以看到，计数排序只适用于整数，且最好数据比较集中。

基数排序

以整数的基数排序来说明这一个过程。由于整数的每一位只有十种可能，从0到9，那么可以建立十个桶，遍历数组，按照最低位对应的数字放到对应的桶中，然后再将所有数组按照0号桶收集起来，然后从数字的低第二位做重复的操作，直到最大数字的最高位。代码实现如下：

func (s *IntSorter) RadixSort(arr []int) {
	var newBuckets func() []*List[int] = func() []*List[int] {
		buckets := make([]*List[int], 10)
		for i := 0; i < 10; i++ {
			buckets[i] = NewList[int]()
		}
		return buckets
	}
	buckets := newBuckets()
	oldBuckets := newBuckets()
	for _, num := range arr {
		oldBuckets[num%10].AppendNodeTail(NewListNode[int](num/10, num))
	}
	flag := true // 停止标志
	for flag {
		flag = false
		for i := 0; i < 10; i++ {
			for node := oldBuckets[i].Begin(); node != oldBuckets[i].End(); node = node.Next {
				if node.Key != 0 {
					flag = true
				}
				buckets[node.Key%10].AppendNodeTail(NewListNode[int](node.Key/10, node.Val))
			}
		}
		oldBuckets = buckets
		buckets = newBuckets()
	}
	// 此时所有数据都在零号桶里
	k := 0
	for node := oldBuckets[0].Begin(); node != oldBuckets[0].End(); node = node.Next {
		arr[k] = node.Val
		k++
	}
}

基数排序的时间复杂度也大致在$O(nm)$左右，对于整数可以认为是$O(n)$，空间复杂度为$O(n)$，适用于整数或者字符串等。