十大排序算法

algorithm
Word count: 3.8k   |   Reading time≈ 17 min

介绍

今天开启我们的算法系列，争取说简单➕通俗易懂。
我们从经典的排序算法开始。学习十大排序算法。

排序算法可以分为两大类：基于比较的排序 and 不基于比较的排序。
基于比较的排序，是通过元素间的两两比较，来判断大小，继而排序。
不基于比较的排序，就是通过各种其他的方法，来让元素排序。

在表格中，上面的7种都是基于比较的排序算法。下3种是不基于比较的排序。

接下来我们一个一个的来仔细看。

1、冒泡排序（Bubble Sort）

首先，我们来说说最简单的冒泡排序。

大家可以想象一下，在小学的时候，第一节体育课，老师给我们按照身高排成一列。

就是相邻的两个同学比较一下身高，让后把高的放右边，矮的站左边。

冒泡排序就是这样，从左往右遍历，相邻的两个元素进行比较，大的放右边，小的放左边。

这样一次遍历之后，最右边的元素肯定是最大的。

再进行n次遍历，就可以把整个队列排好序了。

代码如下：

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
/**
 * 冒泡排序
 * <p>
 * 两次循环，相邻的两个元素比较，小的往前
 * <p>
 * O(n2)
 */
public class BubbleSort {

	public static class Solution {

		public int[] sort(int[] nums) {
			// 注意边界， 不用到最后一个
			for (int i = 0; i < nums.length - 1; i++) {
				for (int j = 0; j < nums.length - i - 1; j++) {
					if (nums[j] > nums[j + 1]) {
						SortUtil.swap(nums, j, j + 1);
					}
				}
			}
			return nums;
		}
	}

}

2、选择排序（Selection Sort）

选择排序思路也很简单，我们把队列分成两个部分。

一部分是乱序的，就是我们一开始的样子。

一部分是有序的。

我们先在乱序的队列里面找到一个最小的元素，放到有序的队列里面。

再在乱序的队列里面找一个最小的元素，依次放到有序队列里面。

直到乱序的队列里面一个元素都没有了。

这样，有序的队列就是我们最终的结果。

为了节省空间，我们可以在一个数组里面，存下这两个队列。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 选择排序， 每次循环找出最小值，往前面换
 */
public class SelectionSort {

	public static class Solution {

		public int[] sort(int[] nums) {
			int minIndex;
			for (int i = 0; i < nums.length - 1; i++) {
				minIndex = i;
				for (int j = i; j < nums.length; j++) {
					if (nums[j] < nums[minIndex]) {
						minIndex = j;
					}
				}
				SortUtil.swap(nums, i, minIndex);
			}
			return nums;
		}
	}

}

3、插入排序（Insertion Sort）

插入排序也很好理解。

相信大家都打过扑克牌，每次我们一开始摸牌都时候，都是一次插入排序都过程。

同样有两个队列，一个乱序，一个有序。

每次我们从乱序都队列里面拿出一张牌，再插入到有序队列里面合适到地方。

这就是插入排序。

请看代码：

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
/**
 * 插入排序， 找到一个元素，向前扫描，前面但往后移动，在合适但地方插入
 */
public class InsertionSort {

	public static class Solution {

		public int[] sort(int[] nums) {
			if (nums.length < 2) {
				return nums;
			}
			// 1   3   2
			//     j   i
			// 1   2   3
			// j       i
			for (int i = 1; i < nums.length; i++) {
				int indexValue = nums[i];
				// 往左扫描
				for (int j = i - 1; j >= 0; j--) {
					// 如果indexValue比较小，j往右移动
					// 同时把 i的值填充进去
					if (indexValue < nums[j]) {
						nums[j + 1] = nums[j];
						nums[j] = indexValue;
					} else {
						// 已经找到比当前小的了， 跳出此轮循环
						break;
					}
				}
			}
			return nums;
		}
	}

}

4、希尔排序（Shell Sort）

希尔排序，顾名思义，它是一个名叫希尔的人发明的，第一个个时间复杂的图片O(n2)排序。

它是插入排序的一个变种，但是它的实现相对复杂。

为了帮助大家理解，我们先看一下插入排序的动图。

大家有没有发现，每一次插入的过程，基本上都要移动好几个元素。大小相似的元素往往相隔的比较远。

为了优化这个过程，希尔选择了先把整个队列按照间隔分组，分别进行插入排序。

然后间隔原来越小，当间隔为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
/**
 * 希尔排序：
 * 1 按照间隔分组（初始间隔一般是数组长度的一半）
 * 2 排序每个组（插入排序法）
 * 3 间隔减小，重新分组（新的间隔一般为原间隔的一般，最后为1）
 * 4 再排序每个组
 */
public class ShellSort {

	public static class Solution {

		public int[] sort(int[] nums) {
			int interval = nums.length / 2;
			while (interval > 0) {
				insertSortByInterval(nums, interval);
				interval = interval / 2;
			}
			return nums;
		}

		private void insertSortByInterval(int[] nums, int interval) {
			for (int i = 0; i < interval; i++) {
				for (int j = i + interval; j < nums.length; j += interval) {
					insertSortByInterval(nums, j, interval);
				}
			}
		}

		//  0  x  x  2  x  x  3  x  x  1  x  x
		//                    i        s
		private void insertSortByInterval(int[] nums, int startIndex, int interval) {
			int value = nums[startIndex];
			int i = startIndex - interval;
			while (i >= 0 && nums[i] > value) {
				nums[i + interval] = nums[i];
				nums[i] = value;
				i -= interval;
			}
		}
	}

}

5、归并排序（Merge Sort）

如果你是程序员的化，归并排序也很好理解。

它主要采用分治的思想，使用递归。 化繁为简。

直接上代码：

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
/**
 * 归并排序
 */
public class MergeSort {

	public static class Solution {

		public int[] sort(int[] nums) {
			return mergeSort(nums);
		}

		// 递归方法
		private int[] mergeSort(int[] nums) {
			// 递归出口
			if (nums.length < 2) {
				return nums;
			}
			// 分成两个数组
			int m = nums.length / 2;
			int[] left = Arrays.copyOfRange(nums, 0, m);
			int[] right = Arrays.copyOfRange(nums, m, nums.length);
			// 对这两个数组做排序
			left = mergeSort(left);
			right = mergeSort(right);
			// 合并这两个排序好的数组
			return mergeSort(left, right);
		}

		// 对两个排序好的数组做合并
		private int[] mergeSort(int[] left, int[] right) {
			int length = left.length + right.length;
			int[] merged = new int[length];
			int leftIndex = 0, rightIndex = 0;
			for (int i = 0; i < length; i++) {
				if (leftIndex < left.length && rightIndex < right.length) {
					int leftValue = left[leftIndex];
					int rightValue = right[rightIndex];
					if (leftValue < rightValue) {
						merged[i] = leftValue;
						leftIndex++;
					} else {
						merged[i] = rightValue;
						rightIndex++;
					}
				} else if (leftIndex >= left.length) {
					merged[i] = right[rightIndex];
					rightIndex++;
				} else {
					merged[i] = left[leftIndex];
					leftIndex++;
				}
			}
			return merged;
		}
	}

}

动图如下：

6、快速排序（Quick Sort）

重点！ 重点～ 重点。。。
快速排序非常重要‼️

它的思想是：设立一个基准，把小于基准的移动到左边，把大于基准的移动到右边。

在把左边小于基准的子队列，再设立一个基准，再移动，右边同理。

使用递归，直至子队列的长度小于2。

先来个带辅助空间的快速排序的实现，很简单，大家体会下。

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
/**
 * 使用List，带辅助空间
 */
public static class Solution {

	public int[] sort(int[] nums) {
		List<Integer> list = quickSort(
				Arrays.stream(nums).boxed().collect(Collectors.toList()));
		return list.stream().mapToInt(i -> i).toArray();
	}

	// 快速排序递归方法
	private List<Integer> quickSort(List<Integer> list) {
		// 递归出口
		if (list.size() < 2) {
			return list;
		}
		// 随便找一个基准，这里取的是第一个元素
		Integer pivot = list.get(0);
		
		// 辅助空间
		List<Integer> low = new ArrayList<>();
		List<Integer> high = new ArrayList<>();
		List<Integer> equal = new ArrayList<>();
		
		// 结果集合
		List<Integer> sorted = new ArrayList<>();
		
		// 大于基准的集合；小于基准的集合；等于基准的集合
		for (Integer item : list) {
			if (item.equals(pivot)) {
				equal.add(item);
			} else if (item < pivot) {
				low.add(item);
			} else {
				high.add(item);
			}
		}
		// 递归
		low = quickSort(low);
		high = quickSort(high);
		
		// 合并
		sorted.addAll(low);
		sorted.addAll(equal);
		sorted.addAll(high);
		return sorted;
	}
}

不带辅助空间的算法实现起来比较复杂，但是思想一致。

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
// in-place
public static class Solution2 {

	public int[] sort(int[] nums) {
		sort(nums, 0, nums.length - 1);
		return nums;
	}

