今天我们来说说常用的三种排序算法：选择排序、插入排序、快速排序-Toy模板网

这篇具有很好参考价值的文章主要介绍了今天我们来说说常用的三种排序算法：选择排序、插入排序、快速排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

原文链接：http://www.ibearzmblog.com/#/technology/info?id=8ac4902f82f525e1456624d5d7a545dc

前言

选择排序、插入排序、快速排序这三种算法算是比较初级的排序算法，对它们的原理和技巧，可以方便我们对后面的算法理解。

温馨提示，因为动图不好弄，所以我在网上下载了AlgorithmMan来进行动图演示。

算法基础模板

后面的算法都是继承于这个基础模板，里面主要是实现一些公用方法，例如比较大小、交换元素等等，所以还是很有必要贴一下代码：

public class SortTemplate {

    /**
     * 排序规则，由子类实现
     * @param a
     */
    public void sort(Comparable[] a){}

    /**
     * 比较v和w的大小
     * @param v
     * @param w
     * @return
     */
    public Boolean less(Comparable v, Comparable w){
        return v.compareTo(w) < 0;
    }

    /**
     * 元素交换
     * @param a
     * @param i
     * @param j
     */
    public void exch(Comparable[] a, int i, int j){
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    /**
     * 输出数组里所有的元素
     * @param a
     */
    public void show(Comparable[] a){
        StringBuilder stringBuilder = new StringBuilder();
        for(int i = 0; i < a.length; i++){
            stringBuilder.append(a[i] + "  ");
        }
        return stringBuilder.toString();
    }

    /**
     * 判断数组是否有序的
     * @param a
     * @return
     */
    public boolean isSorted(Comparable[] a){
        for (int i = 1; i < a.length; i++){
            if(less(a[i], a[i + 1]))
                return false;
        }
        return true;
    }

}

选择排序

选择排序是最简单粗暴的，原理如下：第一步，找到这个数组里最小的元素，然后与第一个元素进行交换位置。然后在剩下的元素中找到最小的元素，然后与第二个元素交换位置，如此反复。如下面的动画：
今天我们来说说常用的三种排序算法：选择排序、插入排序、快速排序,排序算法,算法,java

代码实现很简单：

/**
 * 选择排序
 */
public class SelectSort  extends SortTemplate{

    @Override
    public void sort(Comparable[] a) {
        int N = a.length;
        for (int i = 0; i < N; i++){
            int min = i;
            for(int j = i + 1; j < N; j++){
                if(less(a[j], a[min]))
                    min = j;
            }
            exch(a, i, min);

        }
    }
}

接下来我们讨论下它的时间复杂度，从上面的代码可以知道，长度为N的数组，一共需要交换N次，从0到N-1都会进行（N-1）+(N-2)+(N-3)+…+2+1次比较，根据高斯定理，得出N(N-1)/2，则约等于N^2/ 2（最大系数才是直接影响时间复杂度的核心，常量可以忽略不计）。

所以选择排序的时间复杂度为O(N^2 / 2)。

插入排序

插入排序跟选择排序有点不同，插入排序的性能取决于数组是否有序的，就像我们斗地主的时候，都会将每一张牌插入到其它已经有序的牌中，当插入牌后，就需要将后面的牌向后移动一位，这就是插入排序。

今天我们来说说常用的三种排序算法：选择排序、插入排序、快速排序,排序算法,算法,java

具体代码实现如下：

public class InsertSort extends SortTemplate{

    @Override
    public void sort(Comparable[] a) {
        int N = a.length;
        for(int i = 1; i < N; i++){
            for(int j = i; j > 0 && less(a[j], a[j - 1]); j--){
                exch(a, j, j - 1);
            }
        }
    }
}

举个例子，我现在有个无序数组{10，5，3，6，7}，那么它的执行过程如下：
今天我们来说说常用的三种排序算法：选择排序、插入排序、快速排序,排序算法,算法,java

接下来我们说下时间复杂度，在最好的情况，不用移动原数组的元素，则只是N-1次比较，同时并不需要比较。不过我们通常都只会考虑最坏情况，跟快速排序一样，假如数组是逆序的（也就是从大到小），那么就需要（N-1）+(N-2)+(N-3)+…+2+1次比较和（N-1）+(N-2)+(N-3)+…+2+1次交换，也就是N^2 / 2次比较和N^2 / 2次交换，也就是在逆序的情况下的时间复杂度为O(n^2)，如果在最好的情况下那么时间复杂度就为O(n)。

快速排序

快速排序是一种分治的方法，它的核心理念是将一个无序的数组一分为二并分别排序，当两个子数组都有序时则整个数组都为有序。快速排序的核心在于切分，下面是快速排序的大致过程：
今天我们来说说常用的三种排序算法：选择排序、插入排序、快速排序,排序算法,算法,java

主要代码实现如下：

/**
 * 快速排序
 */
public class QuickSort extends SortTemplate{

    @Override
    public void sort(Comparable[] a) {
        sort(a, 0, a.length - 1);
    }

    private void sort(Comparable[] a, int lo, int hi){
        if(hi <= lo){
            return;
        }
        int j = partition(a, lo, hi);
        sort(a, lo, j - 1);
        sort(a, j + 1, hi);
    }

