基础算法-选择插入排序

今天学习两个简单的数组排序算法，选择排序和插入排序。

题目介绍

给定一个数组，将数组按从小到大顺序排序。题目理解起来也是很容易的，就不再画图介绍了。

选择排序

选择排序算法如下：首先找到数组中最小的那个元素，其次将它和数组的第一个元素交换位置（如果第一个元素就是最小的元素那么它就和自己交换）。再次，在剩下的元素中找到最小的元素，将它和数组的第二个元素交换位置。如此反复，直到将整个数组排序。

这种算法叫选择排序就是因为它在不断地选择剩余元素中最小者。

插入排序

插入排序我们使用通常整理纸牌的方法来描述，我们在整理纸牌的时候一般是一张张的来，将每一张插入到其他已经有序的纸牌中的合适位置。在计算机的程序中，为了给要插入的元素腾出空间，我们需要将其余的所有元素都向右移动一位。

实现代码

因为后续多种排序算法都是基于比较+交换的方式来完成排序的，因此先定义一个抽象的排序类。其他排序算法只需要完成类中的sort方法即可。

/**
 * 比较交换排序算法抽象类
 */
public abstract class AbstractSort {

    /**
     * 对给定数组按从小到大排序
     *
     * @param a
     */
    public abstract void sort(Comparable[] a);

    /**
     * 判斷數字是否已經有序
     *
     * @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;
    }

    /**
     * 比较两个元素，第一个参数是否小于第二个参数
     *
     * @param v
     * @param w
     * @return
     */
    protected boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    /**
     * 交换数组中的两个元素
     *
     * @param a
     * @param i
     * @param j
     */
    protected void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    /**
     * 在一行中打印数组
     *
     * @param a
     */
    protected void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            StdOut.print(a[i] + " ");
        }
        StdOut.println();
    }

}

选择排序：

public class Selection extends AbstractSort {
    @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);
            }
        }
    }
}

插入排序

public class Insertion extends AbstractSort {

    @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);
            }
        }
    }

}

算法相关实现源码地址：https://github.com/xiekq/rubs-algorithms