手写排序算法：插入排序、选择排序、冒泡排序

1 插入排序

选择排序类似于我们打扑克，整理手里牌顺序的场景。
当我们拿到一张牌之后，我们会从后往前开始寻找，找到合适的位置插入。
代码如下所示：

public void Insertionsort(int A[]){
    for(int i=1;i<A.length;i++){
        //模拟插牌场景
        //将A[i]插入在卡片0，到卡片i之间
        // j代表抓到的牌，先放到最右侧，不断交换到对应的位置
         int c = A[i];
         int j = i;
         //一一对比，大于的元素往后移动，给插入的元素留出空间
         for(; j>0 && A[j-1] > c; j--){
             A[j] = A[j-1];
         }
         A[j] = c;
    }
}

两层循环：
外层循环是将第i张牌排序，每次循环之后i指向下一个需要排序的元素，脚下标小于i的元素已经排好序了。
内层循环是从排好序的最后一个元素开始比较，如果比要插入元素的值大，就往后移动，给要插入的元素留出个位置。直到碰到合适的位置插入。

2 选择排序

    public static void SelectionSort(int[] A){
    //直观感受就是 他一半是无序的 一半是有序的。以i为界
        for(int i = A.length-1 ; i>=0; i--){
            // 0 - A[i]
            int j = maxIndex(A, 0, i+1); //左开右闭
            swap(A,i,j);
        }
    }
	//交换
    private static void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
	//得到最大值的索引
    private static int maxIndex(int[] A, int i, int j) {
        int max = Integer.MIN_VALUE;

        int maxIndex = i;
        for(int k=0; k<j; k++){
            if(max < A[k]){
                max = A[k];
                maxIndex = k;
            }
        }
        return maxIndex;
    }

选择排序基本思路是首先选择一个数组中最大(最小)的元素，然后把它放到第一个位置(最后一个位置)，其次在剩下的数组元素中找到最大(最小)的元素，然后它放到第二个位置(倒数第二个位置)，如此往复，知道整个数组排好序。
稳定性？
稳定排序：同值顺序在排序过程中不会调换
比如 2 2 1 1
将选择排序改成稳定的
在选择排序中他是不稳定的，因为maxIndex是从左往右的，遍历到2最大值然后把他放到后面，两个2就位置交换了。
其实选择排序稍作改动就解决这个问题了

 int maxIndex = j-1;
 for(int k=j-1; k>=i; k--)

将maxIndex里面的代码，改成从右向左遍历，就解决了。

3 冒泡排序

选最大的元素的算法：不断交换相邻元素

public static void BubbelSort(int[] A){
    //找到0-i间最大元素放到A[i]
    for(int i = A.length -1; i>=0; i--){
        bubble(A, 0,i+1);
    }
}

private static void bubble(int[] A, int i, int j) {
    for(int k=i; k<j-1;k++){
        if(A[k] > A[k+1]){
            swap(A, k,k+1);
        }
    }
}

稳定性？
冒泡排序是稳定的，但是他的效率是比较低的，一般用的比较少。
为什么比较低呢？因为他的写 *** 作太多了， swap(）执行次数相比选择排序和插入排序要多不少。