    private int partition(Comparable[] a, int lo, int hi){
        int i = lo, j = hi + 1;
        Comparable first = a[i];
        while (true){
            while (less(a[++i], first)){
                if(i == hi){
                    break;
                }
            }
            while (less(first, a[--j])){
                if(j == lo){
                    break;
                }
            }
            if(i >= j){
                break;
            }
            exch(a, i, j);
        }
        exch(a, lo, j);
        return j;
    }
}

快速排序的核心是切分，主要需要满足下面三个条件：

a[lo]到a[j - 1]中的所有元素都不大于a[j]。
a[j + 1]到a[hi]的所有元素都不小于a[j]。
a[j]是已经锁定位置。

其中，回看上面代码，partition()是切分方法，我们重点来分析下：

    private int partition(Comparable[] a, int lo, int hi){
        // 默认第一次切分的元素是数组第一个元素，也就是a[0]
        int i = lo, j = hi + 1;
        Comparable first = a[i];
        while (true){
            // 从左往右找出比切分元素大的元素下标
            while (less(a[++i], first)){
                if(i == hi){
                    break;
                }
            }
            // 从右往左找出比切分元素小的元素下标
            while (less(first, a[--j])){
                if(j == lo){
                    break;
                }
            }
            if(i >= j){
                break;
            }
            // 交换i和j的位置，保证左边的元素都是小于等于切分元素，右边的都是大于等于切分元素
            exch(a, i, j);
        }
        // 一共有三种情况会跳出上面的循环，1.切分元素是数组里最大的元素，2.切分元素是数组里最小的元素，3.当指针相遇时则会跳出。最后的一部j指针的位置与切分元素进行交换
        exch(a, lo, j);
        return j;
    }

从sort()方法可以看到，快速排序就是通过不断的切分、递归的方式进行排序，我们接下来看看它的实际排序过程：

输入: 12, 8, 1, 17, 9, 18, 1, 11, 10, 8, 19, 17, 20
-----------------------
切分前数组: 12  8  1  17  9  18  1  11  10  8  19  17  20  
切分前i: 0, 切分前j: 13, 切分元素为a[i]: 12, lo: 0
比切分元素大的位置i: 3, 比切分元素小的位置j: 9
将i和j的元素进行交换
交换后的数组: 12  8  1  8  9  18  1  11  10  17  19  17  20  
比切分元素大的位置i: 5, 比切分元素小的位置j: 8
将i和j的元素进行交换
交换后的数组: 12  8  1  8  9  10  1  11  18  17  19  17  20  
最后交换lo和j的位置
最后的出数组: 11  8  1  8  9  10  1  12  18  17  19  17  20  
-----------------------
切分前数组: 11  8  1  8  9  10  1  12  18  17  19  17  20  
切分前i: 0, 切分前j: 7, 切分元素为a[i]: 11, lo: 0
最后交换lo和j的位置
最后的出数组: 1  8  1  8  9  10  11  12  18  17  19  17  20  
-----------------------
切分前数组: 1  8  1  8  9  10  11  12  18  17  19  17  20  
切分前i: 0, 切分前j: 6, 切分元素为a[i]: 1, lo: 0
比切分元素大的位置i: 1, 比切分元素小的位置j: 2
将i和j的元素进行交换
交换后的数组: 1  1  8  8  9  10  11  12  18  17  19  17  20  
最后交换lo和j的位置
最后的出数组: 1  1  8  8  9  10  11  12  18  17  19  17  20  
-----------------------
切分前数组: 1  1  8  8  9  10  11  12  18  17  19  17  20  
切分前i: 2, 切分前j: 6, 切分元素为a[i]: 8, lo: 2
最后交换lo和j的位置
最后的出数组: 1  1  8  8  9  10  11  12  18  17  19  17  20  
-----------------------
切分前数组: 1  1  8  8  9  10  11  12  18  17  19  17  20  
切分前i: 4, 切分前j: 6, 切分元素为a[i]: 9, lo: 4
最后交换lo和j的位置
最后的出数组: 1  1  8  8  9  10  11  12  18  17  19  17  20  
-----------------------
切分前数组: 1  1  8  8  9  10  11  12  18  17  19  17  20  
切分前i: 8, 切分前j: 13, 切分元素为a[i]: 18, lo: 8
比切分元素大的位置i: 10, 比切分元素小的位置j: 11
将i和j的元素进行交换
交换后的数组: 1  1  8  8  9  10  11  12  18  17  17  19  20  
最后交换lo和j的位置
最后的出数组: 1  1  8  8  9  10  11  12  17  17  18  19  20  
-----------------------
切分前数组: 1  1  8  8  9  10  11  12  17  17  18  19  20  
切分前i: 8, 切分前j: 10, 切分元素为a[i]: 17, lo: 8
最后交换lo和j的位置
最后的出数组: 1  1  8  8  9  10  11  12  17  17  18  19  20  
-----------------------
切分前数组: 1  1  8  8  9  10  11  12  17  17  18  19  20  
切分前i: 11, 切分前j: 13, 切分元素为a[i]: 19, lo: 11
最后交换lo和j的位置
最后的出数组: 1  1  8  8  9  10  11  12  17  17  18  19  20  
---------最后输出-----------
1  1  8  8  9  10  11  12  17  17  18  19  20

时间复杂度证明比较复杂，我这里直接输出为平均 O(2NlnN)，最多则为O(N^2/2).