三.插入排序介绍
插入排序的基本思路是每次插入一个元素，每一趟完成对一个待排元素的放置，直到全部插入完成。
直接插入排序
直接插入排序是一种最简单的排序方法，过程就是将每个待排元素逐个插入到已经排好的有序序列中。
折半插入排序
由于在插入排序的过程中，已经生成了一个（排好的元素组成的）有序数列。所以在插入待排元素时可以使用折半查找的方式更快速的确定新元素的位置，当元素个数较多时，折半插入排序优于直接插入排序。
希尔排序
希尔排序可以看做是分组插入的排序方法，把全部元素分成几组（等距元素分到一组），在每一组内进行直接插入排序。然后继续减少间距，形成新的分组，进行排序，直到间距为1时停止。
四. 伪代码约定
伪代码是用来描述算法执行的步骤，不会具体到某一种语言，为了表达清晰和标准化，会有一些约定的含义：
缩进：表示块结构，如循环结构或选择结构，使用缩进来表示这一部分都在该结构中。
循环计数器：对于循环结构，在循环终止时，计数器的值应该为第一个超出界限的值。
to：表示循环计数器的值增加。
downto：表示循环计数器的值减少。
by：循环计数器的值默认变化量为1，当大于1时可以使用by。
变量默认是局部定义的。
数组元素访问：通过"数组名[下标]"形式，在伪代码中，下标从1开始（"A[1]“代表数组A的第一个元素）。
子数组：使用”…"来代表数组中的一个范围，如"A[i…j]"代表从第i个到第j个元素组成的子数组。
对象与属性：复合的数据会被组织成对象，如链表包含后继（next）和存储的数据（data）,使用“对象名 + 点 + 属性名”。
特殊值NIL：表示指针不指向任何对象，如二叉树节点无子孩子可认为左右子节点信息为NIL。
return：返回到调用过程的调用点，在伪代码中允许返回多个值。
and和or：与运算和或运算默认短路，即如果已经能够确定表达式结果时，其他条件不会去判断或执行。
五、选择排序
1. 选择排序介绍
选择排序的核心思想是：每一趟从无序区中选出关键字最小的元素，按顺序放在有序区的最后（生成新的有序区，无序区元素个数减1），直到全部排完为止。
直接选择排序
也称简单选择排序，整个过程就是每一趟都将无序区中的所有元素进行逐一比较，找到最小的元素，与无序区中的首个元素进行交换，有序区长度加1，无序区长度减1。重复以上步骤，直到所有的元素均已排好。
树形选择排序
也称锦标赛排序，是为了优化每次在无序区中确定最小元素时比较次数过多的问题。核心思想是借助树形结构对整个序列进行两两比较，将数值较小的元素作为优胜者上升到父节点。最后能够在树形结构中记录每一次优胜者之间的关系，按规则取出即可。
堆排序
堆排序是对树形选择排序的优化，由于树形选择排序需要花费较多的存储空间，堆排序的主要思想是构建一个小顶堆（升序排列中）。整个的过程就是不断的弹出堆顶元素，归入有序区，然后继续将堆中剩余元素调整为小顶堆，重复这个过程，直到排好所有元素。
2. 直接选择排序
输入
n个数的序列，通常直接存放在数组中，可能是任何顺序。
输出
输入序列的一个新排列，满足从小到大的顺序（默认讨论升序，简单的修改就可以实现降序排列）。
算法说明
直接选择排序的主要步骤是：在第1趟中，从n个记录中找出关键字最小的记录与第1个记录交换；在第2趟中，从n-1个记录中找出关键字最小的记录与第2个记录交换；可以归纳为：在第i趟中，从n-i+1个记录中找出关键字最小的记录与第i个记录交换；直到完成i=n-1时的操作，此时整个序列有序。
算法流程
如果使用直接选择排序对元素个数为n的序列进行排序，需要进行n-1趟排序。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ciQfUSPU-1659763128775)(https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/a520c7cacf7c48cf945ddff9f32a3fe4~tplv-k3u1fbpfcp-zoom-1.image)]
第1趟：找出最小元素 5，与第1个元素38交换 -> 5，38，47，15，36，26
第2趟：找出最小元素15，与第2个元素38交换 -> 5，15，47，38，36，26
第3趟：找出最小元素26，与第3个元素47交换 -> 5，15，26，38，36，47
第4趟：找出最小元素36，与第4个元素38交换 -> 5，15，26，36，38，47
第5趟：找出最小元素38，已在对应位置无需交换 -> 5，15，26，36，38，47
3. 伪代码
for i = 1 to n - 1 k = i for j = i + 1 to n if A[j] < A[k] k = j if k != i exchange A[i] with A[k]
六、算法实践
1. 算法实现
输入数据（input）：11，34，20，10，12，35，41，32，43，14
Java源代码
需要注意源代码与伪代码的区别，请查看文章开头补充的概念部分，这里不做过多说明。
public class SelectSort { public static void main(String[] args) { // input data int[] a = {11,34,20,10,12,35,41,32,43,14}; // 调用选择排序 sort(a); // 查看排序结果 for (int data : a){ System.out.print(data + "\t"); } } private static void sort(int[] a){ // 外层循环用于控制循环的趟数 for (int i = 0;i < a.length - 1;i++){ int k = i; // 内层循环的作用是在无序区中选出最小的元素并记录 for (int j = i + 1;j < a.length;j++){ if (a[j] < a[k]) { k = j; } } // 如果本轮选出的最小元素没有在对应的位置上则交换 if (k != i){ int tmp = a[i]; a[i] = a[k]; a[k] = tmp; } } } }
执行效果
输出数据（output）：10，11，12，14，20，32，34，35，41，43
2. 时间复杂度
了解了算法的核心思想后可以发现，整体的排序趟数（外循环）与每趟排序中的元素比较次数（内循环）均和序列的初始顺序无关，因此时间复杂度T(n)= n ( n − 1 ) 2 \frac{n(n-1)}{2} 2n(n−1)=O( n 2 n^{2} n2) 。
3. 空间复杂度
算法在执行过程中只需要定义的几个临时变量，所以空间复杂度为常数级：O(1) 。
