直接插入排序算法
基本思想：
把n个待排序的元素看成一个有序表和一个无序表，开始时有序表中只有一个元素，无序表中有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；无序表：（空）
Java实现：
package sort;
/**
* 直接插入排序 的实现
* 稳定算法
* @author 那一季的银杏叶
*
*/
public class InsertSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[] = {3,1,5,7,2,4,9,6};
new InsertSort().insertSort(a);
}
/**
* 直接插入排序算法的实现
* @param a
*/
private void insertSort(int[] a) {
// TODO Auto-generated method stub
System.out.println("———————————————————直接插入排序算法—————————————————————");
int n = a.length;
int i,j;
for(i=1;i<n;i++){
/**
* temp为本次循环待插入有序列表中的数
*/
int temp = a[i];
/**
* 寻找temp插入有序列表的正确位置
*/
for(j=i-1;j>=0 && a[j]>temp;j--){
/**
* 元素后移，为插入temp做准备
*/
a[j+1] = a[j];
}
/**
* 插入temp
*/
a[j+1] = temp;
print(a,n,i);
}
printResult(a,n);
}
/**
* 打印排序的最终结果
* @param a
* @param n
*/
private void printResult(int[] a, int n){
System.out.print("最终排序结果：");
for(int j=0;j<n;j++){
System.out.print(" "+a[j]);
}
System.out.println();
}
/**
* 打印排序的每次循环的结果
* @param a
* @param n
* @param i
*/
private void print(int[] a, int n, int i) {
// TODO Auto-generated method stub
System.out.print("第"+i+"次：");
for(int j=0;j<n;j++){
System.out.print(" "+a[j]);
}
System.out.println();
}
}
运行结果展示：
（本文仅供学习交流，如有更好的思路，欢迎留下意见供大家探讨学习~）