简单排序

1、选择排序

选择出数组中的最小元素，将它与数组的第一个元素交换位置。再从剩下的元素中选择出最小的元素，
将它与数组的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。

选择排序是对冒泡排序的改进，它的比较次数与冒泡排序相同，但交换次数要小于冒泡排序。
当数据量较大时，效率会有很大的提升，但时间复杂度仍为O(n*n)。

实现

public class Selection {

    public static void main(String[] args) {
        int[] nums = { 2, 7, 3, 5, 8 };
        for (int i = 0; i < nums.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[min]) {
                    min = j;
                }
            }
            //序号有改变，说明需要交换
            if (min != i) {
                swap(nums, i, min);
            }
        }
        for (int i : nums) {
            System.out.println(i);
        }
    }

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

2、冒泡排序

从左到右不断交换相邻逆序的元素，在一轮的循环之后，可以让未排序的最大元素上浮到右侧。

在一轮循环中，如果没有发生交换，就说明数组已经是有序的，此时可以直接退出。
若原数组本身就是有序的（这是最好情况），仅需n-1次比较就可完成；
若是倒序，比较次数为 n-1+n-2+...+1=n(n-1)/2，交换次数和比较次数等值。
所以，其时间复杂度依然为O(n2）。综合来看，冒泡排序性能还还是稍差于选择排序的。

实现

public static void main(String[] args) {
        int[] nums = { 2, 7, 3, 5, 8 };
        int len = nums.length;
        boolean hasSorted = false;
        for (int i = len; i >= 0 && !hasSorted; i--) {
            hasSorted = true;
            for (int j = 1; j < i; j++) {
                if (nums[j - 1] > nums[j]) {
                    hasSorted = false;
                    swap(nums, j - 1, j);
                }
            }
        }
        for (int i : nums) {
            System.out.println(i);
        }
    }

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

3、插入排序

（1）原理：
1、将指针指向某个元素，假设该元素左侧的元素全部有序，
将该元素抽取出来，然后按照从右往左的顺序分别与其左边的元素比较，
遇到比其大的元素便将元素右移，直到找到比该元素小的元素或者找到最左面发现其左侧的元素都比它大，停止
2、此时会出现一个空位，将该元素放入到空位中，此时该元素左侧的元素都比它小，右侧的元素都比它大
3、指针向后移动一位，重复上述过程。每操作一轮，左侧有序元素都增加一个，右侧无序元素都减少一个。

（2）例子：
　　待比较数据：2, 5, 3, 7, 8
　　第一轮：指针指向第二个元素5，假设5左面的元素为有序的，将5抽离出来，形成2,_,3,7,8，
从2开始，2和5比较，发现5>2。无需移动，把5放到空位中，结果仍为：2, 5, 3, 7, 8

　　第二轮：指针指向第三个元素3，此时其左面的元素2,5为有序的，将3抽离出来，形成2,5,_,3,7,8，
从5开始，依次与3比较，发现5>3。将5右移，形成2,_, 5, 7, 8，3插入到5前面的空位，结果：2, 3, 5, 7, 8

　　第三轮：指针指向第四个元素7，此时其左面的元素2, 3, 5,为有序的，将7抽离出来，形成2, 3, 5,_,8，
从5开始，依次与7比较，发现7>5，无需移动，结果为：6,7,8,9,5,1

　　第四轮：同上，结果：2, 3, 5, 7, 8

（3）总结：
插入排序是简单排序中最快的排序算法，虽然时间复杂度仍然为O(n*n)，但是却比冒泡排序和选择排序快很多。

实现

public class Insertion {

    public static void main(String[] args) {
        int[] nums = { 2, 5, 3, 7, 8 };
        int len = nums.length;
        for (int i = 1; i < len; i++) {
            for (int j = i; j > 0; j--) {
                if (nums[j - 1] > nums[j]) {
                    swap(nums, j - 1, j);
                }else {
                    break;
                }
            }
        }
        for (int i : nums) {
            System.out.println(i);
        }
    }

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