1.1排序基本概念
排序：重新排列表中的元素，使表中的元素满足按关键字递增或递减的过程。
算法的稳定性：如果待排序表中有两个元素Ri、Rj，其对应的关键字keyi=keyj，且在排序前Ri在Rj前面，如果使用某一排序算法排序后，Ri仍在Rj的前面，则称这个排序算法是稳定的。
分类：在排序过程中，根据数据元素是否完全在内存中，可将排序算法分为两类。
内部排序：在排序期间元素全部存放在内存中的排序。
外部排序：在排序期间元素无法全部同时存放在内存中，必须在排序过程中根据要求不断地在内外存之间移动的排序。
1.2插入排序
基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中，直到全部记录完成。
1.2.1直接插入排序
原理：把n个待排序的元素看成一个有序表和一个无需表，开始的时候有序表只有1个元素，无序表中有n-1个元素每次从无序表中取出第一个元素，将它插入到有序表中，使之成为新的有序表，重复n-1次完成整个排序过程。
具体流程如下：
- 首先比较数组的前两个数据，并排序；
- 比较第三个元素与前两个排好序的数据，并将第三个元素放入适当的位置；
- 比较第四个元素与前三个排好序的数据，并将第四个元素放入适当的位置；
… - 直至把最后一个元素放入适当的位置
- 实例：
0.初始状态 3，1，5，7，2，4，9，6（共8个数）
有序表：3；无序表：1，5，7，2，4，9，6
1.第一次循环，从无序表中取出第一个数 1，把它插入到有序表中，使新的数列依旧有序
有序表：1，3；无序表：5，7，2，4，9，6
2.第二次循环，从无序表中取出第一个数 5，把它插入到有序表中，使新的数列依旧有序
有序表：1，3，5；无序表：7，2，4，9，6
3.第三次循环，从无序表中取出第一个数 7，把它插入到有序表中，使新的数列依旧有序
有序表：1，3，5，7；无序表：2，4，9，6
4.第四次循环，从无序表中取出第一个数 2，把它插入到有序表中，使新的数列依旧有序
有序表：1，2，3，5，7；无序表：4，9，6
5.第五次循环，从无序表中取出第一个数 4，把它插入到有序表中，使新的数列依旧有序
有序表：1，2，3，4，5，7；无序表：9，6
6.第六次循环，从无序表中取出第一个数 9，把它插入到有序表中，使新的数列依旧有序
有序表：1，2，3，4，5，7，9；无序表：6
7.第七次循环，从无序表中取出第一个数 6，把它插入到有序表中，使新的数列依旧有序
有序表：1，2，3，4，5，6，7，9；无序表：（空）
性能分析：
空间效率：仅使用常数个辅助单元，空间复杂度O(1)
时间效率：时间复杂度O(n2)
最差情况：反序，需要移动n*(n-1)/2个元素，时间复杂度O(n2)
最好情况：正序，不需要移动元素，时间复杂度O(n)
稳定性：稳定的
适用性：适用于顺序存储和链式存储的线性表
import java.util.Scanner; import java.util.Arrays; public class InsertSort { public static void insertSort(int[] arr){ int i=0,j=0,temp=0;//定义变量i,j,temp并初始化 for (i=1;i<arr.length;i++){//从第二个开始比较 temp = arr[i]; for (j=i-1;j>=0;j--){ if (arr[j]>temp){//如果前面的数大于当前数，将它后移 arr[j+1] = arr[j]; }else { break; } } arr[j+1] = temp;//一轮比较结束，将此轮确定元素放到正确位置 } System.out.println("直接插入排序："+Arrays.toString(arr)); } public static void main(String[] args) { Scanner scanner = new Scanner(System.in);//Scanner工具类键盘输入数据 while (scanner.hasNext()) { int n = scanner.nextInt(); if (n > 0) { int arr[] = new int[n]; for (int i = 0; i < n; i++) { arr[i] = scanner.nextInt(); } insertSort(arr);//调用直接插入排序insertSort方法 } } } }
