三种简单排序算法
排序是最常见的算法，本文将介绍三种简单排序算法：冒泡，选择和插入排序。三种算法基本都在数组内部操作数据，所以空间复杂度为O(N)，时间复杂度都为O(N^2)，需要说明的是，虽说时间复杂度均为O(N^2)，但具体来说，O(N^2)仅仅是指用于数据值比较次数的量级，但是交换和拷贝数据的次数是不同的，所以三种排序算法的性能在这里有重要区别。
说明：为了描述方便，以下均以int类型数列为例，数据量为N，排序方式是从小到大。
冒泡排序
冒泡排序是最容易想到的排序方法，操作上就是两两比较和交换，具体来说，首先，从左到右两两比较，若左边的值大，就交换两个数字，这样，一轮下来，数列中的最大值就被交换到了最右边。然后，把最右边的数晾在一边，对前N-1个数重复一轮比较和交换。重复这个过程直到倒数第二大的数被换到了第二的位置。分析可知，这里需要比较的次数是：(N-1)+(N-2)+...+1 = N(N-1)/2，分析需要交换的次数，这里假设比较悲剧的情况，即一开始数据是从大到小排列的，每次都需要交换，则交换次数是N(N-1)/2，一般不会这么背，平均来说，需要交换的次数是N(N-1)/4。
1 /** 2 * 一层层地，一次次地交换局部最值，实现把局部最值放到局部的最后边 3 * Time Complexity: O(N^2) 4 */ 5 public static int[] bubbleSort(int[] input) { 6 if (input.length <= 1) { 7 return input; 8 } 9 // compare And Swap10 for (int outer = input.length - 1; outer > 0; outer--) {11 for (int inner = 0; inner < outer; inner++) {12 int prev = input[inner];13 int next = input[inner + 1];14 if (prev > next) {15 input[inner] = next;16 input[inner + 1] = prev;17 }18 }19 }20 return input;21 }
选择排序
选择排序的比较过程和冒泡排序一样，但是把最值交换到数据最右边的过程，不是通过逐个交换完成的，而是通过增加一个临时变量来记住最值的位置，一次扫描式的比较之后，找出最值的位置，然后把最值和队列最右边的值交换即可。比较次数依然是N(N-1)/2，但交换次数最多只有N-1次，记住最值位置的临时变量的拷贝最多N-1次，平均(N-1)/2。
1 /** 2 * 一层层地找出局部最值，然后交换一次把局部最值放到局部的最后边 3 * Time Complexity: O(N^2) 4 */ 5 public static int[] selectSort(int[] input) { 6 if (input.length <= 1) { 7 return input; 8 } 9 // compare then record and Swap10 for (int outer = input.length - 1; outer > 0; outer--) {11 int maxIdx = 0;12 for (int inner = 1; inner <= outer; inner++) {13 if (input[maxIdx] < input[inner]) {14 maxIdx = inner;15 }16 }17 if (maxIdx != outer) {18 int outerVal = input[outer];19 input[outer] = input[maxIdx];20 input[maxIdx] = outerVal;21 }22 }23 return input;24 }
插入排序
插入排序的思考起点是数据是局部有序的，假如在某个数右边的数据都是有序的，那么，以这个数为起点，向左扫描，不断把数字插入到右边有序的数据列中去，当有序列表扩张到整个数列时，这个数列就是有序的。这里需要说明一下插入操作：把要插入的数字复制到临时变量，然后和有序列中的数字按顺序逐个比较，若有序列中的数字小于待插值，则把这个数字向左挪动一个位置（挪动之后，原来的位置留下一个空位），反之，则把待插值插入这个数字的左边（左边数字挪动后留下的空位或者待插入数字原来的位置）。比较次数：插入排序在最背的情况下，需要N(N-1)/2次，平均需要N(N-1)/4次。挪动数据的次数与比较次数类似：最差N(N-1)/2，平均N(N-1)/4次，另外，临时变量需要N-1次拷贝。在数列比较有序的情况下用插入排序更快，但假如原始顺序与将要排的顺序相反的话，就需要大量挪动数据，变得很慢。
参考代码如下：
1 /** 2 * 遍历把值插入已有的局部有序序列中，逐步实现有序序列的扩张直到整个序列有序。 3 * 优点：局部有序时，几乎不需要挪动数据，直接插入； 4 * 这同时也是其缺点，即当顺序正好与想要的顺序大致相反时，需要大量地挪动数据，此时效率甚至低于冒泡法。 5 * Time Complexity: O(N^2) 6 */ 7 public static int[] insertSortFromRight(int[] input) { 8 if (input.length <= 1) { 9 return input;10 }11 // 从右往左扫描，右边局部有序12 for (int insertIdx = input.length - 2; insertIdx >= 0; insertIdx--) {13 int insertVal = input[insertIdx];14 int orderedIdx = insertIdx + 1;15 for (; orderedIdx < input.length; orderedIdx++) {16 if (insertVal <= input[orderedIdx]) {17 break;18 } else {19 input[orderedIdx - 1] = input[orderedIdx];20 }21 }22 input[orderedIdx - 1] = insertVal;23 }24 return input;25 }
三种排序比较
| 算法 | 比较次数 | 交换次数 | 拷贝次数 |
| 冒泡 | N(N-1)/2 | N(N-1)/4，最差N(N-1)/2 | 0 |
| 选择 | N(N-1)/2 | N-1 | (N-1)/2 |
| 插入 | N(N-1)/4，最差N(N-1)/2 | 0 | N(N-1)/4+(N-1)，最差N(N-1)/2+(N-1) |
说明：一次交换等于三次拷贝。
总结
- 三种算法中，冒泡和选择实现方式简单，而插入法稍微复杂；
- 性能上，选择法比冒泡法快，而插入法在原始数据有序度高时最快，原始顺序与排序顺序相反时，性能下降明显。