【Java】插入排序

插入排序

思路

<font face=黑体>每次处理一个元素,把这个元素插入到前面已经排好序的牌中的合适位置。

代码实现

public class InsertionSort {

private InsertionSort() {}

// 插入排序

public static <E extends Comparable<E>> void sort(E[] arr) {

for (int i = 0; i < arr.length; i++) {

for (int j = i; j - 1 >= 0; j--) {

if (arr[j].compareTo(arr[j - 1]) < 0) {

swap(arr, j, j - 1);

} else {

break;

}

}

/* for (int j = i; j - 1 >= 0 && arr[j].compareTo(arr[j - 1]) < 0 ; j--) {

swap(arr, j, j - 1);

}*/

}

}

// 交换

private static <E> void swap(E[] arr, int i, int j) {

E temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

public static void main(String[] args) {

int[] dataSize = {10000, 100000};

for (int n : dataSize) {

Integer[] arr = ArrayGenerator.generateRandomArray(n, n);

SortingHelper.sortTest("InsertionSort", arr);

}

}

}

测试结果

【Java】插入排序

插入排序的一个小优化

<font face=黑体>插入排序法中的每一次 swap(交换) 都需要三次操作,这里可以把这个交换操作优化成赋值操作。但是这个优化并不能改变插入排序的时间复杂度,它的时间复杂度依然是 O(n^2)。

 // 插入排序的优化

public static <E extends Comparable<E>> void sort2(E[] arr) {

for (int i = 0; i < arr.length; i++) {

E temp = arr[i];

int j;

for (j = i; j - 1 >= 0 && temp.compareTo(arr[j - 1]) < 0; j--) {

arr[j] = arr[j - 1];

}

arr[j] = temp;

}

}

运行结果对比

【Java】插入排序

插入排序法的重要特性

<font face=黑体>插入排序法的内存循环有一个提前中止的机制,就是该元素比它前面元素还大的时候,那么循坏就会中止。<font face=黑体 color = red>所以,对于一个有序数组,插入排序的复杂度就是 O(n) 级别的。

<font face=黑体>所以对于一个近乎有序的数组,我们可以使用插入排序法来进行排序。对比,选择排序的算法复杂度永远是 O(n^2) 的。在一些高级排序的算法中,会利用插入排序的这一重要特性来进行优化。

对比测试

<font face=黑体>在不同数量级下,测试选择排序和插入排序在随机数组和有序数组下的排序时间。

public static void main(String[] args) {

int[] dataSize = {10000, 100000};

for (int n : dataSize) {

System.out.println("Random Array : ");

Integer[] arr = ArrayGenerator.generateRandomArray(n, n);

Integer[] arr2 = Arrays.copyOf(arr, arr.length);

SortingHelper.sortTest("SelectionSort", arr);

SortingHelper.sortTest("InsertionSort2", arr2);

System.out.println();

System.out.println("Ordered Array : ");

arr = ArrayGenerator.generateOrderedArray(n);

arr2 = Arrays.copyOf(arr, arr.length);

SortingHelper.sortTest("SelectionSort", arr);

SortingHelper.sortTest("InsertionSort2", arr2);

System.out.println();

}

}

对比测试结果

【Java】插入排序

_
<font face=黑体>以下是上述代码中用到的两个类:

ArrayGenerator

<font face=黑体>作用主要是生成随机的数组,具体如下所示:

public class ArrayGenerator {

private ArrayGenerator() {

}

/**

* 生成长度为 n 的有序数组

*

* @param n

* @return

*/

public static Integer[] generateOrderedArray(int n) {

Integer[] arr = new Integer[n];

for (int i = 0; i < arr.length; i++) {

arr[i] = i;

}

return arr;

}

/**

* 生成长度为 n 的随机数组,每个数字的范围是[0, bound)

*

* @param n

* @param bound

* @return

*/

public static Integer[] generateRandomArray(int n, int bound) {

Integer[] arr = new Integer[n];

Random rnd = new Random();

for (int i = 0; i < n; i++) {

arr[i] = rnd.nextInt(bound);

}

return arr;

}

}

SortingHelper

<font face=黑体>作用主要是测试各种排序算法的性能,具体如下所示:

public class SortingHelper {

private SortingHelper() {

}

/**

* 判断一个数组是否有序

*

* @param arr

* @param <E>

* @return

*/

public static <E extends Comparable<E>> boolean isSorted(E[] arr) {

for (int i = 1; i < arr.length; i++) {

if (arr[i - 1].compareTo(arr[i]) > 0) {

return false;

}

}

return true;

}

/**

* 测试排序算法的性能

*

* @param sortName

* @param arr

* @param <E>

*/

public static <E extends Comparable<E>> void sortTest(String sortName, E[] arr) {

long startTime = System.nanoTime();

if (sortName.equals("SelectionSort")) {

SelectionSort.sort(arr);

} else if (sortName.equals("InsertionSort")) {

InsertionSort.sort(arr);

} else if (sortName.equals("InsertionSort2")) {

InsertionSort.sort2(arr);

}

long endTime = System.nanoTime();

double time = (endTime - startTime) / 1000000000.0;

if (!SortingHelper.isSorted(arr)) {

throw new RuntimeException(sortName + " failed");

}

System.out.println(String.format("%s , n = %d : %f s", sortName, arr.length, time));

}

}

以上是 【Java】插入排序 的全部内容, 来源链接: utcz.com/a/97281.html

回到顶部