GitHub Repo：Sort Article
Follow: MisterBooo · GitHub
排序算法可以分为内部排序和外部排序。
内部排序是数据记录在内存中进行排序。
而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。
常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。
用一张图概括：
平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。
线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；
O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序
线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。
关于稳定性：
稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。
不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。
1. 冒泡排序 1.1 算法步骤
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
1.2 动画演示
2public class BubbleSort implements IArraySort {
3
4 @Override
5 public int[] sort(int[] sourceArray) throws Exception {
6 // 对 arr 进行拷贝，不改变参数内容
7 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
8
9 for (int i = 1; i < arr.length; i++) {
10 // 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
11 boolean flag = true;
12
13 for (int j = 0; j < arr.length - i; j++) {
14 if (arr[j] > arr[j + 1]) {
15 int tmp = arr[j];
16 arr[j] = arr[j + 1];
17 arr[j + 1] = tmp;
18
19 flag = false;
20 }
21 }
22
23 if (flag) {
24 break;
25 }
26 }
27 return arr;
28 }
29}
2. 选择排序 2.1 算法步骤
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。
2.2 动画演示
2public class SelectionSort implements IArraySort {
3
4 @Override
5 public int[] sort(int[] sourceArray) throws Exception {
6 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
7
8 // 总共要经过 N-1 轮比较
9 for (int i = 0; i < arr.length - 1; i++) {
10 int min = i;
11
12 // 每轮需要比较的次数 N-i
13 for (int j = i + 1; j < arr.length; j++) {
14 if (arr[j] < arr[min]) {
15 // 记录目前能找到的最小值元素的下标
16 min = j;
17 }
18 }
19
20 // 将找到的最小值和i位置所在的值进行交换
21 if (i != min) {
22 int tmp = arr[i];
23 arr[i] = arr[min];
24 arr[min] = tmp;
25 }
26
27 }
28 return arr;
29 }
30}
3. 插入排序 3.1 算法步骤
将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。