一、选择排序
选择排序：首先，找到数组中最小的元素；其次，将它和数组的一个元素交换位置（如果第一个的元素就是就是最小的元素那么它就与自己交换）；再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。此后循环这个过程（找到剩下元素中最小的，将它与第i个元素交换位置），直到将整个数组排序。这就是选择排序，因为它总是在剩余的元素中寻找最小的那一个。
选择排序的内循环只是在比较当前元素与目前已知的最小元素。将交换元素的代码写在内循环外，每次交换元素都能确定一个元素，因此交换的次数总是N。所以算法的时间效率取决于比较的次数。

public class Selection
{
    public static void sort(Comparable[] a)
    {//将a[]按升序排列
        int N =a.length;
        for (int i = 0; i < N; i++)
        {//将a[i]和a[i+1..N]中最小的元素交换
            int min = i;
            for （j = i+1; j < N;j++）
            if(less(a[i],a[min]))
                min = j;
            exch(a,i,min);
        }
    }
}

总得来说，选择排序是一种很容易理解和实现得简单排序算法，它有两个鲜明得特点。

  • 运行时间和输入无关
    为了找出最小的元素而扫描一遍数组不能为下一轮的扫描什么信息
  • 数据移动是最少的
    每次交换都会改变两个数组元素的值，选择排序用了N次交换——交换次数的数组的大小是线性关系。

二、插入排序
我们在打斗地主时，手牌是一张一张抓的，总是以一个从小到大或者从大到小的排序，当抓到一张新的手牌时，都会将其插入到其他已经有序的牌的适当位置。这就是一种类似插入排序的思想。
与选择排序一样，当前索引左边所有的的元素都是有序的，但它们的最终位置时不确定的，为了给更小的元素腾出空间，它们可能会被移动。
而与选择排序不相同的是，插入排序所需要的时间取决于输入中元素的初始顺序。对于一个很大且其中元素以及有序或者接近有序的数组进行插入排序将会比随即顺序的数组或则逆序数组进行排序要快得多。

public class Insertion
{
    public static 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);
            }
        }
    }
}

插入排序对于部分有序数组十分的高效，也很适用小规模数组，而且它们也是高级排序算法的中间过程。