插入排序
插入排序的算法描述是一种简单直观的排序算法，他的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
时间复杂度：O(n^2)空间复杂度：O(1)稳定性：稳定
package 排序算法
;
import java
.util
.Arrays
;
public class insertionSort {
public static void main(String
[] args
) {
int arr
[]={9,1,8,2,7,3,6,4,5};
lnsertionSortUpper(arr
);
System
.out
.println(Arrays
.toString(arr
));
}
private static void lnsertionSortUpper(int[] arr
) {
int e
=0;
int j
=0;
for (int i
=1;i
<arr
.length
;i
++){
e
=arr
[i
];
for (j
=i
;j
>0&&arr
[j
-1]>e
;j
--){
arr
[j
]=arr
[j
-1];
}
arr
[j
]=e
;
}
}
private static void lnsertionSort(int[] arr
) {
for (int i
=1;i
<arr
.length
;i
++){
for (int j
=i
;j
>0&&arr
[j
-1]>arr
[j
];j
--){
swap(arr
,j
,j
-1);
}
}
}
private static void swap(int[] arr
, int j
, int i
) {
int temp
=arr
[i
];
arr
[i
]=arr
[j
];
arr
[j
]=temp
;
}
}
执行结果
[1, 2, 3, 4, 5, 6, 7, 8, 9]
选择 冒泡 插入测试
package 排序算法
;
import java
.util
.Arrays
;
import java
.util
.Random
;
public class TestSort {
public static int[] getTotalRandom(){
Random random
=new Random();
int [] arr
=new int[10000];
for (int i
=0;i
<arr
.length
;i
++){
arr
[i
]=random
.nextInt(10000);
}
return arr
;
}
public static void main(String
[] args
) {
int [] arr1
=getTotalRandom();
int [] arr2
= Arrays
.copyOf(arr1
, arr1
.length
);
int [] arr3
= Arrays
.copyOf(arr1
, arr1
.length
);
testSelectionSort(arr1
);
testBubbleSort(arr2
);
testInsertSort(arr3
);
}
private static void testInsertSort(int[] arr3
) {
long startTime
=System
.currentTimeMillis();
BubbleSort
.bubbleSort(arr3
);
long endTime
=System
.currentTimeMillis();
System
.out
.println("冒泡排序"+(endTime
-startTime
));
}
private static void testBubbleSort(int[] arr2
) {
long startTime
=System
.currentTimeMillis();
insertionSort
.lnsertionSortUpper(arr2
);
long endTime
=System
.currentTimeMillis();
System
.out
.println("插入排序"+(endTime
-startTime
));
}
private static void testSelectionSort(int[] arr
) {
long startTime
=System
.currentTimeMillis();
SelectionSort
.selectionSort(arr
);
long endTime
=System
.currentTimeMillis();
System
.out
.println("选择排序"+(endTime
-startTime
));
}
}
执行结果
选择排序
183
插入排序
16
冒泡排序
148
