手撕十大排序算法（一）

前言

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

本文主要讲述冒泡排序和选择排序的原理和实现，并对两者进行一个简单的比较。

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

冒泡排序

冒泡排序用一句话来总结就是：从左至右，对数组中相邻的两个元素进行比较，将较大的放到后面，具体流程如下图。

如上，假设有一个数组：[5, 3, 2, 4, 1]，一开始两两互换，可以看到最大的数会被置换到最右边（所以下一轮不用再跟它比较），而小的数则会慢慢往左边靠拢，以此类推。

冒泡排序有两种实现方式，这两种方式的最优和最坏的时间复杂度不同。

冒泡实现一

// 冒泡排序实现方式一
// 从小到大：将最大值一直挪到最右边
func bubbleSort1(arr []int) []int {
	n := len(arr)
	for i := 0; i < n-1; i++ {
		// k < n-1-i：后面的数不用再比较
		for k := 0; k < n-1-i; k++ {
			if arr[k] > arr[k+1] {
				arr[k], arr[k+1] = arr[k+1], arr[k]
			}
		}
	}
	return arr
}

总结：这种是比较常见的冒泡排序，由两个for循环构成，所以平均、最优、最坏时间复杂度都为O（n2n^2n2），而由于上述解法并没有用到其他数据结构存储，所以空间复杂度为O（1）。

冒泡实现二

func bubbleSort2(arr []int) []int {
	n := len(arr)
	for i := 0; i < n-1; i++ {
		flag := 0 // 可替换为布尔值
		for k := 0; k < n-1-i; k++ {
			if arr[k] > arr[k+1] {
				arr[k], arr[k+1] = arr[k+1], arr[k]
				flag += 1
			}
		}
		// 当遍历了一遍，flag仍然为0，说明原数组本身有序，所以不用再遍历，复杂度为O(n)
		if flag == 0 {
			break
		}
	}
	return arr
}

总结：这种是改良过的冒泡排序，最坏时间复杂度为O（n2n^2n2），当数组本身有序的情况下，最优时间复杂度为O（n）

选择排序

选择排序用一句话来总结就是：从第一个位置开始，与后面的数进行比较，找出最小的，并和第一个位置互换（从而最小的数都会在最左边）。

如上，假设有一个数组：[5, 3, 2, 4, 1]，一开始拿第一个数跟剩余的数字的进行比较，可以将最小的数字移动到最左边，接着第二轮又把第二小的数字移动到左边，以此类推。

代码实现如下：

func selectSort(arr []int) []int {
	n := len(arr)
	for i := 0; i < n; i++ {
		// k=i+1，表示下一个数
		for k := i + 1; k < n; k++ {
			if arr[i] > arr[k] {
				arr[i], arr[k] = arr[k], arr[i]
			}
		}
	}
	return arr
}

总结：选择排序的平均、最坏、最优复杂度都是O（n2n^2n2），因为遍历一次只能知道哪个数最小，无法节省遍历次数，所以最坏最优都是O（n2n^2n2），同样由于没有利用其它数据结构，所以空间复杂度为O（1）。

冒泡排序 VS 选择排序

之前的我，对冒泡排序和选择排序有点傻傻分不清，经过最近的整理，总结出它们的几点区别：

1.比较方式不同：冒泡排序是相邻比较，选择排序是第一个数与其他数进行比较，具体如下：

如果还是不清楚，可以将图一和图二放在一起比较，就会更容易理解。

2.时间复杂度不同：在特殊的情况下，冒泡排序可以达到O(n)的复杂度；而选择排序的复杂度永远为O(n2)

3.冒泡排序是稳定排序，选择排序是非稳定排序。以一个数组 [4, 6, 4, 3, 3] 为例，在第一轮比较的时候，我们知道第一个4会和第一个3交换位置，从而原数组中2个4的前后顺序就被破坏了，所以选择排序不是稳定排序算法。

写在最后

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