0

我很难理解我的代码是否产生了正确数量的交换（交换）和比较。对于所有三种情况，我得到相同的数字，这与插入排序不同。据我了解，shell 排序是一种改进的插入，它对间隙排序的数字集执行插入排序，这让我怀疑这些值是否正确。

我试过在其他地方计算它们，但我相信我把它们放在正确的地方。我得到的值的唯一区别是当我改变差距时，这显然会改变算法的效率，但这是唯一改变效率的事情吗？还是我的价值观不正确？

int Sort(int arr[]) 
    { 
        int n = arr.length; 
        int exchanges = 0, comparisons = 0;

        // Start with a big gap, then reduce the gap 
        for (int gap = n/2; gap > 0; gap = gap*3 + 1) 
        { 
            //gapped insertion sort 
            for (int i = gap; i < n; i += 1) 
            { 
                // add a[i] to the elements that have been gap 
                // sorted save a[i] in temp and make a hole at 
                // position i 
                exchanges++;
                int temp = arr[i]; 

                // shift earlier gap-sorted elements up until 
                // location for a[i] is found 
                int j; 
                for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) 
                    arr[j] = arr[j - gap]; 
                comparisons++;
                // put temp correct location 
                arr[j] = temp; 
                exchanges++;
            } 
        }
    }

我希望随机值集得到不同的结果。我知道间隙序列对其进行了部分排序，但我得到 Exchanges(Swaps) - 10 和比较 - 5 的值，从 1-10 升序、降序和随机值。这让我不敢相信我的价值观是正确的。shell排序是否使插入排序输入不敏感？任何帮助/输入表示赞赏。

4

0 回答 0