排序算法

冒泡排序

大的元素往上冒

1
2
3
4
5
6
7
8
9


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

特点：稳定

选择排序

每次选择剩余元素的最小数，与剩余元素的第一个位置交换。

从0,1,2…n-1位置中选择最小元素arr[minI]与arr[0]交换
从1,2…n-1位置中选择最小元素arr[minI]与arr[1]交换

…
从n-2,n-1位置中选择最小元素arr[minI]与arr[n-1]交换
结束排序

特点：稳定

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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

插入排序

将元素插入有序数列。

有序列表arr[0:1] ，无序列表arr[1:n]
- 取arr[1]暂存到t,将t与arr[0]比较，若比t大，则将arr[0]=arr[1]，空出位置0，arr[0] = t; 否则arr[1]=t
有序列表arr[0:2] ，无序列表arr[2:n]
- 取arr[2]暂存到t，若t<arr[1]，则arr[2]=arr[1]，空出位置2，继续下一步操作；否则arr[2]=t，结束。
- 将t与arr[0]比较，若t<arr[0]，则arr[1]=arr[0]，空出位置0，arr[0] = t；否则arr[1]=t，结束。
…
有序列表arr[0:n-1] ，无序列表arr[n-1:n]
- 取arr[n-1]暂存到t, 若t<arr[n-2]，则arr[n-1]=arr[n-2]，空出位置n-2，继续下一步；否则arr[n-1]=t,结束操作
- 若t<arr[n-3],则arr[n-2]=arr[n-3]，空出位置n-3，继续下一步；否则arr[n-2]=t
  
  …
- 若t<arr[1]，则arr[2]=arr[1]，空出位置1，继续下一步;否则arr[2]=t，结束操作
- 若t<arr[0]，则arr[1]=arr[0]，空出位置0，arr[0]=t，结束操作;否则arr[1]=t，结束操作
结束。有序列表arr[0:n] ，无序列表arr[n:n]。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


func insertSort(nums []int) {
	t := 0
	j := 0
	for i := 1; i < len(nums); i++ {
		t = nums[i]
		j = 0
		for j = i - 1; j >= 0; j-- {
			if nums[j] > t {
				nums[j+1] = nums[j]
			} else {
				break
			}
		}
		nums[j+1] = t
	}
}

希尔排序

跟插入相同，只不过加入了步长控制，

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


func shellSort(nums []int) {
	for step := len(nums) >> 1; step > 0; step >>= 1 {
		for i := step; i < len(nums); i += step {
			t := nums[i]
			j := 0
			for j = i - step; j >= 0; j -= step {
				if t < nums[j] {
					nums[j+step] = nums[j]
				} else {
					break
				}
			}
			nums[j+step] = t
		}
	}
}

特点：不稳定

归并排序

分治法。将两个有序的数列合并

复杂度为$$O(n+n/2+n/4….+1)$$ 简略为 $$nlog_2n$$ ,
空间复杂度为 O(n)
递归消耗空间复杂度 $$ log_2n $$
稳定性：否

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


func mergeSort(nums []int) {
	if len(nums) <= 1 {
		return
	}
	mid := len(nums) / 2
	mergeSort(nums[0:mid])
	mergeSort(nums[mid:len(nums)])

  //merge
	tempArray := make([]int, len(nums))
	copy(tempArray, nums)
	left := 0
	right := mid
	i := 0
	for left < mid && right < len(nums) {
		if tempArray[left] <= tempArray[right] {
			nums[i] = tempArray[left]
			left++
		} else {
			nums[i] = tempArray[right]
			right++
		}
		i++
	}
	for left < mid {
		nums[i] = tempArray[left]
		i++
		left++
	}
	for right < len(nums) {
		nums[i] = tempArray[right]
		i++
		right++
	}
}

快速排序

分治法。每次循环pivot归位。pivot的选择会影响时间和递归空间

最差复杂度为： $$ O((n-1)(n-2)…(1)) $$ 简略为 $$ O(n^2) $$ ，
平均复杂度为： $$O(nlog_2n)$$
空间复杂度为： $$O(1)$$
递归空间复杂度最优为：$$ O(log_2n) $$ 刚好每次平分。
稳定性：否

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


