排序算法总结

基础排序算法

点击查看代码

 
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
package basic_sort

/**
 * @Author: yirufeng
 * @Date: 2021/4/13 8:28 下午
 * @Desc: 选择排序

时间复杂度：假设数组中有n个数字
	大循环需要遍历n-2趟，然后每一个大循环中，
							我们都需要从开始的数字一直到最后选出最小的数字(时间复杂度：O(n))，然后填充到当期那还没有排好序的起始位置

最后总的时间复杂度：O(n^2)，
空间复杂度：O(1)。
稳定的排序算法（因为两个相等的数字前面那个一定是排序的时候第一个会被放置到前面的）
 **/

func SelectedSort(nums []int) {
	selectedSort(nums)
}

func selectedSort(nums []int) {
	var min int
	for i := 0; i < len(nums)-1; i++ {
		//每次从nums[i]开始起
		min = i
		//依次与后面比对来选择最小的
		for j := i + 1; j < len(nums); j++ {
			if nums[min] > nums[j] {
				min = j
			}
		}
		//交换nums[min]与nums[i]
		nums[i], nums[min] = nums[min], nums[i]
	}
}

选择排序

选择排序总结：

  1. 时间复杂度：O(n^2)
  2. 空间复杂度：O(1)。
  3. 不稳定的排序算法（比如A 80 B 80 C 70 这三个卷子从小到大排序，最后将会变成CBA，但是稳定的应该是CAB）

三个版本的冒泡排序：

  1. 最基本的
  2. 如果某次冒泡的时候没有交换元素，那么说明这一趟以及后面的元素都是有序的，之后后面我们就不再需要进行冒泡，可以直接退出
  3. 在第二种改进的基础上再使用一个变量，表示我们最后交换的位置，下次遍历到这个位置就可以了

点击查看代码

 
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
package basic_sort

/**
 * @Author: yirufeng
 * @Date: 2021/4/13 8:28 下午
 * @Desc:

有好几个版本：
1. 最基本的
2. 如果某次冒泡的时候没有交换元素，那么说明这一趟以及后面的元素都是有序的，之后后面我们就不再需要进行冒泡，可以直接退出
3. 在第二种改进的基础上再使用一个变量，表示我们最后交换的位置，下次遍历到这个位置就可以了
 **/

func BubbleSort(nums []int) {
	bubbleSortV2(nums)
}

//最基本的
func bubbleSortV1(nums []int) {
	for i := 1; i < len(nums); i++ { //冒泡的次数
		for j := 0; j < len(nums)-i; j++ {
			//如果前面比后面大就交换
			if nums[j] > nums[j+1] {
				nums[j], nums[j+1] = nums[j+1], nums[j]
			}
		}
	}
}

//如果某次冒泡的时候没有交换元素，那么说明这一趟以及后面的元素都是有序的，之后后面我们就不再需要进行冒泡，可以直接退出
func bubbleSortV2(nums []int) {
	//表示某一趟是否有元素交换
	flag := true
	for i := 1; i < len(nums); i++ { //冒泡的次数
		flag = true
		for j := 0; j < len(nums)-i; j++ {

			//如果前面比后面大就交换
			if nums[j] > nums[j+1] {
				flag, nums[j], nums[j+1] = false, nums[j+1], nums[j]
			}
		}
		//如果没有元素交换，说明已经有序，直接退出即可
		if flag {
			break
		}
	}
}

//在第二种改进的基础上再使用一个变量，表示我们最后交换的位置，下次遍历到这个位置就可以了
//使用一个变量记录最后发生交换的位置，说明该位置之后都是有序的
func bubbleSortV3(nums []int) {
	//表示某一趟是否有元素交换
	flag := true
	//表示最后发生交换的位置
	//注意点1:这里必须再额外使用临时变量，因为如果只是用一个变量lastSwapPos的话，
	//lastSwapPos的值会一直改变，因此如果一旦变小，我们的for循环就会推出
	lastSwapPos := len(nums) - 1     //注意点2：初始值赋值是len(nums) - 1
	for i := 1; i < len(nums); i++ { //冒泡的次数
		lastSwapPosTemp := len(nums) - i //注意点3：初始值赋值是len(nums) - i
		flag = true
		//下次遍历的时候遍历到我们上次最后发生交换的位置就可以了
		for j := 0; j < lastSwapPos; j++ {
			//如果前面比后面大就交换
			if nums[j] > nums[j+1] {
				flag, nums[j], nums[j+1], lastSwapPosTemp = false, nums[j+1], nums[j], j //注意点4：这里lastSwapPosTemp应该赋值j，因为j与j+1比较过了，所以就认为j之后是已经有序的了
			}
		}
		//如果没有元素交换，说明已经有序，直接退出即可
		if flag {
			break
		}

		lastSwapPos = lastSwapPosTemp
	}
}

