转载

简单排序之冒泡、选择、插入、希尔详细总结

前言

本文讲述一些简单算法的实现和效率比较。所有代码用 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;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;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;
            }
        }
    }
}