初级排序算法

约定

首先我们约定几个工具方法：

/**
    比较a是否小于b，如果a<b返回true
*/
public static boolean less(int a,int b){
    if(a<b){
        return true;
    }
    return false;
}

/**
    交换数组中i，j的值的位置
*/
public static void exchange(int[] arr,int i,int j){
    int temp = arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
}

选择排序

选择排序的思想是在一堆无序数字中，首先找出最小的数字，然后与数组第一个元素交换，然后再在剩下的元素中找最小的数字，与第二个交换。这样以此类推，直到整个排序完成。这个就是选择排序。选择排序的思想就是一直选择最小的那个值。

代码：

/**
选择排序，在传入前请判断arr是否为null
*/
public static void selectSort(int[] arr){
    int len = arr.length;
    for(int i=0;i<len;i++){
        int min = i;
        for(int j=i+1;j<len;j++){
            if(less(arr[j],arr[i])){
                min=j;
            }
        }
        exchange(arr,i,min);
    }
}

选择排序的特点，我们可以看到，选择排序每次都是从开始位置，一直到最后的位置，而且每次都需要遍历。所以输入的值关系并没有影响它，比如你输入“1,2,3,4”和“4，1，3,2”所需要的时间是相等的，因为它每次都会起始位置开始比较。数据移动是固定的，跟待比较的值呈线性关系。输入N个值，移动N次。另外有一点，如果一次遍历下来最小值是它本身，那么它还是会和自己做一次交换。
选择排序的时间复杂度怎么计算了？我们可以看到比较次数为：(n-1)+(n-2)+(n-3)+(n-4)+…+3+2+1，也就是任意i的位置都需要进行一次交换和（n-i-1）次比较。可以由公式得出为 $ (n-1)+(n-2)+(n-3)+(n-4)+…+3+2+1 ~ N^2/2 $

插入排序

如果你喜欢打牌，那么你肯定就知道插入排序就是怎么样了。比如你抓牌的时候会将抓到的牌按照大小顺序来排列，当你手上的牌是一个已好的顺序时候，下次抓出的牌你会将它插入到相应的位置。这就是插入排序的原理了。在实际中，我们用数组的方式来表示的话，当插入的已有的顺序中间的时间，那么其它位置的牌将需要全部移动一个位置。

public void insertSort(int[] arr){
    int len = arr.length;

    //为什么从1开始？，第0个位置相当于抓的第一张牌，做基础对比的。
    for(int i=1;i<len;i++){
        // i之前的数据，可以看作是已经排好序了
        for(int j=i;j>0;j--){
            if(less(arr[j],arr[j-1])){
                exchange(arr,i,j);
            }
        }

    }
}

插入排序如果是以下集中情况将会很有效：

数组中每个元素的位置离他们最终元素的位置都不远；
数组中只有几个元素的位置不正确；
一个有序的大数组接一个小数组。