常用内部排序算法之四：简单选择排序、直接插入排序和冒泡排序

前言

之所以把这三类算法放在一块，是因为除此之外的算法都是在这三类算法的基础上进行优化的。简单选择排序的思想是每一趟n−i+1(i=1,2,...,n−1)$n-i+1(i=1,2,...,n-1)$个记录中选择最小的记录作为有序序列的第i$i$个记录。直接插入排序的思想是将一个记录插入到已经排好序的有序序列中，从而得到一个新的、记录数增加1的有序表。冒泡排序的算法思想是不断在交换，通过交换完成最终的排序，每一趟的交换就会把最大的记录取出来，下一趟则会把第二大的记录取出来，这样每进行一趟交换就把一个记录取出来的过程称为冒泡。

简单选择排序算法

简单选择的排序的算法思想是：通过n−i$n-i$次关键字间的比较，从n−i+1$n-i+1$个记录中选出关键字最小的记录，并和第i(1≤i≤n)$i(1le i le n)$个记录交换之。其算法代码如下：

package com.rhwayfun.algorithm.sort;

public class SelectSort {

    public void selectSort(int[] a){
        int i,j,min;
        for (i = 0; i < a.length; i++) {
            //假设第一个位置的值是最小值
            min = i;
            for(j = i + 1; j < a.length; j++){
                if(a[min] > a[j]){
                    min = j;
                }
            }
            //如果min不等于i，说明找到最小值的下标
            if(min != i){
                swap(a,i,min);
            }
        }

        for(i = 0; i < a.length; i++){
            System.out.println(a[i]);
        }
    }

    private void swap(int[] a, int i, int min) {
        int temp = a[i];
        a[i] = a[min];
        a[min] = temp;
    }

    public static void main(String[] args) {
        new SelectSort().selectSort(new int[]{9,1,5,8,3,7,4,6,2});
    }
}

观察代码可以发现，第i$i$趟排序需要比较n−i$n-i$次关键字的比较，所以总共需要比较∑n−1i=1(n−i)=n−1+n−2+...+1=n(n−1)2$sum_{i=1}^{n-1}(n-i)=n-1+n-2+...+1=frac{n(n-1)}{2}$次。最好的情况下，交换0次，最差的情况是交换n−1$n-1$次，所以最终的时间复杂度是O(n2)$O(n^2)$。

直接插入排序算法

直接插入排序算法的思想是：将一个记录插入到已经排序的有序表中，从而得到一个新的、记录数增加1的有序表。其处理过程是，在排序刚开始的时候，把第一个元素当做是排序的记录，当依次插入后面的元素的时候，就获得其插入的位置，然后形成一个新的有序表。其算法代码如下：

package com.rhwayfun.algorithm.sort;

public class InsertSort2 {

    public void insertSort(int[] a) {
        int i,j,temp;
        for(i = 1; i < a.length; i++){
            if(a[i] < a[i-1]){
                temp = a[i];
                for(j = i - 1; j >= 0 && a[j] > temp; j--){
                    a[j+1] = a[j];
                }
                a[j+1] = temp;
            }
        }

        for(i = 0;i < a.length; i++){
            System.out.println(a[i]);
        }
    }

    public static void main(String[] args) {
        new InsertSort2().insertSort(new int[]{9,1,5,8,3,7,4,6,2});
    }
}

从空间上分析，直接插入排序算法只需要一个辅助空间。
从时间复杂度上分析，最好的情况是排序的记录本身是有序的，所以时间复杂度是O(n)$O(n)$；在最坏的情况，待排序的记录是逆序的，那么此时的时间复杂度是O(n24)$O(frac{n^2}{4})$。所以虽然量级仍然是n2$n^2$，但是直接插入排序算法的时间复杂度是优于冒泡排序算法和简单选择排序的。

冒泡排序

冒泡排序的基本思想是两两比较相邻记录的关键字，如果反序就交换，直到没有反序的关键字为止。下面是一种实现思路：

package com.rhwayfun.algorithm.sort;

public class BubbleSort3 {

    public void bubbleSort(int[] a){
        int i,j;
        for(i = 0; i < a.length; i++){
            for(j = i + 1; j < a.length; j++){
                if(a[i] > a[j]){
                    swap(a,i,j);
                }
            }
        }

        for(i = 0; i < a.length; i++){
            System.out.println(a[i]);
        }
    }

    private void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void main(String[] args) {
        new BubbleSort3().bubbleSort(new int[]{9,1,5,8,3,7,4,6,2});
    }
}

这种版本也是我第一时间写出来的，但是可以发现一个问题，在排好第一个和第二个为止之后，数字3反而被排到了最后面。下面是针对这种情况的改良版代码：

public void bubbleSort2(int[] a){
        int i,j;
        for(i = 0; i < a.length; i++){
            for(j = a.length - 2; j >= i; j--){
                if(a[j] > a[j + 1]){
                    swap(a,j,j+1);
                }
            }
        }

        for(i = 0; i < a.length; i++){
            System.out.println(a[i]);
        }
    }

这里的改进主要把第二个for循环由从前往后比较改成由后往前进行比较了，这样的好处是可以把本来较小的元素放在尽可能前一点的位置，这种差异性在数据量较大的时候能够体现出来。以上改良版的冒泡排序使用于基本无序的序列，如果是基本有序的序列再使用上述的算法进行排序就会出现一个问题：那就是可能在进行完前几次的冒泡之后就已经是有序的了，那么后面的冒泡都是多余的。下面得代码是针对这种情况进行的优化：

public void bubbleSort3(int[] a){
        int i,j;
        boolean flag = true;
        for(i = 0; i < a.length && flag; i++){
            flag = false;
            for(j = a.length - 2; j >= i; j--){
                if(a[j] > a[j + 1]){//如果不进行数据交换，说明是有序的
                    swap(a,j,j+1);
                    flag = true;
                }
            }
        }

        for(i = 0; i < a.length; i++){
            System.out.println(a[i]);
        }
    }

如果在面试中要求写出冒泡排序算法的代码，写最后一种情况就可以了。

下面分析冒泡排序算法的时间复杂度：在最坏的情况就是待排序的记录是逆序的，此时的时间复杂度是O(n2)$O(n^2)$；最好的情况是，排序表本身就是有序的，那么在这种情况下，时间复杂度是O(n)$O(n)$。