在C中實現shellort算法

Question

void shellsort(int v[], int n) 
{ 
    int gap, i, j, temp; 
    for (gap = n/2; gap > 0; gap /= 2) 
     for (i = gap; i < n; i++){ 
      for (j=i-gap; j>=0 && v[j]>v[j+gap]; j-=gap) { 
       temp = v[j]; 
       v[j] = v[j+gap]; 
       v[j+gap] = temp; 
      } 
     } 
    } 
} 

在這個shellsort()函數中，我們有j-=gap。假設n = 10，差距總是5和j從0,1,2,3,4...增加。

這意味着該內for循環運行的前5次，將一個負的值返回到j（例如0-5=-5），因此，因爲j不會大於或等於0，它將只運行一次。

它的工作原理正是我們想要的。我們不想多次交換，因爲如果我們這樣做了，我們只會再次交換相同的兩個值，從而導致不必要的冗餘。

所以，我在想，爲什麼我們不能在循環中忽略j-=gap，因爲它似乎並不影響功能。包含j-=gap是否有特殊原因？

我在這裏錯過了什麼嗎？

Answer 1

這可能有助於查看插入排序作爲參考，以查看其來源。在插入排序中，我們從左向右掃描，將每個元素向後交換，直到它大於前面的元素（或者它返回到數組的開始位置）。該算法的僞代碼如下所示：

for (int i = 1; i < n; i++) { 
    for (int j = i - 1; j > 0 && A[j + 1] > A[j]; j--) { 
     swap(A[j], A[j - 1]); 
    } 
} 

在陣列中的所有元素的外環的範圍，稱「把每一個在適當位置。」內部循環說：「只要前面有一個元素，並且該元素大於它，就保持當前元素與之前交換的元素交換。」在這裏，使用+1，++，-1和 - 是因爲我們一直在查看緊接在當前元素之前的元素。

在shellort中，除了我們不使用步長大小之外，我們在該數組上運行該算法的多次通過。相反，我們使用稱爲間隙量的一定量的步長。因此，希爾排序看起來是這樣的：

for (each gap size) { 
    for (int i = gap; i < n; i += gap) { 
     for (int j = i - gap; j > 0 && A[j + gap] > A[j]; j -= gap) { 
     swap(A[j], A[j - 1]); 
     } 
    } 
} 

的想法是，每一個元素應該與之前它gap元素的元素連續進行對比。如果它小於這個數字，我們想把它與前面的元素交換，但是需要重複地將它與它之前的新元素進行比較。

作爲一個例子，假設我們正在shellsorting這個數組長度爲6的：

6 5 4 3 2 1 

希爾排序（gap = 3）的第一遍之後，將陣列看起來像這樣：

3 2 1 6 5 4 

現在，想象一下，我們用gap = 1進行shellort的第二次傳遞。內循環現在說「每個元素反覆交換到前面，直到它休息。」如果您從該循環中刪除j -= gap步驟，則將每個元素與直接在其之前的元素進行比較。這將導致以下結果。在每個這些快照，克拉指其中的互換正在尋找：

3 2 1 6 5 4 -> 2 3 1 6 5 4 
^^

2 3 1 6 5 4 -> 2 1 3 6 5 4 
^^ 

2 1 3 6 5 4 
    ^^ 

2 1 3 6 5 4 -> 2 1 3 5 6 4 
    ^^ 

2 1 3 5 6 4 -> 2 1 3 5 4 6 
     ^^ 

注意，所得到的陣列未被排序。但是，如果我們把後面的j -= gap代碼混進去，那麼下面會發生，而不是：

3 2 1 6 5 4 -> 2 3 1 6 5 4 
^^

2 3 1 6 5 4 -> 2 1 3 6 5 4 -> 1 2 3 6 5 4 
^^   ^^ 

1 2 3 6 5 4 
    ^^ 

1 2 3 6 5 4 -> 1 2 3 5 6 4 
    ^^ 

1 2 3 5 6 4 -> 1 2 3 5 4 6 -> 1 2 3 4 5 6 
     ^^   ^^ 

正如你所看到的，現在一切都被正確排序。