抉择排序

抉择排序 (Selection Sort) 是一种十分简单明了的排序算法，其基本思路是：假如一个数组有 n 个数，从第一个数开始，遍历一遍找到最小的一个数的下标，将最小的数与第一个数替换地位，这样第一个数的地位就排好了，接下来从第二个数开始遍历找到从 2 到 n 中最小的数与第二个数做替换，如此重复，晓得第 n-1 个数也排好序了，整个数组排序就完结了。

示意图

代码示例：

public class SelectionSort {public static void sort(int[] arr) {for (int i = 0; i < arr.length - 1; i++) {
            int mini = i;
            for (int j = i+1; j < arr.length; j++) {if(arr[j] < arr[mini]) {mini = j;}
            }
            swap(arr, i, mini);
        }
    }
}

工夫复杂度和空间复杂度

算法第一次循环执行 n-1 次，第二次循环执行 n-2 次，以此类推，直到排序实现大概执行了 (n-1) + (n-2) + ... + 2 + 1，这是一个等差数列，依据等差数列公式能够得出执行了 $\frac{n^2}{2} – \frac{n}{2}$ 次，疏忽常数项和低次项失去工夫复杂度 $O(n^2)$

依据算法的计算过程，能够晓得不论是什么数组都要执行 $\frac{n^2}{2} – \frac{n}{2}$，其最好和最差的状况下工夫复杂度都是 $O(n^2)$

算法除开一些长期变量并没有应用一些额定空间，因而空间复杂度是 $O(1)$

稳定性

因为算法是间接将数组中找到的最初一个最小的数与第一个数替换，因而相等的两个数的程序会在替换之后扭转，所以抉择排序是一个不稳固的排序算法

优化

在一次循环遍历中同时找到最大和最小值，别离与最初一位和第一位数进行替换，缩小循环的次数。尽管如此，其工夫复杂度任然是 $O(n^2)$

代码示例：

public static void sort(int[] arr) {
     int len = arr.length;
     for (int i = 0; i < len/2; i++) {
        int mini = i;
        int maxi = i;
        for (int j = i + 1; j < len-i; j++) {if (arr[j] < arr[mini]) {mini = j;}
            if (arr[j] > arr[maxi]) {maxi = j;}
        }
        swap(arr, i, mini);
        // 留神在最大值替换前有可能曾经被最小值替换
        if (maxi == i) {maxi = mini;}
        swap(arr, len-1 - i, maxi);
    }
}

冒泡排序

冒泡排序也是简略排序的一种，其算法思路是：假如一个数组的长度为 n，比拟第一个数和第二个数，若第一个数大于第二个数，替换两个数，再比拟第二个数与第三个数的大小，大于则替换，同样地比拟剩下的数，最初，最大的数将会到数组开端，第 n 个数曾经排好序了，再对 1 ~ n-1 的数做雷同操作，1 ~ n-1 中最大的数会到 n-1 的地位，n-1 ~ n 是排好序的，反复这个 “ 冒泡 ” 过程，直到排序（若一次循环中未产生过一次替换能够提前结束排序）。

示意图

如上图所示，5 8 排好序之后，剩下的 1 3 4 进行排序，同样的一次循环后将不会产生替换，阐明剩下局部曾经有序，此时能够提前结束排序。

代码示例

public class BubbleSort {public static void sort(int[] arr) {for (int i = arr.length; i > 1; i--) {
            boolean flag = true;
            for (int j = 1; j < i; j++) {if (arr[j-1] > arr[j]) {swap(arr, j-1, j);
                    flag = false;
                }
            }
            if (flag) {break;}
        }
    }
}

工夫复杂度和空间复杂度

冒泡排序在个别状况下，须要进行两层嵌套循环，第一次循环执行 n-1 次，第二次执行 n-2 次 …，直到最初大概执行了 (n-1) + (n-2) + ... + 2 + 1，同样是等差数列，因而工夫复杂度为 $O(n^2)$。最差状况下其工夫复杂度为 $O(n^2)$，而如果程序中做了优化，在未产生替换时提前结束排序，则只需执行一次循环，所以最好状况的工夫复杂度是 $O(n)$。

因为除了局部长期变量外，没有用到其余额定空间，所以其空间复杂度为 $O(1)$。

稳定性

在冒泡排序算法中，相邻两个数进行比拟时，相等的数将不会进行替换，因而能够保障相等的数在排序后的程序不变，是一种稳固的排序算法。

插入排序

插入排序是简略排序中的最初一种，插入排序顾名思义，相似于持有一手乱序的扑克牌，每次从无序的牌中取出一张插入有序的牌中，随着无序的牌组缩小，整副牌趋于有序。其基本思路是：假如数组长度为 n，从第二个数开始，同前一个数进行比拟，若小于前一个数则替换，否则进行插入，再从第三个数开始往前面曾经有序的局部插入，反复这个步骤，直到最初一个数插入实现，数组有序。

示意图

代码示例

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

下面的代码须要每次进行替换，能够稍加改良：

public class InsertSort {public static void sort(int[] arr) {for (int i = 1; i < arr.length; i++) {
            int j = i;
            int temp = arr[j];
            while (j > 0 && temp < arr[j-1]) {arr[j] = arr[j-1];
                j--;
            }
            arr[j] = temp;
        }
    }
}

工夫复杂度和空间复杂度

插入排序算法同样的应用到了嵌套循环，个别状况下整个算法大概执行了 1 + 2 + ... + (n-2) + (n-1)，同样的工夫复杂度是 $O(n^2)$，然而插入排序要比冒泡排序少了许多比拟和替换的过程，会快得多，而且在比拟有序的状况下，所用的工夫会比拟少，最好的状况下只需循环一次，因而最好工夫复杂度为 $O(n)$。

同样的插入排序的空间复杂度为 $O(1)$。

稳定性

插入排序通过比拟相邻元素的大小进行替换，因而同样是稳固的。

总结

三种简略排序算法的工夫复杂度都是 $O(n^2)$，空间复杂度是 $O(1)$，冒泡排序和插入排序和插入排序的最好工夫复杂度是 $O(n)$，是稳固排序，抉择排序的最好工夫复杂度是 $O(n^2)$，是不稳固排序，同时插入排序要比冒泡排序快一些，因而在数据量小时能够应用简略排序，优先应用插入排序。