	private void sort(int[] nums, int left, int right) {
		if (left >= right) {
			return;
		}
		int pivotIndex = pivotDivision(nums, left, right);

		sort(nums, left, pivotIndex - 1);
		sort(nums, pivotIndex + 1, right);
	}

	// 按照基准  左右划分
	// 3  2  6  5  4
	// 3  2  4  6  5
	private int pivotDivision(int[] nums, int left, int right) {
		// 默认给最右边的值 为基准
		int pivot = nums[right];
		// 初始化，基准Index
		int pivotIndex = left;
		// 把子数组遍历一遍
		for (int i = left; i < right; i++) {
			// 如果比 基准小  替换到前面  基准Index++
			if (nums[i] <= pivot) {
				SortUtil.swap(nums, i, pivotIndex);
				pivotIndex++;
			}
		}
		// 最后再把 基准放到中间来
		SortUtil.swap(nums, right, pivotIndex);

		return pivotIndex;
	}
}

最后我们看下动图：
黄色的元素是基准

7、堆排序（Heap Sort）

堆排序，就比较不好想了，它的思路是把数组转换成二叉树。对，没错。

把数组当成一个二叉树。

然后对二叉树进行递归比较，把较大对元素放到根节点。

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
public class HeapSort {

	/**
	 * 1. 把数组抽象成二叉树
	 * <p>
	 * 2. 每个子树做堆化操作，比较根元素和子元素，交换位置，保持根元素最大
	 * <p>
	 * 3. 循环，保持整棵树的根元素最大
	 * <p>
	 * 4. 把根元素放到最后
	 */
	public static class Solution {

		// 7  6  5  2  3  4  1
		//          7
		//         /  \
		//        5    2
		//       / \  /
		//      3  4  1
		//  左边叶子节点的位置 = 根节点的位置 * 2 + 1
		//  右边叶子节点的位置 = 根节点的位置 * 2 + 2
		public int[] sort(int[] nums) {
			for (int i = nums.length - 1; i >= 0; i--) {
				// 堆化
				heapify(nums, i);
				// 此时root已经最大，把root移动到后面
				SortUtil.swap(nums, 0, i);

			}
			return nums;
		}

		// 从后往前比较每一个节点
		// 类似一个冒泡的过程，把最大的值给冒上来
		private void heapify(int[] nums, int i) {
			for (int j = i; j >= 0; j--) {
				checkRootValueBeMax(nums, j, i);
			}
		}

		// 保证根节点 元素最大  左边节点，第二大   右边节点最小
		private void checkRootValueBeMax(int[] nums, int rootIndex, int limit) {
			int leftIndex = rootIndex * 2 + 1;
			int rightIndex = rootIndex * 2 + 2;

			if (leftIndex < limit && nums[leftIndex] > nums[rootIndex]) {
				SortUtil.swap(nums, leftIndex, rootIndex);
			}
			if (rightIndex < limit && nums[rightIndex] > nums[rootIndex]) {
				SortUtil.swap(nums, rightIndex, rootIndex);
			}
			if (leftIndex < nums.length &&
					rightIndex < nums.length &&
					nums[leftIndex] > nums[rightIndex]) {
				SortUtil.swap(nums, leftIndex, rightIndex);
			}
		}
	}

}

动图如下：

8、计数排序（Counting Sort）

从这种排序算法开始，后面3种算法，就都是不依靠比较的排序算法了。

计数排序就是其中之一。

计数排序的核心，就是定义一个计数数组，记录每个数出现的次数。

如果有一个待排序的数组如：[ 5, 3, 3, 2, 6, 7, 8, 9, 0, 4 ]，最大值为10。

