排序算法总结

基础排序算法

点击查看代码

 
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. 是否稳定：不稳定

！！！

算法排序

不基于比较的排序找到数组排序后的最大差值

题目描述

给定一个数组，求如果排序之后，相邻两数的最大差值，要求时 间复杂度O(N)，且要求不能用非基于比较的排序

注意不基于比较哦

思路

思路：桶排序
  1. 假设数组长度为n，准备n+1个桶
  2. 遍历该数组，将最小值放入到第1个位置，将最大值放入到最后一个位置
  3. 将剩下的数等分成等分成n-1份依次放入剩下对应范围的桶中，
  4. 最后这n+1个桶中至少有一个空桶，说明桶内的数值差不是最大差值，我们去桶间找最大差值
  5. 对于每个桶，我们都保存了每个桶的最小值和最大值，从第2个桶开始，每次计算当前桶的最小值与前一个桶(要有元素)的最大值的差，过程中我们动态更新最大差值
算法排序

堆排序

堆排序基本知识

基本介绍

堆是一个完全二叉树，因此我们可以利用节点的特性去使用一个数组模拟一颗完全二叉树：

  1. 下标为i的节点的左子节点的下标为i*2+1, 右子节点的下标为i*2+2
  2. 下标为i的节点的父节点的下标为(i-1)/2

建立堆的时间复杂度：O(log1) + O(log2) + … + O(logN) 近似于 O(N)，因此建立堆的时间复杂度为O(N)

堆有大根堆以及小根堆，没有规定堆中左子树的根必须大于(或小于)右子树的根。

堆排序的两个基本步骤：(具体说明看代码注释)
  1. 建堆，循环将数组中的每个数加入堆中（每次都需要heapInsert）
  2. 不断从堆的最后一个元素交换到堆的头部，然后将堆的长度减小1，再调整堆，每次都需要heapify
算法排序

归并排序

应用场景

  1. 求小和
  2. 求逆序对的个数

几个注意点：

mid := l + (r-l)>>1 避免数组越界

for i <= mid { help[index] = nums[i] index++ i++ }，这里是一个for循环，不是if，因为是要将后面剩下的数拷贝进来

for i <= mid { help[index] = nums[i] index++ i++ }，这里是一个for循环，不是if，因为是要将后面剩下的数拷贝进来

算法排序

冒泡排序以及优化

冒泡排序

思路：从左向右每次两两比较相邻元素，如果前一个元素大于后一个元素，那么就交换这两个元素，一趟下来肯定有一个元素放到了最后的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func BubbleSort(nums []int) []int {
	bubbleSort(nums)
	return nums
}

func bubbleSort(nums []int) {
	//从前往后进行交换，每次都会固定好后面的元素
	for i := 0; i < len(nums)-1; i++ {
		for j := 0; j < len(nums)-1-i; j++ {
			//两两比较并交换
			if nums[j] > nums[j+1] {
				nums[j], nums[j+1] = nums[j+1], nums[j]
			}
		}
	}
}
算法排序

选择排序

选择排序

思路：每次选择一个当前未排序的最小元素放到当前未排序的第一个位置上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func SelectSort(nums []int) []int {
	selectSort(nums)
	return nums
}

func selectSort(nums []int) {
	//存储最小元素对应的下标
	var min int
	//进行多少趟
	for i := 0; i < len(nums)-1; i++ {
		min = i
		//每趟从哪里开始
		j := i + 1
		for ; j < len(nums)-1; j++ {
			if nums[min] > nums[j] {
				min = j
			}
		}
		if min != i {
			nums[i], nums[min] = nums[min], nums[i]
		}
	}
}
算法排序

直接插入排序以及优化

直接插入排序

直接插入排序是简单排序中性能最好的

平均时间复杂度：O(n^n / 4)
最好时间复杂度：O(n)
最坏时间复杂度：O(n^n)

直接插入排序版本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
package main

import (
	"log"
	"math/rand"
	"time"
)

/**
 * @Author: yirufeng
 * @Email: yirufeng@foxmail.com
 * @Date: 2020/9/10 9:12 上午
 * @Desc: 直接插入排序
 */

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

//思路：如果当前元素比前一个元素小就交换，一直到当前元素大于等于前一个元素
func insertSort(nums []int) {
	//默认下标为0的已经有序，因此从下标为1的开始插入
	for i := 1; i < len(nums); i++ {
		//插入条件：要排序的元素一定要小于前面的元素
		if nums[i] < nums[i-1] {
			//什么时候结束插入：当要插入的元素的值大于等于前面的那个元素就停止插入
			for j := i; j >= 1 && nums[j] < nums[j-1]; j-- {
				nums[j], nums[j-1] = nums[j-1], nums[j]
			}
		}
	}
}


//写一个随机数生成器
func RandArray(length int) []int {
	nums := []int{}
	for i := 0; i < length; i++ {
		r := rand.New(rand.NewSource(time.Now().UnixNano()))
		nums = append(nums, r.Intn(100))
	}
	return nums
}

func main() {
	rand.Seed(time.Now().UnixNano())
	nums := RandArray(30)
	log.Println(nums)
	log.Println(InsertSort(nums))
}

算法排序

快速排序以及优化

经典快速排序

思路：选取数组中的第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

算法排序