面试问题浓缩总结
小游
2021-03-21

排序算法

image-20210310152450389

# 插入排序

# 直接插入排序

插入排序是最简单的，我们不断比较插入数据

// 插入排序
// 时间复杂度 n^2
// 因为我们这里是两层for循环，运气好的话，如果是有序的那么只需要执行一层，时间复杂度就是n
// 运气不好的话时间复杂度就是 n^2 平均的时间复杂度为 n^2
// 空间复杂度 1 ，因为我们只使用了一个临时变量，然后就没申请其他的了，所以空间复杂度为 1
func insertSort(arr []int){
	// 使用j来表示当前排序的位置
	var j = 0
	for i:=1;i<len(arr);i++{
		// 使用临时变量存储
		tmp:=arr[i]
		// 这个就是核心部分，首先我们让j处于i上
		// 当j-1大于tmp也就是arr[i]的时候,我们就需要把数字向后移动
		for j = i ; j>0 && arr[j-1] > tmp ; j--{
			arr[j] = arr[j-1]
		}
		// for循环的顺序 就是先j=1，然后执行判断语句，成功的话我们就执行函数体，最后才执行j--
		// 所以我们这里移动后，j实际上减了1，这样我们就可以直接替换了
		arr[j] = tmp
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

插入排序的思想如下

image-20210128094237098

时间复杂度为o(n^2) 空间复杂度为o(1)

# 折半插入排序

image-20210128102903185

// 折半插入排序（这个不算10大排序算法）
// 时间复杂度为 n^2，为什么是n^2呢，外面这一层不必多说就是n
// 里面这层，虽然有两个for循环，但是实际情况下，这个执行的时间是随n线性变化的，所以也可以看成n
// 空间复杂度为 1 这里为什么不是3呢，因为我们这个空间复杂度反映的是一个趋势
// 无论我们的n是多大，我们始终只用了三个变量，所以空间复杂度为1
func bInsertSort(arr []int){
	var j = 0
	for i:=1;i<len(arr);i++{
		// 存储临时变量
		tmp := arr[i]
		// 赋值low和high，这里high等于i-1
		// 这里为什么i-1，因为我们最后计算的时候要确保low指针+1不会越界
		low,high,mid:=0,i-1,0
		// 我们使用指针来查找需要插入的位置
		for low <= high {
			mid = (low+high) /2
			if arr[mid] > tmp {
				high = mid - 1
			} else {
				low = mid + 1
			}
		}
		// 这里说一下为什么最后这个low就是我们应该放入的位置
		// low,high,mid的值是两个一组的，上一组是a[i]和a[mid]未经比较以前的，
		// 下一组是比较后，经过调整的。调整结果要么是low=mid+1，要么是high=mid-1。
		// 不知大家从上面的数据看出了什么。对！我们现在可以清楚的肯定：新元素的插入位置就是low。
		// 并且还发现high比low要小一，即high+1才与low相等。这是显然的，否则while循环如何结束。
		// 我想此刻大家的疑惑肯定是解开了。那么插入位置的写法就很随意了:low和high+1都行！
		// fmt.Println(low,mid,high)
		// 这里为什么要取low因为我们结束后j一定为是low，所以我们可以直接替换
		// 我也尝试过high不减一，low<high 但是就是调不出来，我也不知道为什么
		for j=i;j>low;j-- {
			arr[j] = arr[j-1]
		}
		arr[low] = tmp
	}
}
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

时间复杂度为o(n^2) 时间复杂度为O(1)

# 希尔排序

image-20210310105042665

也叫缩小增量排序，通过把整个待排序记录序列分割成几组，从而减少需要排序的数据量

image-20210310105238782

我们的代码如下：

// 希尔排序
// 时间复杂度 n^1.3 这个是别人试验验证的结果
// 空间复杂度 不随n变化就是1
func shellSort(arr []int) {
	// 首先我们就是要确定增量大小，默认情况下，我们取n=len(arr)/2，后面我们的增量就会不断的缩小
	for gap:=len(arr)/2;gap>0;gap/=2{
		// 确定好增量后我们就从gap开始,这里为什么是i等于gap呢，因为我们后面是j-gap，所以我们需要从这个增量开始计算
		for i:=gap;i<len(arr);i++{
			// 用一个变量来暂存i的位置
			j:=i
			// 这里就开始比较了，我们是从gap开始的，j-gap 是我们比的第二个数字，然后我们进行交换
			for j-gap>=0 && arr[j] < arr[j-gap] {
				// 如果发现右边大于左边的，我们就交换一下
				arr[j],arr[j-gap] = arr[j-gap],arr[j]
				// 这一步其实是优化，要不要都一样，我们这里就是确保后面排序后再给前面排序，加快排序速度
				j-=gap
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 交换排序

# 冒泡排序

// 冒泡排序
// 时间复杂度 n^2 因为我们用了两层循环，这种两层循环的一般都是n^2
// 空间复杂度 1 这个和上面一样，不解释
func bubbleSort(arr []int)  {
	flag:=true
	// 首先我们直接设置i，i表示当前未排序的区间最大值,同时为了避免重复比较，设置一个flag来进行标记
	for i:=len(arr)-1;i>0 && flag;i-- {
		// 把flag置为false，如果没有排序那么我们就退出循环
		flag = false
		// 然后我们只需要按顺序排好i前面的就行了
		for j:=0;j<i;j++ {
			// 冒泡排序是比较相邻两个位置的元素
			if arr[j] > arr[j+1] {
				// flag置为true表示已经排过序了
				flag = true
				// 交换
				arr[j+1],arr[j] = arr[j],arr[j+1]
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

算法思路如下

image-20210202102330722

算法特点

(1)稳定排序。

(2)可用于链式存储结构。

(3)移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时此算法不宜采用。

# 快速排序

快速排序(QuickSort) 是由冒泡排序改进而得的。在冒泡排序过程中， 只对相邻的两个记录进行比较，因此每次交换两个相邻记录时只能消除一个逆序。如果能通过两个(不相邻)记录的一次交换，消除多个逆序，则会大大加快排序的速度。快速排序方法中的一次交换可能消除多个逆序。

// 快速排序-返回枢纽位置并进行排序，传入一个low指针，一个high指针，然后给数组进行简单排序
// 这里我们的数组排序好后返回一个中间位置的指针
func partition(arr []int,low int,high int) int {
	// 一般情况下我们直接取low点作为枢纽，然后我们就要进行排序，把比low小的排左边，比low大的排右边
	tmp:=arr[low]
	// 当low大于high时我们的排序就已经好了,这个时候其实low就是high同时这个值为我们的枢纽
	for low < high {
		// 首先我们从high哪里往左遍历，找出第一个比tmp小的点
		for low < high && arr[high] >= tmp {
			high --
		}
		// 找到这个比tmp小的点后我们就替换过去，这个时候我们的high其实留了一个空
		arr[low] = arr[high]
		// 因为上面high有一个空，所以这时候我们就可以从low指针开始出发，找到一个比tmp大的
		for low < high && arr[low] <= tmp {
			low ++
		}
		// 找到后我们就可以替换了，这个时候我们就把high给替换了，此时low就没用了
		// 然后我们就可以进行下一轮比较了，然后我们可以继续把比tmp小的点放到low这里
		arr[high] = arr[low]
	}
	// fmt.Println(low,high)
	// 最后替换完后，low和high其实就指向同一个位置了，这时我们就可以把low换成tmp了
	arr[low] = tmp
	// 返回low指针
	return low
}

// 快速排序
// 时间复杂度 nlogn 这东西推导比较复杂
// 具体参考 https://www.zhihu.com/question/22393997
// 空间复杂度 最好情况nlogn（注意这个log以2为底），最坏情况就是n
func quickSort(arr []int,low int,high int)  {
	// 这里也要判断，要不然会堆栈溢出
	if low < high {
		// 给数组进行简单排序，同时留下一个mid位置的指针
		mid:=partition(arr,low,high)
		// 这里我们使用递归来分别递归左右两部分
		quickSort(arr,low,mid-1)
		quickSort(arr,mid+1,high)
	}
}
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

算法特点

(1)记录非顺次的移动导致排序方法是不稳定的。

(2)排序过程中需要定位表的下界和上界，所以适合用于顺序结构，很难用于链式结构。

(3)当n较大时，在平均情况下快速排序是所有内部排序方法中速度最快的一种，所以其适合初始记录无序、n较大时的情况。

# 选择排序

选择排序的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，按顺序放在已排序的记录序列的最后，直到全部排完为止。本节首先介绍一种简单选择排序方法，然后给出另一种改进的选择排序方法——堆排序。

# 简单选择排序

// 选择排序
// 时间复杂度 n^2 这个很简单，因为是for循环嵌套
// 空间复杂度为1 
func selectSort(arr []int){
	j:=0
	for i := 0; i < len(arr); i++ {
		// 记录最小值的位置
		min:=i
		// 找出最小的那个值，这里我们从i开始往后找，找到一个最小的
		for j=i+1;j<len(arr);j++{
			if arr[j] < arr[min]{
				min = j
			}
		}
		// 最小值进行替换一下
		arr[i],arr[min] = arr[min],arr[i]
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

image-20210203145740355

(1)就选择排序方法本身来讲，它是一种稳定的排序方法，但图8.6所表现出来的现象是不稳定的，这是因为上述实现选择排序的算法采用“交换记录”的策略所造成的，改变这个策略，可以写出不产生“不稳定现象”的选择排序算法。

(2)可用于链式存储结构。

(3)移动记录次数较少，当每一记录占用的空间较多时，此方法比直接插入排序快。

# 堆排序

堆排序(HeapSort) 是一种树形选择排序， 在排序过程中， 将待排序的记录[.] 看成是一根完全二叉树的顺序存储结构、利用完全二叉树中双亲结点和孩子结点之间的内在关系、在当前无序的序列中选择关键字最大(或最小)的记录。

堆的定义

堆要满足下面这样的条件

image-20210203160925522

堆可以看成完全二叉树

image-20210203161155273

堆排序的步骤

首先需要建初堆，建初堆的目的是将无序序列调整为堆，然后我们不断交换堆顶和堆最后一个元素，然后重新调整堆

筛选法调整堆的算法步骤如下

image-20210203162419868

建初堆的步骤如下

image-20210203162626056

// 建初堆
func createHeap(arr []int)  {
	// 这里我们使用筛选法来建初堆，我们依次把、[n/2],[n/2]-1,....,1的节点都调整为堆即可
	n := len(arr) - 1
	// 根据堆的性质，在完全二叉树中所有序号大于 [n/2]的节点都是叶子，
	// 所以我们只需要调整 1 - n/2 这个区间把这几个点调整为大根堆就行
	// 这里调整堆传入了一个开始点和结束点
	for i :=n/2;i>=0;i--{
		adjustHeap(arr,i,n)
	}
}

// 调整堆
func adjustHeap(arr []int,s int,m int)  {
	// 保存起始点的值作为临变量
	rc:=arr[s]
	// 我们使用筛选法来调整堆
	// 这里使用了堆的性质
	// 当 ki>=k2i 且 ki >= k2i+1 或 ki <=k2i 且 ki <= k2i+1
	for j:=2*s;j<=m;j*=2{
		if j<m && arr[j]<arr[j+1]{ j++ }
		if rc >= arr[j] { break}
		arr[s] = arr[j]
		s=j
	}
	arr[s] = rc
}

// 堆排序
// 时间复杂度 nlogn
// 这里耗时操作在于筛选和调整 筛选需要n-1次 然后n个节点的二叉树深度为logn +1
// 空间复杂度 1 因为只需要一个临时空间
func heapSort(arr []int)  {
	// 先建堆，保证初始的时候是一个堆
	createHeap(arr)
	// 开始进行for循环，进行堆排序
	for i:=len(arr)-1;i>0;i--{
		// 这里我们把最大的那个最后一个（这个指的是当前堆的最大一个）互换
		// 因为我们堆排序后0号是最大的
		arr[0],arr[i] = arr[i],arr[0]
		// 我们i号是最大的了，所以我们忽略i，从i-1开始进行调整
		adjustHeap(arr,0,i-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

利用了堆里面首部元素最大的特点

image-20210203163030143

# 归并排序

image-20210203163313449

// 合并表
// 注意这里我们arr2是一个空数组，然后arr1的low和mid是一个排好序的数组，mid+1和high也是一个排好序的数组
// 这个函数的作用就是把两个数组合并为一个数组，放入arr2中
func Merge(arr1 []int,arr2 []int,low int,mid int,high int)  {
	// 这里我们使用i和j来表示arr1数组的两部分，然后k就表示arr2数组的位置
	i,j,k:=low,mid+1,low
	// 只要有一个数组到头了，我们就介绍排序
	for i <= mid && j<=high {
		// 因为我们要合并两个数组，所以我们需要判断一下数组的两部分到底谁大
		if arr1[i] > arr1[j] {
			// 注意，k表示arr2的位置，然后j表示的是 mid+1 到high这个数组
			arr2[k] = arr1[j];k++;j++
		} else {
			// 注意，k表示arr2的位置，然后j表示的是 low 到mid 这个数组
			arr2[k] = arr1[i];k++;i++
		}
	}
	// 剩余部分因为已经是一个有序的数组了，所以我们直接按顺序加到arr2就行
	for i<=mid {
		arr2[k] = arr1[i];i++;k++
	}
	for j<=high {
		arr2[k] = arr1[j];j++;k++
	}
}

// 2-路归并排序
// 时间复杂度nlogn
// 空间复杂度 n 因为我们排序的时候需要申请n个空间来存储
func mSort(arr []int,arr2 []int,low int,high int)  {
	// 当low和high相等的时候，这个时候大小为1，我们直接放到arr2就行
	if low == high{
		arr2[low] = arr[low]
	} else {
		// 我们准备开始进行拆分,我们需要把我们的数组拆成两部分
		arr3:=make([]int,high+1)
		// 直接取mid作为数组的分界点
		mid:= (low + high) / 2
		// 首先我们把low和mid 进行排序并放入arr3中
		mSort(arr,arr3,low,mid)
		// 然后我们把mid+1和high 进行排序并放入arr3中
		mSort(arr,arr3,mid+1,high)
		// 最后我们得到的数组在arr3中已经排好序并分成了两部分
		// 因为arr2是一个空数组，所以我们把arr3再进行排序，最后就是合并为一个有序的表并放入arr2中
		Merge(arr3,arr2,low,mid,high)
	}
}
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

# 其他排序

# 计数排序

参考：漫画：什么是计数排序？-五分钟学算法 (cxyxiaowu.com) (opens new window)

这个算法不是基于元素比较，而是利用数组下标来确定元素的正确位置

假定我的的20个随机整数值如下：

9，3，5，4，9，1，2，7，8，1，3，6，5，3，4，0，10，9 ，7，9
1

我们可以确定最大值为10最小值为0，这样我们就建立一个大小为11的数组

image-20210311103052699

非常简单，让我们遍历这个无序的随机数列，每一个整数按照其值对号入座，对应数组下标的元素进行加1操作。比如第一个整数是9，那么数组下标为9的元素加1

image-20210311103146018

最终，数列遍历完毕时，数组的状态如下：

image-20210311103157084

有了这个“统计结果”，排序就很简单了。直接遍历数组，输出数组元素的下标值，元素的值是几，就输出几次：

0，1，1，2，3，3，3，4，4，5，5，6，7，7，8，9，9，9，9，10
1

通常，我们为了节省空间，需要确定一个最大值和最小值

image-20210311104347879

实际代码如下:

// 计数排序,这里我们传入一个数组，一个最小值，一个最大值
func countingSort(arr []int, minvalue, maxValue int){
	// 首先我们建立一个统计数组,为了节省空间我们直接取最大值和最小值的差+1的空间，这个时候最大值在最后一个，最小值在第一个
	count:=make([]int,maxValue-minvalue+1)
	// 遍历数组，统计出现的次数，注意我们计算的时候需要减minValue
	for _,v:=range arr{
		count[v-minvalue] ++
	}
	// 最后我们输出数组，这里我们使用i来标记arr数组
	i:=0
	// 遍历count
	for k,v:=range count{
		// 如果count数组为0那么就不管，如果不为0那么就为几，我们就输出几次
		if v!=0 {
			// 输出v次
			for j:=0;j<v;j++{
				arr[i] = minvalue + k
				i ++
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 桶排序

1.9 桶排序 | 菜鸟教程 (runoob.com) (opens new window)

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

  1. 在额外空间充足的情况下，尽量增大桶的数量
  2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

1. 什么时候最快

当输入的数据可以均匀的分配到每一个桶中。

2. 什么时候最慢

当输入的数据被分配到了同一个桶中。

image-20210311105443539

比如我们有下面这几个数组

[63,157,189,51,101,47,141,121,157,156,194,117,98,139,67,133,181,13,28,109]
1

我们分成5个桶，下面开始排序

  1. 找到数组中的最大值194和最小值13，然后根据桶数为5，计算出每个桶中的数据范围为(194-13+1)/5=36.4
  2. 遍历原始数据，(以第一个数据63为例)先找到该数据对应的桶序列Math.floor(63 - 13) / 36.4) =1，然后将该数据放入序列为1的桶中(从0开始算)
  3. 当向同一个序列的桶中第二次插入数据时，判断桶中已存在的数字与新插入的数字的大小，按从左到右，从小打大的顺序插入。如第一个桶已经有了63，再插入51，67后，桶中的排序为(51,63,67) 一般通过链表来存放桶中数据，但js中可以使用数组来模拟
  4. 全部数据装桶完毕后，按序列，从小到大合并所有非空的桶(如0,1,2,3,4桶)
  5. 合并完之后就是已经排完序的数据

image-20210311105823407

// 桶排序，这里我们传入一个最大值，还有一为个桶的数量
// 时间复杂度 为n+k
// 空间复杂度为 n+k
func sortBucket(arr []int,max int,num int) {
	// 创建桶，大小为我们传入桶的数量
	buckets := make([][]int,num)
	var index int
	// 遍历数组
	for _,v := range arr{
		// 分配桶 index = value * (n-1)/k 这里我们使用公式来确放入的位置
		index = v * (num-1) / max
		// 把我们的数字放入桶内
		buckets[index] = append(buckets[index],v)
	}
	// 桶内排序
	tmpPos := 0
	// 这里我们遍历每一个桶
	for k:=0; k < num; k++ {
		// 获取桶里面数据的长度
		bucketLen := len(buckets[k])
		// 如果我们这个桶大小为0，那么我们就对桶里面进行排序
		if bucketLen>0{
			// 使用插入排序对数组进行排序
			insertSort(buckets[k])
			// 我们把排序好的部分复制到数组中
			copy(arr[tmpPos:],buckets[k])
			// 数组位置加上桶的大小，开始保存下一个桶
			tmpPos +=bucketLen
		}
	}
}
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

# 基数排序

基数排序与桶排序、计数排序都用到了桶的概念，但对桶的使用方法上有明显差异：

  • 基数排序：根据键值的每位数字来分配桶；
  • 计数排序：每个桶只存储单一键值；
  • 桶排序：每个桶存储一定范围的数值；

基数排序按取数方向分为两种：从左取每个数列上的数，为最高位优先（Most Significant Digit first, MSD）；从右取每个数列上的数，为最低位优先（Least Significant Digit first, LSD）。下列以LSD为例。

基数排序步骤：

  • 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零
  • 从最低位开始，依次进行一次排序
  • 从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列
func radixSort(theArray []int,max int){
	// 因为前面我们获取了最大值，这里我们获取一下最大值的位数
	var count = 0
	for max % 10>0{
		max /= 10
		count++
	}
	// 给桶中对应的位置放数据
	for i:=0; i<count; i++ {
		// 根据不同的位数，我们来获取10的n次方，用于后面获取每位的值
		theData := int(math.Pow10(i))
		// 建立空桶
		bucket:=make([][]int,10)
		// 遍历数组
		for k:=0; k<len(theArray); k++{
			// 这里我们进行取余操作，目的是为了获取这个数组在每位上的值
			theResidue := (theArray[k]/theData) %10
			// 获取到了位数后我们直接放入对应的桶中
			bucket[theResidue] = append(bucket[theResidue],theArray[k])
		}

		// 一遍循环完之后需要把数组二维数据进行重新排序，比如数组开始是10 1 18 30 23 12 7 5 18 233 144 ，循环个位数
		// 循环之后的结果为10 30 1 12 23 233 144 5 7 18 18 ，然后循环十位数，结果为1 5 7 10 12 18 18 23 30 233 144
		// 最后循环百位数，结果为1 5 7 10 12 18 18 23 30 144 233
		var x = 0
		// 遍历我们的桶
		for p:=0; p<len(bucket); p++ {
			for q:=0; q<len(bucket[p]); q++ {
				// 这里按照桶的结构，按桶的顺序把桶里面的数据放入数组中
				if bucket[p][q]!=0 {
					theArray[x] = bucket[p][q]
					x++
				}else {
					break
				}
			}
		}
	}
}
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

# 动图展示

# 冒泡排序

img

# 选择排序

img

# 插入排序

img

# 希尔排序

归并排序

# 归并排序

img

img

# 快速排序

img

img

# 堆排序

img

img

# 计数排序

img

# 桶排序

img

# 基数排序

img

参考收集一波十大算法动态图 - 简书 (jianshu.com) (opens new window)

编辑 (opens new window)
上次更新: 2021/03/21, 20:50:06
查找算法

查找算法→

Theme by Vdoing | Copyright © 2021-2021 小游