排序基础02：插入排序法
实现泛型约束插入排序法
import java.util.Arrays;
public class Algorithm {
public static void main(String[] args) {
Integer[] arr = {2, 5, 6, 8, 1, 3};
InsertionSort.sort(arr);
System.out.println(Arrays.toString(arr));
}
}
class InsertionSort {
private InsertionSort() {}
public static void sort(E[] arr) {
for (int i = 1; i < arr.length; i++) {
/**
* 循环不变量：arr[i...n)未排序，而arr[0...i)已排序
* arr[i]从后向前依次和arr[0...i)中的元素进行对比，谁比它大就和谁互换位置，直到前面的元素都比它小
* 和选择排序不同的是，选择排序每次排好的arr[0...i)不会再变动，而插入排序会一直变动
*/
for (int j = i; j > 0; j--) {
if (arr[j].compareTo(arr[j - 1]) < 0) {
E tem;
tem = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tem;
}
/**
* 如果arr[i - 1]已经比arr[i]小了，说明左边所有数都比arr[i]小，就不用再往前比较了
*/
else {
break;
}
}
// /**
// * if()语句判断的条件可以一同写进for()循环，省去了break语句的跳转，简化代码
// */
// for (int j = i; j > 0 && arr[j].compareTo(arr[j - 1]) < 0; j--) {
//
// E tem;
// tem = arr[j];
// arr[j] = arr[j - 1];
// arr[j - 1] = tem;
// }
}
}
}
优化插入排序法
import java.util.Arrays;
public class Algorithm {
public static void main(String[] args) {
Integer[] arr = {2, 5, 6, 8, 1, 3};
InsertionSortBetter.sort(arr);
System.out.println(Arrays.toString(arr));
}
}
class InsertionSortBetter {
private InsertionSortBetter() {}
public static void sort(E[] arr) {
for (int i = 1; i < arr.length; i++) {
/**
* 循环不变量：arr[i...n)未排序，而arr[0...i)已排序
* 将arr[i]先暂存起来，从后向前依次和arr[0...i)中的元素进行对比，谁比它大谁就往后挪一位，直到前面的元素都比
* 它小，然后将arr[i]放在j这个位置
*/
E tem = arr[i];
int j;
for (j = i; j > 0 && tem.compareTo(arr[j - 1]) < 0; j--) {
arr[j] = arr[j - 1];
}
arr[j] = tem;
}
}
}
选择排序法和插入排序法的性能比较
插入排序法的复杂度也是O(n^2)
但是和选择排序相比，当一个数组本身的有序程序很高的时候，插入排序可能只要将arr[i]和arr[i + 1]对比一次就可以结束内循环，此时插入排序法的复杂度会降到O(n)；而选择排序却一定要遍历所有arr[i...n]所有的元素才能确保找到最小值
所以当数组的有序程度较高时，推荐使用插入排序
import java.util.Arrays;
import java.util.Random;
public class Algorithm {
public static void main(String[] args) {
Integer[] testScale = {10000, 100000};
for (Integer n : testScale) {
/**
* 测试随机数组排序性能
*/
Integer[] randomArr = ArrayGenerator.generatorRandomArray(n, n);
/**
* 测试有序数组排序性能
*/
Integer[] sortedArr = ArrayGenerator.generatorSortedArray(n, n);
/**
* Arrays.copyOf()方法复制数值的数值，为了测试更具有对比性
*/
Integer[] arr1 = Arrays.copyOf(randomArr, randomArr.length);
Integer[] arr2 = Arrays.copyOf(randomArr, randomArr.length);
Integer[] arr3 = Arrays.copyOf(sortedArr, sortedArr.length);
Integer[] arr4 = Arrays.copyOf(sortedArr, sortedArr.length);
System.out.println("测试随机数组排序性能");
System.out.println();
Verify.testTime("SelectionSort", randomArr);
Verify.testTime("InsertionSort", arr1);
Verify.testTime("InsertionSortBetter", arr2);
System.out.println();
System.out.println("测试有序数组排序性能");
System.out.println();
Verify.testTime("SelectionSort", sortedArr);
Verify.testTime("InsertionSort", arr3);
Verify.testTime("InsertionSortBetter", arr4);
System.out.println();
}
}
}
class InsertionSort {
private InsertionSort() {}
public static void sort(E[] arr) {
for (int i = 1; i < arr.length; i++) {
for (int j = i; j > 0; j--) {
if (arr[j].compareTo(arr[j - 1]) < 0) {
E tem;
tem = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tem;
}
else {
break;
}
}
}
}
}
class InsertionSortBetter {
private InsertionSortBetter() {}
public static void sort(E[] arr) {
for (int i = 1; i < arr.length; i++) {
E tem = arr[i];
int j;
for (j = i; j > 0 && tem.compareTo(arr[j - 1]) < 0; j--) {
arr[j] = arr[j - 1];
}
arr[j] = tem;
}
}
}
class SelectionSort {
private SelectionSort(){}
public static> void sort(E[] arr){
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j].compareTo(arr[minIndex]) < 0) {
minIndex = j;
}
}
if (i != minIndex) {
E tem;
tem = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = tem;
}
}
}
}
class ArrayGenerator {
private ArrayGenerator (){}
public static Integer[] generatorRandomArray (Integer n, Integer maxBound){
Integer[] arr = new Integer[n];
Random random = new Random();
for (int i = 0; i < n; i++) {
arr[i] = random.nextInt(maxBound);
}
return arr;
}
public static Integer[] generatorSortedArray (Integer n, Integer maxBound){
Integer[] arr = new Integer[n];
for (int i = 0; i < n; i++) {
arr[i] = i;
}
return arr;
}
}
class Verify {
private Verify (){}
public static> boolean isSorted(E[] arr){
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i].compareTo(arr[i + 1]) > 0) {
return false;
}
}
return true;
}
public static> void testTime(String AlgorithmName, E[] arr) {
long startTime = System.nanoTime();
if (AlgorithmName.equals("SelectionSort")){
SelectionSort.sort(arr);
}
if (AlgorithmName.equals("InsertionSort")) {
InsertionSort.sort(arr);
}
if (AlgorithmName.equals("InsertionSortBetter")) {
InsertionSortBetter.sort(arr);
}
long endTime = System.nanoTime();
if (!Verify.isSorted(arr)){
throw new RuntimeException(AlgorithmName + "算法排序失败！");
}
System.out.println(String.format("%s算法，测试用例为%d，执行时间：%f秒", AlgorithmName, arr.length, (endTime - startTime) / 1000000000.0));
}
}
原文：https://www.cnblogs.com/taoyuann/p/15350637.html