插入排序代码复核

Question

这是我的插入排序代码。这段代码可以工作，但是这是编写插入排序的方式吗？我看过很少的教程，但他们以不同的方式来做。

int thirdArray[] = { 0, 22, 1, 10, 8, 5,39 };
for (int i = 0; i < thirdArray.length - 1; i++) {
    for (int j = i + 1; j > 0; j--) {
        if (thirdArray[j] < thirdArray[j - 1]) {
            int index = thirdArray[j];
            thirdArray[j] = thirdArray[j - 1];
            thirdArray[j - 1] = index;
        }
    }
}
for (int number : thirdArray) {
    System.out.print(number + "\t");
}

Answer 1

在Java7中，现在做排序是如此简单。

  Arrays.sort(thirdArray);

这将对已排序的数组元素进行排序。

Answer 2

在您的代码中，您为交换操作占用了额外的空间。然而，这是一种有效的方法，但您可以通过以下方式对其进行优化

    int thirdArray[] = { 0, 22, 1, 10, 8, 5,39 };
    int key,j;
    for(int i = 1 ; i < thirdArray.length ; i++)
    {
        key = thirdArray[i];
        j = i - 1;

        while(j >=0 && key < thirdArray[j])
        {
            thirdArray[j+1] = thirdArray[j];
            j--;
        }
        arr[j+1] = key;
    }
}

在上面的代码中，您从第一个索引开始与它的前一个索引进行比较，如果它较小，则覆盖它的值(您已经将当前值保存在key中)，最后将它放在正确的位置。我们可以保证在排序之后，左边的所有元素都是排序的。插入排序具有最坏情况的性能:О(n^2)最佳情况的性能: O(n)。通过交换，我们增加了更多的复杂性，你可以避免它。