冒泡排序

冒泡排序总结：

  1. 时间复杂度：O(n^2)，最好是O(n)
  2. 空间复杂度：O(1)。
  3. 稳定

点击查看代码

 
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
package basic_sort

/**
 * @Author: yirufeng
 * @Date: 2021/4/13 8:28 下午
 * @Desc:

时间复杂度：O(n^2)
空间复杂度：O(1)
稳定的：因为是到前面找到一个小于等于自己的后面那个位置
 **/

func InsertSort(nums []int) {
	insertSort(nums)
}

func insertSort(nums []int) {
	var j int
	//第一个元素已经有序，只需要插入后面的元素即可
	for i := 1; i < len(nums); i++ {
		//当前要插入的元素目前位于i位置
		cur := nums[i]
		//从后往前找，直到前面元素小于当前元素就停，并且遍历的过程中不断将前面的元素移动到后面
		for j = i - 1; j >= 0 && nums[j] > cur; j-- {
			nums[j+1] = nums[j]
		}
		//此时j指向的元素就是前面那个小于或者等于当前元素的位置
		//但是我们应该在j+1位置插入
		nums[j+1] = cur
	}
}

直接插入排序总结

直接插入排序总结：

  1. 时间复杂度：O(n^2)，
  2. 空间复杂度：O(1)。
  3. 稳定的：因为是到前面找到一个小于等于自己的后面那个位置

进阶排序算法

点击查看代码

 
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
package advanced_sort

import (
	"algos/模板/排序/util"
	"fmt"
	"sort"
)

/**
 * @Author: yirufeng
 * @Date: 2021/4/14 3:31 下午
 * @Desc: 归并排序
 **/

func MergeSort(nums []int) {
	mergeSort(nums, 0, len(nums)-1)
}

func mergeSort(nums []int, l, r int) {
	if l == r {
		return
	}

	//找到中间点，一分为二
	mid := l + (r-l)>>1
	//划分成左右两个有序的空间
	mergeSort(nums, l, mid)
	mergeSort(nums, mid+1, r)
	//将左右两部分以mid为划分轴进行合并
	merge(nums, l, mid, r)

}

//合并nums[l:mid+1] 与 nums[mid+1:r+1]两部分内容
func merge(nums []int, l, mid, r int) {
	i, j := l, mid+1
	cur := 0
	//注意点1：这里必须借助一个数组，否则我们前面可能还没有被排序的结果会被我们后半部分的内容覆盖掉，导致前面就没有内容
	help := make([]int, r-l+1)
	for i <= mid && j <= r {
		if nums[i] < nums[j] {
			help[cur], cur, i = nums[i], cur+1, i+1
		} else {
			help[cur], cur, j = nums[j], cur+1, j+1
		}
	}

	for i <= mid {
		help[cur], cur, i = nums[i], cur+1, i+1
	}
	for j <= r {
		help[cur], cur, j = nums[j], cur+1, j+1
	}

	//最后记得我们的help数组中的内容要放回到我们的原来的数组中
	for i := 0; i < len(help); i++ {
		nums[l+i] = help[i]
	}
}

func main() {
	nums := util.GenerateRandomNums(0, 100, 30)
	fmt.Println(nums)
	temp := make([]int, 30)
	copy(temp, nums)
	sort.Ints(temp)
	MergeSort(nums)
	fmt.Println(temp)
	fmt.Println(nums)
}

归并排序

  1. 时间复杂度：O(nlogN) 最好最坏都是O(NlogN)
  2. 空间复杂度：O(n)。需要一个辅助空间
  3. 是否稳定：稳定的（因为一旦两个数相等我们就不比较，并且每次都是前半部分与后半部分进行比较，所以前面同样的内容与后面同样的内容的相对位置不会改变）

点击查看代码

 
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
package main

import (
	"algos/模板/排序/util"
	"fmt"
	"log"
	"sort"
)

/**
 * @Author: yirufeng
 * @Date: 2021/4/14 3:29 下午
 * @Desc: 从小到大的堆排序(需要建立一个大顶堆)

从小到大排序需要建立一个大顶堆，因为我们建立好大顶堆之后，每次从堆头开始排除元素，然后都会将堆头放到目前数组的最后位置，最后位置会不断缩小，
因此我们最后的位置就是一个不断往前移动的过程，从而就是说我们得到的整个数组是从小到大的
 **/