func quickSort(nums []int) {
	if len(nums) <= 1 {
		return
	}
	pivot := nums[0]

	left := 0
	right := len(nums) - 1
	for left < right {
		for left < right && nums[right] > pivot {
			right--
		}
		if left < right {
			nums[left] = nums[right]
			left++
		}

		for left < right && nums[left] < pivot {
			left++
		}
		if left < right {
			nums[right] = nums[left]
			right--
		}
	}
	nums[left] = pivot

	quickSort(nums[0:left])
	quickSort(nums[left+1:])
}

堆排序

什么是堆? 堆通常是一个可以被看做一棵完全二叉树的数组对象。
最大堆、最小堆? 最大堆，父节点的值大于等于子节点。最小堆，父节点的值小于等于子节点。
如何维护某个节点子树的最大堆? 每次某个节点的值发生变化后，都要对其所在子树从上往下调整堆(序号小的到大的)。为什么是上往下?因为最大堆的某个节点换成较小值后只影响其子树的变化，故需要继续往下调整。
如何建立堆? 从下往上即根节点递减调整每一个节点的堆，因为这才能保证下层的最堆的根节点小于其父节点。
堆排序算法 如输入数组A[0…n]

建立最大堆，最大的元素在根节点
根节点的值与A[n]互换位置，即剩余最大元素归位
n–，将A[n]从堆中移出
调整堆为最大堆，重复2~3，直到堆的长度为1，此时的元素全部归位

空间复杂度：O(1)
时间复杂度: $$nlog_2n$$
硬伤：对堆顶节点进行堆化，会依次访问数组下标是i, i*2+1, i*2+2 的元素，而不是像快速排序那样，局部顺讯访问，所以，这样对cpu缓存是不友好的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


func heapSort(nums []int) {
	buildMaxHeap(nums)
	heapSize := len(nums)

	for i := len(nums) - 1; i >= 1; i-- {
		nums[0], nums[i] = nums[i], nums[0]
		heapSize--
		maxHeapify(nums, 0, heapSize)
	}
}

//下往上建立堆
func buildMaxHeap(nums []int) {
	heapSize := len(nums)
	for i := heapSize>>1 - 1; i >= 0; i-- {
		maxHeapify(nums, i, heapSize)
	}
}

//上往下调整堆
func maxHeapify(nums []int, i int, heapSize int) {
	for {
		maxI := i
		leftChildI := i<<1 + 1
		rightChildI := leftChildI + 1
		if leftChildI < heapSize && nums[leftChildI] > nums[maxI] {
			maxI = leftChildI
		}
		if rightChildI < heapSize && nums[rightChildI] > nums[maxI] {
			maxI = rightChildI
		}

		if i == maxI {
			break
		}

		nums[i], nums[maxI] = nums[maxI], nums[i]
		i = maxI
	}
}

计数排序

顾名思义，就是统计元素个数，然后填充列表。如 [1,2,4,1,3]，1的个数为2，2的个数为1，4的个数为1，3的个数为1，后依次填充列表。为了保证稳定性，需要有所处理

为了化简，输入限制为非负数。

复杂度为O(n*2+k*2) ,n为元素个数，k为数组长度
稳定性：是(需要特殊处理)
空间复杂度：O(n+k)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


func countingSort(nums []int) {
	max := nums[0]
	for i := 1; i < len(nums); i++ {
		if max < nums[i] {
			max = nums[i]
		}
	}
	countTable := make([]int, max+1)
	for i := 0; i < len(nums); i++ { //整数范围k
		countTable[nums[i]]++
	}

  // 为了保证稳定
	for i := 1; i < len(countTable); i++ { //整数范围k
		countTable[i] += countTable[i-1]
	}

	copyNums := append([]int{}, nums...)
	for i := len(nums) - 1; i >= 0; i-- { //输出长度n
		nums[countTable[copyNums[i]]-1] = copyNums[i]
		countTable[copyNums[i]]--
	}
}

Table of Contents