1、直接插入排序
1）原理说明：直接插入排序是一种最简单的插入排序方法，它的基本思想是，仅有一个元素的序列总是有序的，因此，对n 个记录的序列，可从第二个元素开始直到第n 个元素，逐个向有序序列中执行插入操作，从而得到n 个元素按关键字有序的序列。
2）代码实现如下：
package com.test.sort;
public class InsertSort
{
private static void sort(int[] data)
{
for (int i = 1; i < data.length; i++)
{
int temp = data[i];
int j = i - 1;
while (j >= 0 && temp < data[j])
{
data[j + 1] = data[j];
j--;
}
data[j + 1] = temp;
}
}
public static void main(String[] args)
{
int[] data = new int[] { 3, 5, 55, 34, 67, 3, 78, 3423, 675, 4567 };
sort(data);
System.out.print("Select sort result is: {");
for (int temp : data)
{
System.out.print(temp + " ");
}
System.out.print("}");
}
}
2、折半插入排序
1）原理说明：折半插入排序是在直接插入排序的基础上，不断对半二分有序序列来寻找插入位置，即搜索插入位置的方法可以使用折半查找实现，是对直接插入排序的一种改进。
2）代码实现如下：
package com.test.sort;
public class binaryInsertSort
{
private static void sort(int[] data)
{
for (int i = 1; i < data.length; i++)
{
int temp = data[i];
int low = 0;
int high = i - 1;
while (low <= high)
{
int mid = (low + high) / 2;
if (temp < data[mid])
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
for (int j = i - 1; j > high; j--)
{
data[j + 1] = data[j];
}
data[high + 1] = temp; // 或者data[low] = temp;
}
}
public static void main(String[] args)
{
int[] data = new int[] { 3, 5, 55, 34, 67, 3, 78, 3423, 675, 4567 };
sort(data);
System.out.print("Select sort result is: {");
for (int temp : data)
{
System.out.print(temp + " ");
}
System.out.print("}");
}
}