java - 这是 Java 插入排序的代码吗？为什么要使用额外的变量？

Question

我刚刚编写了以下代码，我不确定它是否是 Java 中插入排序的正确实现（它看起来与冒泡排序太相似了，我无法确定）。

public static void insertionsort (int[] arr){
    int temp;
    for (int i = 0; i<arr.length; i++){
            for (int j = i+1; j>=0; j--){
            
             if (arr[j]<arr[j-1]){
                temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
            }
                            
         }
        
    }
    
}

当我将我的解决方案与在线解决方案进行比较时，我注意到它们都使用变量来存储 arr[i]。例如：

void sort(int arr[]) 
{ 
    int n = arr.length; 
    for (int i = 1; i < n; ++i) { 
        int key = arr[i]; 
        int j = i - 1; 

        /* Move elements of arr[0..i-1], that are 
           greater than key, to one position ahead 
           of their current position */
        while (j >= 0 && arr[j] > key) { 
            arr[j + 1] = arr[j]; 
            j = j - 1; 
        } 
        arr[j + 1] = key; 
    } 
} 

这个关键变量的目的是什么？是不是有点多余？

标签： javainsertion-sort

Answer 1

关键变量的目的是保存将在内部循环之后插入到其排序位置的值。现在看来，您的解决方案不足以用于插入排序。