简单排序算法

简单排序算法包括3个排序算法：

1）简单选择排序

原理是：每一趟从待排序的数组元素中选择最小的，放到这一趟的最左边。从左边开始有序。这个就是每次都吃最好苹果或者最烂苹果的那个故事。

  /**
     * 每一趟从待排序的数据元素中选择最小（或最大）的一个元素作为首元素
     */
    public static void easySelect(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int min = arr[i];
            int minIndex = i;

            // 找到最大元素及其索引，并与arr[i]交换
            for (int j = i; j < arr.length - 1; j++) {
                if (min > arr[j + 1]) {
                    minIndex = j + 1;
                    min = arr[j + 1];
                }
            }

            swap(arr, i, minIndex);
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 5, 2, 6, 8, 2, 5, 7, 3, 1};
        easySelect(arr);
        System.out.println(Arrays.toString(arr));
    }

2）冒泡排序

原理是：每一趟都比较相邻元素，不满足选定的顺序就交换，逐渐把大的浮到右边。从右边开始有序。

    /**
     * 每一趟都比较相邻元素
     */
    public static void bubbleUpSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] <= arr[j + 1]) {
                    swap(arr, j, j + 1);
                }
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = new int[] {1, 2, 5, 2, 6, 8, 2, 5, 7, 3, 1};
        bubbleUpSort(arr);
        System.out.println(Arrays.toString(arr));
    }

3）插入排序

原理是：每一次把右半边数组的第一个元素插入到左半边，然后排序左半边数组，直到元素都插入完。从左边开始有序。

待排序数组[1，2，5，2，6，8，2，5，7，3，1]

一开始逻辑上把数组分为左半边数组[1]，和右半边数组[2，5，2，6，8，2，5，7，3，1]

把2插入到左半边数组，形成[1，2]，符合升序，不用排序。

再把5插入到左半边数组，形成[1, 2, 5]，符合升序，不用排序。

再把2插入到左半边数组，形成[1, 2, 5, 2]，不符合升序，需要排序。由于[1, 2, 5]是有序的，所以只需要把新增的2往数组左边移，直到左半边数组有序，这样子排序最快。此时左半边数组是[1, 2, 2, 5]。

再把6插入到左半边数组，形成[1，2，2，5，6]，符合升序，不用排序。

再把8插入到左半边数组，形成[1，2，2，5，6，8]，符合升序，不用排序。

再把2插入到左半边数组，形成[1，2，2，5，6，8，2]，不符合升序，需要排序。由于[1，2，2，5，6，8]是有序的，所以还是只需把新增的2往数组左边移，直到左半边数组有序。此时左半边数组是[1，2，2，2，5，6，8]。

就这样一直插入，直到元素全部插入到左边数组中。

    public static void insertSelect(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int j = i;
            while (j > 0 && arr[j - 1] > arr[j]) {
                swap(arr, j - 1, j);
                j--;
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 5, 2, 6, 8, 2, 5, 7, 3, 1};
        insertSelect(arr);
        System.out.println(Arrays.toString(arr));
    }

插入排序的代码比较难，自己从来没有写出来过。需要背下来。