func HeapSort(nums []int) {
	heapSort(nums)
}

func heapSort(nums []int) {
	if nums == nil || len(nums) < 2 {
		return
	}

	for i := 0; i < len(nums); i++ {
		heapPush(nums, i)
	}

	log.Println("建堆完成--------------->", nums)
	heapSize := len(nums)

	//之后不断吐出元素
	for heapSize > 0 {
		nums[0], nums[heapSize-1] = nums[heapSize-1], nums[0]
		heapSize--
		heapify(nums, heapSize)
	}
}

//表示当前要加入的是nums中的索引为index的元素
func heapPush(nums []int, index int) {
	for (index-1)>>1 >= 0 && nums[index] > nums[(index-1)>>1] {
		nums[index], nums[(index-1)>>1], index = nums[(index-1)>>1], nums[index], (index-1)>>1
	}
}

//length 表示堆的元素个数
func heapify(nums []int, length int) {
	index := 0
	// (index << 1 + 1) < length 说明是有左子树的
	for (index<<1 + 1) < length { //思路：每次找到左右孩子中更大的与父进行交换
		left := index<<1 + 1
		//如果有右子树并且右子树比左子树大
		if left+1 < length && nums[left+1] > nums[left] {
			left++
		}
		//如果当前节点比左右孩子中大的大，就不交换
		if nums[left] <= nums[index] {
			break
		}
		//如果当前节点比左右孩子中大的小，交换当前节点与左右孩子中较大的
		//同时让index变为left
		nums[left], nums[index], index = nums[index], nums[left], left
	}
}

func main() {
	nums := util.GenerateRandomNums(0, 100, 50)
	temp := make([]int, 50)
	copy(temp, nums)
	sort.Ints(temp)
	fmt.Println(temp)
	HeapSort(nums)
	fmt.Println(nums)
}

点击查看代码

 
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
package main

import (
	"algos/模板/排序/util"
	"fmt"
	"sort"
)

/**
 * @Author: yirufeng
 * @Date: 2021/4/15 2:20 下午
 * @Desc: 从大到小的排序，需要建立一个小顶堆
 **/

func HeapSort(nums []int) {
	heapSort(nums)
}

func heapSort(nums []int) {

	//如果nums为空或者元素个数小于两个，可以直接退出
	if nums == nil || len(nums) < 2 {
		return
	}

	//此时我们需要不断将元素加入我们的堆中
	for i := 1; i < len(nums); i++ {
		heapInsert(nums, i)
	}

	//获取堆的大小
	heapSize := len(nums)

	//此时我们不断将堆里面的元素弹出放到应该放置的位置
	for heapSize > 0 {
		//将堆的最后一个元素与堆顶交换
		nums[0], nums[heapSize-1] = nums[heapSize-1], nums[0]
		//堆的元素个数减去1
		heapSize--
		//开始从堆顶从上往下开始调整堆
		heapAdjustFromTopToBottom(nums, heapSize-1) // 从下到上的堆调整
	}
}

//第二个参数表示插入的元素位于nums的位置
func heapInsert(nums []int, index int) {
	//不断比较当前插入的位置的元素与父节点的大小，如果比父节点小就交换
	for (index-1)>>1 >= 0 && nums[(index-1)>>1] > nums[index] {
		nums[index], nums[(index-1)>>1], index = nums[(index-1)>>1], nums[index], (index-1)>>1
	}
}

//第二个参数表示当前堆的元素个数
func heapAdjustFromTopToBottom(nums []int, length int) {
	index := 0
	for index<<1+1 < length {
		left := index<<1 + 1

		//如果有右孩子并且右比左小
		if left+1 < length && nums[left+1] < nums[left] {
			left++
		}

		//当前节点小于等于两个孩子较小的
		if nums[index] <= nums[left] {
			break
		}
		nums[index], nums[left], index = nums[left], nums[index], left
	}
}

func main() {
	nums := util.GenerateRandomNums(0, 100, 50)
	temp := make([]int, 50)
	copy(temp, nums)
	sort.Ints(temp)
	fmt.Println(temp)
	HeapSort(nums)
	fmt.Println(nums)
}

点击查看代码

 
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
package main

import (
	"algos/模板/排序/util"
	"fmt"
	"math/rand"
	"sort"
)

/**
 * @Author: yirufeng
 * @Date: 2021/4/14 3:31 下午
 * @Desc: 从小到大的快速排序
 **/

func QuickSort(nums []int) {
	quickSort(nums, 0, len(nums)-1)
}

