希爾排序演算法

希爾排序是一種高效的排序演算法，它基於插入排序演算法。該演算法避免了插入排序中可能出現的大量位移，尤其是在較小值位於最右側且需要移動到最左側的情況。

該演算法首先對間隔較大的元素進行插入排序，然後對間隔較小的元素進行排序。這個間隔被稱為**步長**。步長的計算基於Knuth公式：

h = h * 3 + 1
where −
   h is interval with initial value 1

對於中等規模的資料集，該演算法效率很高，其平均和最壞情況下的時間複雜度均為O(n)，其中**n**是元素個數。

希爾排序演算法

以下是希爾排序演算法：

1. Initialize the value of h.
2. Divide the list into smaller sub-list of equal interval h.
3. Sort these sub-lists using insertion sort.
4. Repeat until complete list is sorted.

虛擬碼

以下是希爾排序的虛擬碼：

procedure shellSort()
   A : array of items

   /* calculate interval*/
   while interval < A.length /3 do:
      interval = interval * 3 + 1
   end while

   while interval > 0 do:
      for outer = interval; outer < A.length; outer ++ do:

         /* select value to be inserted */
         valueToInsert = A[outer]
         inner = outer;
            
            /*shift element towards right*/
            while inner > interval -1 &&  A[inner - interval] 
			>= valueToInsert do:
               A[inner] = A[inner - interval]
               inner = inner – interval
            end while
         
         /* insert the number at hole position */
         A[inner] = valueToInsert
         end for
   
   /* calculate interval*/
   interval = (interval -1) /3;
   end while
end procedure

示例

讓我們考慮以下示例，瞭解希爾排序的工作原理。我們使用前面示例中相同的陣列。為了方便理解，我們將步長設為4。建立一個虛擬子列表，包含所有間隔為4位置的元素。這些元素為{35, 14}, {33, 19}, {42, 27}和{10, 14}

我們比較每個子列表中的元素，並在原陣列中交換它們（如有必要）。此步驟後，新陣列應如下所示：

然後，我們將步長設為2，這將生成兩個子列表 - {14, 27, 35, 42}, {19, 10, 33, 44}

我們比較並交換原陣列中需要的元素。此步驟後，陣列應如下所示：

最後，我們使用步長為1的值對其餘陣列進行排序。希爾排序使用插入排序對陣列進行排序。

以下是分步說明：

我們看到只需要四次交換就能對其餘陣列進行排序。

實現

希爾排序是一種高效的排序演算法，它基於插入排序演算法。該演算法避免了插入排序中可能出現的大量位移，尤其是在較小值位於最右側且需要移動到最左側的情況。

#include <stdio.h>
void shellSort(int arr[], int n){
   int gap, j, k;
   for(gap = n/2; gap > 0; gap = gap / 2) { //initially gap = n/2, decreasing by gap /2
      for(j = gap; j<n; j++) {
         for(k = j-gap; k>=0; k -= gap) {
            if(arr[k+gap] >= arr[k])
               break;
            else {
               int temp;
               temp = arr[k+gap];
               arr[k+gap] = arr[k];
               arr[k] = temp;
            }
         }
      }
   }
}
int main(){
   int n;
   n = 5;
   int arr[5] = {33, 45, 62, 12, 98}; // initialize the array
   printf("Array before Sorting: ");
   for(int i = 0; i<n; i++)
      printf("%d ",arr[i]);
   printf("\n");
   shellSort(arr, n);
   printf("Array after Sorting: ");
   for(int i = 0; i<n; i++)
      printf("%d ", arr[i]);
   printf("\n");
}

Array before Sorting: 33 45 62 12 98
Array after Sorting: 12 33 45 62 98

#include<iostream>
using namespace std;
void shellSort(int *arr, int n){
   int gap, j, k;
   for(gap = n/2; gap > 0; gap = gap / 2) { //initially gap = n/2, decreasing by gap /2
      for(j = gap; j<n; j++) {
         for(k = j-gap; k>=0; k -= gap) {
            if(arr[k+gap] >= arr[k])
               break;
            else {
               int temp;
               temp = arr[k+gap];
               arr[k+gap] = arr[k];
               arr[k] = temp;
            }
         }
      }
   }
}
int main(){
   int n;
   n = 5;
   int arr[5] = {33, 45, 62, 12, 98}; // initialize the array
   cout << "Array before Sorting: ";
   for(int i = 0; i<n; i++)
      cout << arr[i] << " ";
   cout << endl;
   shellSort(arr, n);
   cout << "Array after Sorting: ";
   for(int i = 0; i<n; i++)
      cout << arr[i] << " ";
   cout << endl;
}

Array before Sorting: 33 45 62 12 98
Array after Sorting: 12 33 45 62 98

import java.io.*;
import java.util.*;
public class ShellSort {
   public static void main(String args[]) {
      int n = 5;
      int[] arr = {33, 45, 62, 12, 98}; //initialize an array
      System.out.print("Array before Sorting: ");
      for(int i = 0; i<n; i++)
         System.out.print(arr[i] + " ");
      System.out.println();
      int gap;
      for(gap = n/2; gap > 0; gap = gap / 2) { //initially gap = n/2, decreasing by gap /2
         for(int j = gap; j<n; j++) {
            for(int k = j-gap; k>=0; k -= gap) {
               if(arr[k+gap] >= arr[k])
                  break;
               else {
                  int temp;
                  temp = arr[k+gap];
                  arr[k+gap] = arr[k];
                  arr[k] = temp;
               }
            }
         }
      }
      System.out.print("Array After Sorting: ");
      for(int i = 0; i<n; i++)
         System.out.print(arr[i] + " ");
      System.out.println();
   }
}

Array before Sorting: 33 45 62 12 98
Array After Sorting: 12 33 45 62 98

def shell_sort(array,n):
   gap = n//2 #using floor division to avoid float values as result
   while gap > 0:
      for i in range(int(gap),n):
         temp = array[i]
         j = i
         while j >= gap and array[j-gap] >temp:
            array[j] = array[j-gap]
            j -= gap
            array[j] = temp
      gap = gap // 2 #using floor division to avoid float values as result

arr = [33, 45, 62, 12, 98]
n = len(arr)
print("Array before Sorting: ")
print(arr)
shell_sort(arr, n);
print("Array after Sorting: ")
print(arr)

Array before Sorting: 
[33, 45, 62, 12, 98]
Array after Sorting: 
[12, 33, 45, 62, 98]