三.选择排序（Selection sort ） 排序原理： 1. 每一次遍历的过程中，都假定第一个索引处的元素是最小值，和其他索引处的值依次进行比较，如果当前索引处的值大于其他某个索引处的值，则假定其他某个索引处的值为最小值，最后可以找到最小值所在的索引 2.交换第一个索引处和最小值所在的索引处的值 选择排序的方法： 构造方法： Selection() ：创建 Selection 对象 成员方法： 1.public static void sort(Comparable[] a) ：对数组内的元素进行排序 2.private static boolean greater(Comparable v,Comparable w): 判断 v 是否大于 w 3.private static void exch(Comparable[] a,int i,int j) ：交换 a 数组中，索引 i 和索引 j 处的值 选择排序的时间复杂度分析： 选择排序使用了双层 for循环，其中外层循环完成了数据交换，内层循环完成了数据比较，所以我们分别统计数据 交换次数和数据比较次数。保留最高阶项，去除常数因子，时间复杂度为 O(N^2); 代码实现：
四.插入排序（Insertion sort ） 排序原理： 1.把所有的元素分为两组，已经排序的和未排序的，刚开始时将数组的首元素作为已排序区间的第一个元素，然后每次取未排序区间的元素在已排序区间找到合适的位置插入 ； 2. 找到未排序的组中的第一个元素，向已经排序的组中进行插入； 3. 倒叙遍历已经排序的元素，依次和待插入的元素进行比较，直到找到一个元素小于等于待插入元素，那么就把待插入元素放到这个位置，其他的元素向后移动一位；
插入排序方法：
构造方法：Insertion()：创建Insertion对象
成员方法：
1.public static void sort(Comparable[] a) ：对数组内的元素进行排序 2.private static boolean greater(Comparable v,Comparable w): 判断 v 是否大于 w 3.private static void exch(Comparable[] a,int i,int j) ：交换 a 数组中，索引 i 和索引 j 处的值 插入排序的时间复杂度分析 插入排序使用了双层 for循环，其中内层循环的循环体是真正完成排序的代码，所以，我们分析插入排序的时间复 杂度，主要分析一下内层循环体的执行次数即可。保留函数中的最高阶项那么最终插入排序的时间复杂度为 O(N^2). 代码实现：
五.希尔排序（Shell sorting）
排序原理：即对插入排序的优化，插排的 元素是一个一个往后搬，损耗较大；现在是一次走好几步； 1.选定一个增长量h ，按照增长量 h 作为数据分组的依据，对数据进行分组； 2.对分好组的每一组数据完成插入排序； 3.减小增长量，最小减为1 ，重复第二步操作。4.增量h一般公式：h=n/2，向下取整；增量缩小公式：h=h/2,向下取整，直到增量为1排序结束
希尔排序方法：
构造方法：Shell()：创建Shell对象
成员方法：1.public static void sort(Comparable[] a)：对数组内的元素进行排序
2.private static boolean greater(Comparable v,Comparable w):判断v是否大于w
3.private static void exch(Comparable[] a,int i,int j)：交换a数组中，索引i和索引j处的值
代码实现：
六.归并排序
排序原理：先分后治 1. 尽可能的一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素个数是1为止。 2.将相邻的两个子组进行合并成一个有序的大组； 3. 不断的重复步骤 2 ，直到最终只有一个组为止。 归并排序方法： 构成方法： Merge() ：创建 Merge 对象 成员方法： 1.public static void sort(Comparable[] a) ：对数组内的元素进行排序 2.private static void sort(Comparable[] a, int lo, int hi) ：对数组 a 中从索引 lo 到索引 hi 之间的元素进 行排序 3.private static void merge(Comparable[] a, int lo, int mid, int hi): 从索引 lo 到所以 mid 为一个子组，从索引mid+1 到索引 hi 为另一个子组，把数组 a 中的这两个子组的数据合并成一个有序的大组（从索引lo 到索引 hi ） 4.private static boolean less(Comparable v,Comparable w): 判断 v 是否小于 w 5.private static void exch(Comparable[] a,int i,int j) ：交换 a 数组中，索引 i 和索引 j 处的值 成员变量：private static Comparable[] assist ：完成归并操作需要的辅助数组 时间复杂度分析： 假设元素的个数为 n ，那么使用归并排序拆分的次数为 log2(n), 所以 共log2(n)层 ， 最终得出的归并排序的时间复杂度为：层数* 2^层数=n*层数，即log2(n)* 2^(log2(n))= log2(n)*n ,根据大 O 推导法则，忽略底数，最终归并排序的时间复杂度为O(nlogn); 代码实现：七.快速排序：
排序原理： 1. 首先 设定一个分界值 ，通过该分界值将数组分成左右两部分,为了方便，分界值可以取第一个数； 2. 将大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左边 。 3.然后，左边和右边的数据独立排序。对于左边数据，再取一个分界值，再分成左右两部分，同样在左边放置较小值，右边放置较大值。右边数据也做相同操作。 4. 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了。 快速排序方法： 构造方法： Quick() ：创建 Quick 对象 成员方法： 1.public static void sort(Comparable[] a) ：对数组内的元素进行排序 2.private static void sort(Comparable[] a, int lo, int hi) ：对数组 a 中从索引 lo 到索引 hi 之间的元素 进行排序 3.public static int partition(Comparable[] a,int lo,int hi): 对数组 a 中，从索引 lo 到索引 hi 之间的元 素进行分组，并返回分组界限对应的索引 4.private static boolean less(Comparable v,Comparable w): 判断 v 是否小于 w 5.private static void exch(Comparable[] a,int i,int j) ：交换 a 数组中，索引 i 和索引 j 处的值 时间复杂度分析： 快速排序的一次切分从两头开始交替搜索，直到left 和 right 重合。所以一次切分算法的时间复杂度为 O(n), 但整个快速排序的时间复杂度和切分的次数相关。 最优情况 ：每一次切分选择的基准数字刚好将当前序列等分， 共切分 logn 次，所以 时间复杂度为 O(nlogn)； 最坏情况 ：每次切分选择的数是数组n中的最大或最小数，那么总共就得切分n 次，所以，最坏情况下，快速排序的时间复杂度为 O(n^2)；代码实现：
八.排序算法的稳定性
稳定性的定义：若数组a，有两个相同的元素A和B，且A初始时排在B的前面，在使用某种排序算法排序后，依旧能够保证A元素在B元素的前面，那么就说该算法是稳定的。
常见的算法中，冒泡排序，插入排序，归并排序都是稳定的；
而选择排序，希尔排序，快速排序都是不稳定的。
九.排序算法的时空复杂度总结