//表示对[l,r]的元素进行快排
func quickSort(nums []int, l, r int) {
	if l < r {
		//在[l,r]区间内生成一个随机数作为划分
		index := rand.Intn(r-l+1) + l
		//每次都把我们随机选择的元素交换到最后
		nums[index], nums[r] = nums[r], nums[index]
		//进行划分，得到两个相等的区间
		less, more := partition(nums, l, r)
		//继续对小于和大于的两个区间进行快速排序
		quickSort(nums, l, less-1)
		quickSort(nums, more+1, r)
	}
}

//返回两个结果是等于我们随机数的区间的左端点和右端点
func partition(nums []int, l, r int) (int, int) { //使用nums[r]作为一个划分
	less, more := l-1, r
	num := nums[r]
	cur := l
	for cur < more {
		if nums[cur] < num {
			nums[less+1], nums[cur], less, cur = nums[cur], nums[less+1], less+1, cur+1
		} else if nums[cur] > num {
			nums[more-1], nums[cur], more = nums[less+1], nums[more-1], more-1
		} else if nums[cur] == num {
			more++
		}
	}
	nums[more], nums[r] = nums[r], nums[more]
	//每次随机择一个划分点
	return less + 1, more - 1
}

func main() {
	nums := util.GenerateRandomNums(0, 100, 10)
	fmt.Println(nums)
	temp := make([]int, 10)
	copy(temp, nums)
	sort.Ints(temp)
	fmt.Println(temp)
	QuickSort(nums)
	fmt.Println(nums)
}

快速排序

思路：采用荷兰国旗的问题进行划分，每次可以划分为3个区间，分别是小于，等于以及大于的区间。

  1. 时间复杂度：O(nlogN) 最好是O(nlogN) 最坏是O(n^2)
  2. 空间复杂度：O(n)。
  3. 是否稳定：不稳定

！！！

算法排序

快速排序以及优化

经典快速排序

思路：选取数组中的第1个元素作为划分元素，划分为两部分，左边一部分比该元素小，右边一部分比该元素大

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
package quickSortV1

import (
	"InterviewQuestions/Algo/sort"
	"fmt"
)

/**
 * @Author: yirufeng
 * @Email: yirufeng@foxmail.com
 * @Date: 2020/9/10 7:45 上午
 * @Desc:
 */

/*
快速排序第1个版本：选择第1个元素作为划分枢轴
注意：切片作为参数传递的时候是一个引用
*/
func QuickSort(nums []int) []int {
	quickSort(nums, 0, len(nums)-1)
	return nums
}

func quickSort(nums []int, low int, high int) {
	var pivotkey int
	if low < high {
		//pivotkey 为枢轴防止的最终下标
		pivotkey = partition(nums, low, high)
		quickSort(nums, low, pivotkey-1)
		quickSort(nums, pivotkey+1, high)
	}
}

func partition(nums []int, low int, high int) int {
	//选择划分元素
	dummy := nums[low]
	for low < high {
		for low < high && dummy <= nums[high] {
			high--
		}
		swap(nums, low, high)
		for low < high && dummy > nums[low] {
			low++
		}
		swap(nums, low, high)
	}
	//最后low == high
	return low
}

func swap(nums []int, i int, j int) {
	nums[i], nums[j] = nums[j], nums[i]
}


//------------------------------for test------------------------------
func main() {

	fmt.Println(QuickSort(sort.RandArray(100)))
}

经典快速排序的不足

虽然经典快速排序性能相对其他排序性能较高，但仍然有一定的瓶颈，例如如果是一个有序的数组。

此外快速排序可以从以下几点进行改进：

  1. 优化选取枢轴的策略
    1. 随机从low到high中选择一个下标对应的元素作为枢轴
    2. (三数取中)从left, high 以及mid对应的下标的元素中的三个选择一个大小居中的元素
    3. (九数取中)
  2. 优化不必要的交换：采用置换而不是交换。我们可以提前存储nums[low],之后每次在右边找到小的元素就将其赋值给nums[low]，每次在左边找到大的元素可以直接赋值给nums[high]
  3. 优化小数组的排序方案：虽然快速排序可以有很好的性能，但是在数组较小时，直接插入排序效率比快速排序效率高(直接插入排序是简单排序中性能最好的)
  4. 对快排进行尾递归优化：如果传入一个大量数据且有序的数组，快排会不断的递归，栈的深度也会越来越深，因此很容易在数据量大且数据有序的时候造成栈溢出(申请不到更多的栈空间)

9QFpxr

算法排序