插入排序算法java实现，如下采用100万个随机长度的随机数组进行了验证
package sort;
import java.util.Arrays;
public class InsertSort {
public static void swap(int[] arr,int i,int j)
{
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
public static void printArray(int[] arr)
{
for(int elem:arr)
{
System.out.print(elem+"\t");
}
System.out.println();
}
public static void insertSort(int[] arr)
{
if(arr==null || arr.length<2)
{
return;
}
for(int i=1;i<arr.length;i++)
{
for(int j=i;j>0;j--)
{
if (arr[j]<arr[j-1])
{
swap(arr,j,j-1);
}
else
{
break;
}
}
}
}
public static int[] generateRandomArray(int maxSize,int maxValue)
{
int[] arr=new int[(int)((maxSize+1)*Math.random())];
for(int i=0;i<arr.length;i++)
{
arr[i]=(int)((maxValue+1)*Math.random()-(int)(maxValue*Math.random()));
}
return arr;
}
public static int[] copyArray(int[] arr)
{
int[] arr2=new int[arr.length];
for(int i=0;i<arr.length;i++)
{
arr2[i]=arr[i];
}
return arr2;
}
public static boolean arrayIsEqual(int[] arr1,int[] arr2)
{
if(arr1.length != arr2.length)
{
return false;
}
else
{
for(int i=0;i<arr1.length;i++)
{
if (arr1[i]!=arr2[i])
{
printArray(arr1);
printArray(arr2);
return false;
}
}
return true;
}
}
public static void main(String[] args) {
int testTime=1000000;
int maxSize=100;
int maxValue=100;
boolean succeed=true;
for(int i=0;i<testTime;i++)
{
int[] arr1=generateRandomArray(maxSize,maxValue);
int[] arr2=copyArray(arr1);
insertSort(arr1);
Arrays.sort(arr2);
if(!arrayIsEqual(arr1,arr2))
{
succeed=false;
break;
}
}
System.out.println(succeed?"Nice":"Failed!");
int[] arr=generateRandomArray(maxSize,maxValue);
printArray(arr);
insertSort(arr);
printArray(arr);
}
}
执行结果为：
Nice
51 -54 -45 -37 57 3 -51 10 87 46 14 20 -61 7 -11 -49 -84 -16 -56 21 -8 51 45 -35
-84 -61 -56 -54 -51 -49 -45 -37 -35 -16 -11 -8 3 7 10 14 20 21 45 46 51 51 57 87