那么我们的计数数组填充完毕后的样子就是：[ 1, 0, 1, 2, 1, 1, 1, 1, 1, 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
// 计数排序
public class CountingSort {

	public static class Solution {

		// [ 5, 3, 3, 2, 6, 7, 8, 9, 0, 4 ]   , 10
		public int[] sort(int[] nums, int maxValue) {

			// 定义计数数组
			int[] countingArray = new int[maxValue];

			// 把 nums 存放到计数数组中
			// [ 1, 0, 1, 2, 1, 1, 1, 1, 1, 1 ]
			for (int value : nums) {
				int count = countingArray[value];
				countingArray[value] = count + 1;
			}

			int numsIndex = 0;
			// 再把计数数组中的数据 反哺到nums中
			for (int i = 0; i < countingArray.length; i++) {
				int count = countingArray[i];
				for (int j = 0; j < count; j++) {
					nums[numsIndex] = i;
					numsIndex++;
				}
			}

			return nums;
		}
	}
}

9、桶排序（Bucket Sort）

大家学过了计数排序，有没有发现一个问题，如果数组中元素的大小跨越的过大的化，所需要的计数数组的大小就越大。非常浪费空间。

为了优化这个问题，随之诞生的桶排序可以很好的解决这个问题。

它的数据结构类似与Java中的HashMap，图解如下：

它的思想也是定义一个数组，数组的每一个位置当成一个桶，

但是每一个位置里面可以有很多元素。

再对每一个桶进行排序。

最后，通过这个桶数组，生成一个排好序的数组作为结果。

代码如下：

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
// 桶排序
// 1、 定义桶
// 2、 按桶，对数组分组
// 3、 对每个桶进行排序
// 4、 组合每个桶
public class BucketSort {

	public static class Solution {

		public int[] sort(int[] nums) {

			// 1、 定义桶
			int maxValue = nums[0], minValue = nums[0];
			for (int v : nums) {
				maxValue = Math.max(maxValue, v); // 47
				minValue = Math.min(minValue, v); // 1
			}

			// 桶对数量（不重要，大概就行）
			int bucketCount = (int) Math.sqrt(nums.length); // 8
			List<Integer>[] buckets = new List[bucketCount];
			// 2、 按桶，对数组分组
			for (int v : nums) { // v =15
				// 找到对应对桶，这点要注意
				int bucketIndex = v * (bucketCount - 1) / maxValue;
				List<Integer> bucket = buckets[bucketIndex];
				if (bucket == null) {
					bucket = new ArrayList<>();
					bucket.add(v);
					buckets[bucketIndex] = bucket;
				} else {
					bucket.add(v);
				}
			}
			// 3、 对每个桶进行排序
			for (List<Integer> bucket : buckets) {
				Collections.sort(bucket);
			}
			// 4、 组合每个桶
			return Arrays.stream(buckets).flatMap(Collection::stream)
					.mapToInt(Integer::intValue).toArray();
		}
	}

}

10、基数排序（Radix Sort）

基数排序对于桶排序来说，也是换汤不换药。

同样有一个桶数组，但是这个数组的长度固定，只有10。

通过从低位到最高位的循环，每次循环都做一次桶排序。

最终就会得到一个排序好的数组。

这种算法占用的额外空间更小，也更可控。

动图如下：

思想很简单。

请看代码

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
/**
 * 基数排序
 * <p>
 * 取得数组中的最大数，并取得位数；
 * <p>
 * arr为原始数组，从最低位开始取每个位组成radix数组；
 * <p>
 * 对radix进行计数排序（利用计数排序适用于小范围数的特点）；
 */
public class RadixSort {

	public static class Solution {

		public int[] sort(int[] nums) {

			//取得数组中的最大数，并取得位数
			int digit = getBiggestDigit(nums);

			// i=1表示个位； i=2表示十位 ......
			for (int i = 1; i <= digit; i++) {
				// 每一个位置都过一下桶数组
				bucket(nums, i);
			}

			return nums;
		}

		// i=1表示个位； i=2表示十位 ......
		private void bucket(int[] nums, int i) {
			List<Integer>[] buckets = new List[10];
			// 把数组，放置到桶中
			for (int n : nums) {
				// 获取对应位数的数值
				int pos = getPosition(n, i);
				List<Integer> list = buckets[pos];
				if (list == null) {
					list = new ArrayList<>();
					buckets[pos] = list;
				}
				list.add(n);
			}
			// 再把桶中到数据，恢复到原数组中
			int index = 0;
			for (List<Integer> bucket : buckets) {
				if (CollectionUtils.isNotEmpty(bucket)) {
					for (Integer v : bucket) {
						nums[index] = v;
						index++;
					}
				}
			}
		}

		// 获取对应位数的数值
		private int getPosition(int n, int digit) {
			String s = String.valueOf(n);
			// 33   2
			if (s.length() < digit) {
				return 0;
			}
			return Integer.parseInt(s.substring(s.length() - digit, s.length() - digit + 1));
		}

		// 取得数组中的最大数，并取得位数
		private int getBiggestDigit(int[] nums) {
			int maxDigit = 0;
			for (int num : nums) {
				int d = String.valueOf(num).length();
				maxDigit = Math.max(maxDigit, d);
			}
			return maxDigit;
		}
	}

}

总结

至此，我们的十大排序算法就学习完了。

希望大家都有所收获。

其中最重要的当属 快速排序 了，两种快速排序算法，大家一定要好好掌握。

还有希尔排序，也比较难想，需要大家好好理解。

结束！！！

  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2020-2022 chengpeng
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信