作者：threezj
原文地址：简单排序之冒泡、选择、插入、希尔详细总结
前言
本文讲述一些简单算法的实现和效率比较。所有代码用java实现。用到的两个基本的api代码如下：
private boolean less(Comparable v,Comparable w){
return v.compareTo(w) <0;
}
private void exch(Comparable[] a,int i,int j){
Comparable temp = a[i];
a[i] = a[j];
a[j] = temp;
}
冒泡排序(Bubble Sort)
一般算法入门，都是用冒泡做的例子。但实际中基本很难用到，复杂度O(n²)。
原理
一趟一趟的比，每一趟中，循环剩余的数，和后一个进行比较，若比它小则交换。这样一趟下来最小的在第一个，最大的在最后一个。总共比n-1趟。
实现
public class Bubblesort implements Sortable {
@Override
public void sort(Comparable[] a) {
for(int i=0;i<a.length-1;i++){
for(int j=0;j<a.length-1-i;j++){
if(less(a[j+1],a[j])){
exch(a,j,j+1);
}
}
}
}
}
优化
上面的算法，无论的你的数据怎么样，始终都要比n²次，效率很低。若你的数据局部有序，经过几趟交换以后，已经有序，则不用继续往下比。效率会高很多。优化代码如下：
public class Bubblesort implements Sortable {
@Override
public void sort(Comparable[] a) {
for(int i=0;i<a.length-1;i++){
boolean didSwap = flase;
for(int j=0;j<a.length-1-i;j++){
if(less(a[j+1],a[j])){
exch(a,j,j+1);
didSwap = true;
}
}
if(!didSwap) return ;
}
}
}
选择排序(Selection sort)
和冒泡复杂度一样O(n²)，但是时间上可能会比冒泡稍微快一点，因为交换的次数比冒泡少。
原理
选择排序可以说是最好理解的算法。就是每次遍历一趟，找出最小的数，放到最前端。（这里说的是最前，是指无序的队列中的最前）
实现
public class Selection implements Sortable {
@Override
public void sort(Comparable[] a){
for(int i=0;i<a.length;i++){
int min=i;
for(int j=i+1;j<a.length;j++){
if(less(a[j],a[min])){
min = j;
}
}
exch(a,i,min);
}
}
}
插入排序
时间复杂度O(n²)。
原理
遍历未排序序列。把未排序数列的第一个数和已排序数列的每一个数比较，若比它大则交换。经典的理解方式就是理解成摸牌时候理牌的顺序。我上面的实现是直接交互数字，若是把大的数直接往后移效率还会更高。
实现
public class Insertion implements Sortable{
@Override
public void sort(Comparable[] a){
for(int i=1;i<a.length;i++){
for(int j=i;j>0;j--){
if(less(a[j],a[j-1])){
exch(a,j,j-1);
}
else break;
}
}
}
}
适合插入排序的数据
当你的数据是基本有序的时候且数据量小，利用插入排序的时候，效率会很高。若数据为逆序的话，效率很低。
希尔排序(Shell Sort)
可以看出是插入排序的一种优化，或者是预处理。希尔排序就是先进行h-sort，也就是让间隔为h的元素都是有序的。普通的插入排序就是1-sort。
原理
主要就是选定一个h的有序数组来进行预排序。这样最后进行插入排序的时候，能使数据局部有序。就算交换的话，交换的次数也不会很多。这样h序列称为递增序列。希尔的性能很大部分取决于递增序列 。一般来说我们使用这个序列3x + 1.
实现
public class ShellSort implements Sortable {
@Override
public void sort(Comparable[] a){
int h=1;
while(h<a.length/3){
h=3*h+1;
}
while(h>=1){
for(int i=h;i<a.length;i++){
for(int j=i;j>=h;j=j-h){
if(less(a[j],a[j-h])){
exch(a,j,j-h);
}
else break;
}
}
h=h/3;
}
}
}
性能
对于希尔排序的性能其实无法准确表示。介于O(nlogn)和O(n²)之间，大概在n的1.5次幂左右。
希尔排序对于中大型数据的排序效率是很高的，而且占用空间少，代码量短。而且就算是很大的数据，用类似快排这种高性能的排序方法，也仅仅只比希尔快两倍或者不到。
运行时间比较
我测试了一下，用5000个数据，排序100次。使用上述四个算法的运行时间如下。
冒泡排序 5.734000000000004
选择排序 2.351
插入排序 2.720999999999999
希尔排序 0.09400000000000007
