这两种Java插入排序算法哪个更好？

Question

这是我对插入排序算法的解决方案：

void insertionSort(int[] array) {

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

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

            if(array[j] < array[j-1]) {

                int tmp = array[j];

                array[j] = array[j-1];

                array[j-1] = tmp;

            }

        }

    }

}

这是“标准”解决方案：

void sort(int arr[]) 

    { 

        int n = arr.length; 

        for (int i=1; i<n; ++i) 

        { 

            int key = arr[i]; 

            int j = i-1; 

            while (j>=0 && arr[j] > key) 

            { 

                arr[j+1] = arr[j]; 

                j = j-1; 

            } 

            arr[j+1] = key; 

        } 

    }

我的解决方案有问题吗？它是否以任何方式降低了效率，因为到目前为止的测试表明它有效。

Answer 1

如果您设置了性能测量，您可以轻松查看哪个更快。insertionSort : [0.0, 0.0, 0.0, 0.5, 35.0, 3289.5]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;sort : [0.0, 0.0, 0.0, 0.3, 15.6, 1163.1]该sort方法比该方法快得多insertionSort，因为它与快速排序（使用枢轴）非常相似。示例代码import java.util.Arrays;import java.util.Random;import java.util.concurrent.ThreadLocalRandom;public class SortCompare {&nbsp; &nbsp; public static void main(String[] args) {&nbsp; &nbsp; &nbsp; &nbsp; int tests = 2;&nbsp; &nbsp; &nbsp; &nbsp; int runs = 10;&nbsp; &nbsp; &nbsp; &nbsp; int size = 6; // 1 -> 100,000&nbsp; &nbsp; &nbsp; &nbsp; long[][][] times = new long[tests][size][runs];&nbsp; &nbsp; &nbsp; &nbsp; double[][] avgs = new double[tests][size];&nbsp; &nbsp; &nbsp; &nbsp; for (int run = 0; run < runs; run++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.printf("Run #%d...%n", run);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int magnitude = 0; magnitude < size; magnitude++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.printf("Magnitude #%d...%n", magnitude);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int[] a = shuffle(range((int) Math.pow(10, magnitude)));&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; long start = System.currentTimeMillis();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; insertionSort(Arrays.copyOf(a, a.length));&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; times[0][magnitude][run] = System.currentTimeMillis() - start;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; long start = System.currentTimeMillis();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sort(Arrays.copyOf(a, a.length));&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; times[1][magnitude][run] = System.currentTimeMillis() - start;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < size; i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int j = 0; j < tests; j++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; avgs[j][i] = avg(times[j][i]);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; System.out.printf("insertionSort : %s%n", Arrays.toString(avgs[0]));&nbsp; &nbsp; &nbsp; &nbsp; System.out.printf("&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;sort : %s%n", Arrays.toString(avgs[1]));&nbsp; &nbsp; }&nbsp; &nbsp; private static double avg(long[] times) {&nbsp; &nbsp; &nbsp; &nbsp; long total = 0;&nbsp; &nbsp; &nbsp; &nbsp; for (long time : times) total += time;&nbsp; &nbsp; &nbsp; &nbsp; return ((double) total) / times.length;&nbsp; &nbsp; }&nbsp; &nbsp; private static int[] range(int size) {&nbsp; &nbsp; &nbsp; &nbsp; int[] a = new int[size];&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < size; i++) a[i] = i;&nbsp; &nbsp; &nbsp; &nbsp; return a;&nbsp; &nbsp; }&nbsp; &nbsp; private static int[] shuffle(int[] a) {&nbsp; &nbsp; &nbsp; &nbsp; Random rnd = ThreadLocalRandom.current();&nbsp; &nbsp; &nbsp; &nbsp; for (int i = a.length - 1; i > 0; i--) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int index = rnd.nextInt(i + 1);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int tmp = a[index];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; a[index] = a[i];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; a[i] = tmp;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return a;&nbsp; &nbsp; }&nbsp; &nbsp; private static void insertionSort(int[] array) {&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 1; i < array.length; i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int j = i; j > 0; j--) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (array[j] < array[j - 1]) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int tmp = array[j];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; array[j] = array[j - 1];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; array[j - 1] = tmp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; private static void sort(int arr[]) {&nbsp; &nbsp; &nbsp; &nbsp; int n = arr.length;&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 1; i < n; ++i) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int key = arr[i];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int j = i - 1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; while (j >= 0 && arr[j] > key) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; arr[j + 1] = arr[j];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; j = j - 1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; arr[j + 1] = key;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }}