likes
comments
collection
share

手撕十大排序算法（二）

作者站长头像
站长
· 阅读数 3

前言

十大排序包含：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序（快排）、桶排序、计数排序、基数排序以及堆排序。

本文主要讲述插入排序和希尔排序的原理和实现，并对两者进行一个简单的比较。

注：本文代码采用Golang实现。

插入排序

插入排序有点像我们斗地主时，对手中的牌进行排序的过程。

手撕十大排序算法（二）

还是以数组 [5, 3, 2, 4, 1] 为例，可以将其看做5张牌：

  • 1.一开始拿到数字5，没有人和它比较，所以它放在最左边
  • 2.接着拿到数字3，和5做比较，发现比5小，所以手中的牌变成 [3, 5]
  • 3.接着拿到数字2，和5比较后交换，然后和3比较，也交换，所以手中的牌变成 [2, 3, 5]
  • 4.接着拿到数字4和数字1，以此类推

可以看到，插入排序是将一个值插入到一个已经排好序的数组，并一直持续到所有值插入完毕，最终得到一个新的有序数组。

这里也列举插入排序的两种实现方式，最坏最优时间复杂度也不同。

插入排序实现一

func insertSort1(arr []int) []int {
	n := len(arr)
	for i := 1; i < n; i++ {
		idx := i
		for idx > 0 {
			if arr[idx] < arr[idx-1] {
				arr[idx], arr[idx-1] = arr[idx-1], arr[idx]
			}
			// 通过这里，我们可以看到插入排序是往后比较的
			idx -= 1
		}
	}
	return arr
}

总结：上述为插入排序的常规写法，最优时间复杂度和最坏时间复杂度为O（n2n^2n2），空间复杂度为O（1）

插入排序实现二

func insertSort2(arr []int) []int {
	n := len(arr)
	for i := 1; i < n; i++ {
		idx := i
		for idx > 0 {
			if arr[idx] < arr[idx-1] {
				arr[idx], arr[idx-1] = arr[idx-1], arr[idx]
				idx -= 1
				// 当要插入的值，比排好序的数组的最后一个值大，则不用再比较
			} else {
				break
			}
		}
	}
	return arr
}

总结：插入排序的一种优化实现，最坏时间复杂度为O（n2n^2n2），当数组本身有序的情况下，最优时间复杂度为O(n), 有点类似冒泡排序，空间复杂度为O（1）。

希尔排序

希尔排序是插入排序的一种，又称缩小增量排序，它是直接插入排序算法的一种更高效的改进版本。

根据上文，其实我们知道，插入排序在数组本身有序的情况下，时间复杂度其实可以达到O（n），具体实现参见上文的第二种实现。

而希尔排序，其实就是通过分组，加快数组从无序到有序的进程，从而减少直接插入排序的时间复杂度。

那么希尔排序的算法流程是怎样的呢，可以参照下面这张图：

手撕十大排序算法（二）

假设我们有一个数组：[5, 3, 2, 4, 1, 10, 7, 8, 6, 9]：

第一轮，我们通过数组长度除以2得到5，即这10个数会被分为5组，每一小组我们都通过直接插入排序进行排序，最终得到[5, 3, 2, 4, 1, 10, 7, 8, 6, 9]。（因为刚好前面的数都小于后面的数，所以数组顺序并没有变）

第二轮，我们通过5除以2得到2（新一轮的增量），即这10个数会被分为2组，每一组继续通过直接插入排序进行排序，最终得到[1, 3, 2, 4, 5, 8, 6, 9, 7, 10]

第三轮，我们通过2除以2得到1（最后一轮的增量都是1），即这10个数会被分为1组，通过排序后得到[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]，排序完成。

代码实现如下：

// 希尔排序实现一
func shellSort1(arr []int) []int {
	// 第 1 层循环：得到每一次的增量，即哪些数在同一组
	for gap := len(arr) / 2; gap > 0; gap /= 2 {
		// 第 2、3 层循环，对每一个增量中的每一组进行直接插入排序
		for i := gap; i < len(arr); i++ {
			for k := i - gap; k >= 0; k -= gap {
				// 左边的数大于右边的数，则交换位置
				if arr[k] > arr[k+gap] {
					arr[k], arr[k+gap] = arr[k+gap], arr[k]
				}
			}
		}
	}
	return arr
}

关于希尔排序，其实还有一种比较普遍的实现方式，与上述的代码区别在于增量函数的不同（使用的是 h=3*h + 1）：

func shellSort2(arr []int) []int {
	// 增量公式：h = 3*h + 1
	h := 1
	for h <= len(arr)/3 {
		h = h*3 + 1
	}
	// gap = (gap - 1) / 3  ==>  3gap + 1 = gap
	for gap := h; gap > 0; gap = (gap - 1) / 3 {
		// 第 2、3 层循环，对每一个增量中的每一组进行直接插入排序
		for i := gap; i < len(arr); i++ {
			for k := i - gap; k >= 0; k -= gap {
				// 左边的数大于右边的数，则交换位置
				if arr[k] > arr[k+gap] {
					arr[k], arr[k+gap] = arr[k+gap], arr[k]
				}
			}
		}
	}
	return arr
}

2、关于时间复杂度O（nlog2log_2log2​n）是怎么来的，我其实也不是很懂，比如以希尔排序实现一为例，可以看到有三层循环，第一层是一个不断二分的过程，所以可以得到复杂度为O（log2log_2log2​n），但这样的话第二、三层循环的复杂度就得为O（n），这是我一个不是很理解的地方，希望有大神能在评论区解答！！

关于稳定性： 希尔排序是一个不稳定的算法，因为通过分组，会打乱原有顺序，可以通过推导[5, 8, 6, 5, 4, 2, 3, 8, 6, 9]得到结论

手撕十大排序算法（二）

写在最后

本文如有错漏，麻烦在评论区指出，言某感激不尽，另外，如果本文对你有用，还麻烦客官们点个小小的爱心💖！

转载自:https://juejin.cn/post/6994472649082535972
评论
请登录