O(n²)的三个排序算法
今天复习下最简单的三个排序算法，一个是选择排序，一个是插入排序，一个是冒泡排序，三者时间复杂度都是O(n²)，通过分析来发现三者的优劣，以及对最好的情况和最坏的情况进行分析。 另外，这三中排序算法都是基于比较的排序算法。基于比较的排序算法的执行过程，会涉及两种操作，一种是元素比较大小，另一种是元素交换或移动。所以，如果我们在分析排序算法的执行效率的时候，应该把比较次数和交换（或移动）次数也考虑进去。
一、选择排序 SelectionSort
选择排序是一种简单直观的排序算法，工作原理为：在未排序的序列中找出最小(大)元素与第一个位置的元素交换位置，原理如下图所示：
选择排序的静态图：
1public static void selectSort(int[] arr) {
2 for (int i = 0; i < arr.length; i++) {
3 int tmp;
4 //寻找[i,n]之间的最小值
5 int minIndex = i;
6 for (int j = i+1; j < arr.length; j++) {
7 if(arr[j] < arr[minIndex]){
8 minIndex = j;
9 }
10 }
11 tmp = arr[i];
12 arr[i] = arr[minIndex];
13 arr[minIndex] = tmp;
14 }
15}
稳定性
选择排序是一种不稳定的排序算法。 从图中可以看出来，选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。
最好和最坏情况
选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为O(n²)
二、插入排序 InsertionSort
首先，我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。
静态图展示
1public static void execSort(int[] arr) {
2 int tmp;
3 for (int i = 1; i < arr.length; i++) {
4 //寻找元素arr[i]合适的插入位置
5 for (int j = i; j > 0; j--) {
6 if(arr[j] < arr[j-1]){
7 tmp = arr[j];
8 arr[j] = arr[j-1];
9 arr[j-1] = tmp;
10 }else {
11 //到这里说明前面的所有元素已经比当前值小了，没有继续比较的必要了
12 break;
13 }
14 }
15 }
16}
换个比较简洁的写法：
1//更简洁的写法：替换上面的break
2public void execSort(int[] arr) {
3 int tmp;
4 for (int i = 1; i < arr.length; i++) {
5 //寻找元素arr[i]合适的插入位置
6 for (int j = i; j > 0 && arr[j] < arr[j-1]; j--) {
7 tmp = arr[j];
8 arr[j] = arr[j-1];
9 arr[j-1] = tmp;
10 }
11 }
12}
插入排序的改进
1public static void insertionSortOptimize(int[] arr){
2 for (int i = 0; i < arr.length; i++) {
3 int e = arr[i];
4 int j; //用来保存元素e应该插入的位置
5 for (j = i; j > 0 && arr[j-1] > e; j--) {
6 arr[j] = arr[j-1];
7 }
8 arr[j] = e;
9 }
10}
插入排序和选择排序的对比
其实我们很容易发现选择排序的最致命的缺点就是两层for循环需要完全走完才能完成排序，而插入排序则不需要。所以选择排序在任何情况下都是比较慢的。插入排序则不同，最坏的情况下（其实就是逆序了）才是O(n²)，如果是已经有序，或者大部分有序，还是非常快的，比如在我自己的电脑上排一亿个有序的数，才0.035s，这种速度比n*Log(n)的排序算法性能还高，至于选择排序的话我等了1分钟还没排出来，直接stop了。
**所以O(n²)级别的排序算法并非一无是处！**下面我们看看冒泡排序吧！
稳定性
在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。
最好和最坏情况
上面已经说过了，如果要排序的数据已经是有序的，我们并不需要搬移任何数据。如果我们从尾到头在有序数据组里面查找插入位置，每次只需要比较一个数据就能确定插入的位置。所以这种情况下，最好是时间复杂度为 O(n)
如果数组是倒序的，每次插入都相当于在数组的第一个位置插入新的数据，所以需要移动大量的数据，所以最坏情况时间复杂度为 O(n²)。
三、冒泡排序 BubbleSort
冒泡排序也属于一种典型的交换排序，交换排序顾名思义就是通过元素的两两比较，判断是否符合要求，如过不符合就交换位置来达到排序的目的。冒泡排序名字的由来就是因为在交换过程中，类似水冒泡，小（大）的元素经过不断的交换由水底慢慢的浮到水的顶端。
如果用静态图来展示的话就是这个样子：
1public static void bubbleSort(int[] arr) {
2 for (int i = 0; i < arr.length; i++) {
3 for (int j = 0; j < arr.length - i - 1; j++) {
4 if(arr[j] > arr[j+1]){
5 int tmp = arr[j];
6 arr[j] = arr[j+1];
7 arr[j+1] = tmp;
8 }
9 }
10 }
11}
优化版本定义一个标志位用来表示当前第i趟是否有交换，如果有，则要进行i+1趟，如果没有则说明当前数组已经完成排序，不需要剩下的比较：
1public static void bubbleSortOptimize(int[] arr) {
2 for (int i = 0; i < arr.length; i++) {
3 //用来表示当前第i趟是否有交换，
4 //如果有则要进行i+1趟，如果没有则说明当前数组已经完成排序
5 boolean flag = true;
6 for (int j = 0; j < arr.length - i - 1; j++) {
7 if(arr[j] > arr[j+1]){
8 int tmp = arr[j];
9 arr[j] = arr[j+1];
10 arr[j+1] = tmp;
11 flag = false;
12 }
13 }
14 if(flag) return;
15 }
16}
其实冒泡排序还有更优化的做法，那就是记录最后一次交换的位置：
1public static void bubbleSortOptimizePlus(int[] arr) {
2 int pos; //用来记录最后一次交换的位置
3 int k = arr.length - 1;
4 for (int i = 0; i < arr.length; i++) {
5 pos = 0;
6 //用来表示当前第i趟是否有交换，
7 //如果有则要进行i+1趟，如果没有则说明当前数组已经完成排序
8 boolean flag = true;
9 for (int j = 0; j < k; j++) {
10 if(arr[j] > arr[j+1]){
11 int tmp = arr[j];
12 arr[j] = arr[j+1];
13 arr[j+1] = tmp;
14 flag = false;
15 pos = j;
16 }
17 }
18 if(flag) return;
19 k = pos;
20 }
21}
排序随机数组的时候，优化效果一般，但是排序几乎有序的数组和本来就有序的数组还是有优化效果的：
第二种优化之后才0.049秒，不优化是22秒。
稳定性
冒泡排序是稳定排序，在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。
最好和最坏情况
最好情况下，要排序的数据已经是有序的了，我们只需要进行一次冒泡操作，就可以结束了，所以最好情况时间复杂度是 O(n)。而最坏的情况是，要排序的数据刚好是倒序排列的，我们需要进行 n 次冒泡操作，所以最坏情况时间复杂度为 O(n²)。
四、三种排序总结
一看图就明白了什么排序算法最实用了吧，那就是插入排序。 这三种时间复杂度为 O(n²) 的排序算法中，冒泡排序、选择排序，可能就纯粹停留在理论的层面了，学习的目的也只是为了开拓思维，实际开发中应用并不多，但是插入排序还是挺有用的。