盘一盘常见的排序算法

发表于 分类于

对常见的以及一些高级的排序算法的总结：

  • 冒泡排序
  • 选择排序
  • 插入排序
  • 快速排序
  • 归并排序
  • 桶排序
  • 基数排序
  • 希尔排序

冒泡排序 BubbleSort

每一轮遍历，两两交换，将最大的放到最后面。

排序是稳定的，没有改变相同大小的元素的相对位置。

时间复杂度

对于有 n 个元素的区间，每一轮遍历，都能确定一个最大的数。交换次数为 n-1。

则总的交换次数为 1 + 2 + ··· + (n-1)，时间复杂度为 $O(n^2)$。

优化

  1. 设置一个标志位，记录这一轮遍历有没有发生交换。如果没有交换就意味着已经排好序了
  2. 记录某一轮遍历中，最后发生交换的位置。下次遍历时到这个位置就可以结束了，因为后面的已经有序了

代码示例（Go）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
package main

func BubbleSort(arr []int) {
	length := len(arr)
	
	for i := length-1; i > 0; i-- {
		for j := 0; j < i; j++ {
			if arr[j] > arr[j+1] {
				swap(arr, j, j+1)
			}
		}
	}
}

func swap(arr []int, i, j int) {
	temp := arr[i]
	arr[i] = arr[j]
	arr[j] = temp
}

选择排序 SelectSort

每一轮遍历找出一个最小的，放在最前面。

它和冒泡不一样的冒泡是相邻的两两交换，把最大的或者最小的换到终点。而它是找到最小的之后直接和终点元素交换，所以这种算法排序不稳定。

时间复杂度

最好的情况就是数组本来就是有序的，此时只会发生比较而不会交换。

和冒泡排序一样，时间复杂度为 $O(n^2)$。

优化

每一轮遍历选出最小和最大的，这样就可以减少一半的遍历次数。

示例代码（Go）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package main

func SelectSort(arr []int) {
	length := len(arr)
	
	for i := 0; i < length; i++ {
		k := i
		for j := i; j < length; j++ {
			if arr[j] < arr[k] {
				k = j
			}
		}
		
		swap(arr, i, k)
	}
}

func swap(arr []int, i, j int) {
	temp := arr[i]
	arr[i] = arr[j]
	arr[j] = temp
}

插入排序 InsertSort

插入排序就是遍历过的都是有序的，然后把正在遍历的元素插入到遍历过的有序的数组里面。

稳定。

时间复杂度

最好的情况就是数组本身就是有序的，这种情况不会发生任何交换，只需要遍历一次就可以，时间复杂度为 $O(n)$。

最坏的情况就是数组完全倒序，每一次都需要将当前元素移动到数组头部，所以时间复杂度是 1 + 2 + ··· + (n-1)，也就是 $O(n^2)$。

优化

查找的时候使用二分查找。

示例代码（Go）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package main

func InsertSort(arr []int) {
	length := len(arr)
	
	for i := 0; i < length; i++ {
		if i == 0 {
			continue
		}
		
		j := i
		temp := arr[i]
		
		for ; j > 0; j-- {
			if temp < arr[j-1] {
				arr[j] = arr[j-1]
			} else {
				break
			}
		}
		
		arr[j] = temp
	}
}

快速排序

堆并排序

桶排序

基数排序

希尔排序