选择排序

public static void selectionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                minIndex = arr[j] < arr[minIndex] ? j : minIndex;
            }
            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;
    }

【选择排序——例子】：对数组数据从小到大进行排序
数组数据：1、9、10、4、5

第1次：将1与9、10、4、5进行比较，找到最小值1
第1次排序后：

第2次：将9与10、4、5进行比较，找到最小值4，将4
与9的位置进行互换
第2次排序后：

第3次：将10与9、5进行比较，找到最小值5，将5与
10的位置进行互换
第3次排序后：

第4次：将9与10进行比较，找到最小值9
第4次排序后：

【过程：】
arr[0～N-1]范围上，找到最小值所在的位置，然后把最小值交换到0位置。
arr[1～N-1]范围上，找到最小值所在的位置，然后把最小值交换到1位置。
arr[2～N-1]范围上，找到最小值所在的位置，然后把最小值交换到2位置。
…
arr[N-1～N-1]范围上，找到最小值位置，然后把最小值交换到N-1位置。

【时间复杂度估算：】
很明显，如果arr长度为N，每一步常数操作的数量，如等差数列一般
所以，总的常数操作数量 = a(N^2) + bN + c (a、b、c都是常数)

所以选择排序的时间复杂度为O(N^2)。

冒泡排序

public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int e = arr.length - 1; e > 0; e--) { 
            for (int i = 0; i < e; i++) {
                if (arr[i] > arr[i + 1]) {
                    swap(arr, i, i + 1);
                }
            }
        }
    }

    // 交换arr的i和j位置上的值
    public static void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

【冒泡排序——例子】：对数组数据从小到大进行排序
数组数据：1、9、10、4、5

第1次：将1与9进行比较，1<9，排序不变
第1次排序后：

第2次：将9与10进行比较，9<10，排序不变
第2次排序后：

第3次：将10与4进行比较，10>4，将10与4进行交换
第3次排序后：

第4次：将10与5进行比较，10>5，将10与5进行交换
第4次排序后：

第5次：将1与9进行比较，1<9，排序不变
第5次排序后：

第6次：将9与4进行比较，9>4，将9与4进行交换
第6次排序后：

第7次：将9与5进行比较，9>5，将9与5进行交换
第7次排序后：

第8次：将1与4进行比较，1<4，排序不变
第8次排序后：

第9次：将4与5进行比较，4<5，排序不变
第9次排序后：

第10次：将1与4进行比较，1<4，排序不变
第10次排序后：

【过程：】
在arr[0～N-1]范围上：
arr[0]和arr[1]，谁大谁来到1位置；arr[1]和arr[2]，谁大谁来到2位置…arr[N-2]和arr[N-1]，谁大谁来到N-1位置

在arr[0～N-2]范围上，重复上面的过程，但最后一步是arr[N-3]和arr[N-2]，谁大谁来到N-2位置
在arr[0～N-3]范围上，重复上面的过程，但最后一步是arr[N-4]和arr[N-3]，谁大谁来到N-3位置
…
最后在arr[0～1]范围上，重复上面的过程，但最后一步是arr[0]和arr[1]，谁大谁来到1位置

【时间复杂度的估算：】
很明显，如果arr长度为N，每一步常数操作的数量，依然如等差数列一般
所以，总的常数操作数量 = a(N^2) + bN + c (a、b、c都是常数)

所以冒泡排序的时间复杂度为O(N^2)。

插入算法

public static void insertionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 1; i < arr.length; i++) { // 0 ~ i 做到有序
            for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
                swap(arr, j, j + 1);
            }
        }
    }

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

【插入排序——例子】：对数组数据从小到大进行排序
数组数据：1、9、10、4、5

第1次：将9与1进行比较，1<9，排序不变
第1次排序后：

第2次：将10与9进行比较，9<10，排序不变
第2次排序后：

第3次：将9与1进行比较，1<9，排序不变
第3次排序后：

第4次：将4与10进行比较，10>4，将10与4进行交换
第4次排序后：

第5次：将4与9进行比较，9>4，将9与4进行交换
第5次排序后：

第6次：将4与1进行比较，1<4，排序不变
第6次排序后：

第7次：将5与10进行比较，10>5，将10与5进行交换
第7次排序后：

第8次：将5与9进行比较，9>5，将9与5进行交换
第8次排序后：

第9次：将4与5进行比较，4<5，排序不变
第9次排序后：

第10次：将1与4进行比较，1<4，排序不变
第10次排序后：

【过程：】
想让arr[0~0]上有序，这个范围只有一个数，当然是有序的。
想让arr[0~1]上有序，所以从arr[1]开始往前看，如果arr[1]<arr[0]，就交换。否则什么也不做。
…
想让arr[0~i]上有序，所以从arr[i]开始往前看，arr[i]这个数不停向左移动，一直移动到左边的数字不再比自己大，停止移动。
最后一步，想让arr[0~N-1]上有序， arr[N-1]这个数不停向左移动，一直移动到左边的数字不再比自己大，停止移动。

【时间复杂度：】
很明显，在最差情况下，如果arr长度为N，插入排序的每一步常数操作的数量，还是如等差数列一般

所以，总的常数操作数量 = a(N^2) + bN + c (a、b、c都是常数)

所以插入排序排序的时间复杂度为O(N^2)。