数据结构---插入排序 java
按照排序算法的稳定性分：
稳定排序：在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变
不稳定排序：经过排序后，若具有相同关键字的记录之间的相对次序发生变化
按照是否涉及数据的内、外存交换分：
内排序： 适用于记录个数不很多的小文件
外排序： 适用于记录个数太多，不能一次将其全部记录放入内存的大文件
按照策略分：排序分为 插入排序、交换排序、选择排序、归并排序、分配排序
这次重新学习的目的，就是清晰理解算法的思想，并按照不同策略进行相关算法学习，例子代码使用java书写，先加了个油！
插入排序：
1.直接插入排序
思想：将列表分为两个逻辑部分，分别是无序和有序部分。
例如数据{1,4,2,6,9,8}
1. 拿到无序序列表的第一个元素，并将其插入有序列表，由于有序列表为空，所以不用判断可直接插入。
{1} {4,2,6,9,8}
2. 拿到无序列的第一个元素，将其插入有序列表，迭代有序列表，将新的元素x插入到满足a[n+1]>x>a[n]的地方
{1,4} {2,6,9,8}
3.以此类推
{1,2,4} {6,9,8}
4.以此类推
{1,2,4,6} {9,8}
5.以此类推
{1,2,4,6,9} {8}
6.以此类推
{1,2,4,6,8,9} {}
java 代码实现：
public class InsertSort {
public static int insertsort(int[] inta){
for(int i=0;i<inta.length;i++){
int temp = inta[i];
int j=i-1;
while(j>=0&&temp<inta[j]){
inta[j+1]=inta[j];
j--;
}
inta[j+1]=temp;
}
return 0;
}
public static void main(String[] args) {
int[] a = {1,4,2,6,9,8};
for(int k=0;k<a.length;k++){
System.out.print(""+a[k]+",");
}
System.out.println();
insertsort(a);
for(int k=0;k<a.length;k++){
System.out.print(""+a[k]+",");
}
}
}
