Shell Sort

Group the data sequence into subsequences with a fixed increment based on small indices, sort each subsequence using insertion sort. As the increment gradually decreases, the number of keywords in each group increases. When the decrement reaches 1, the entire file is treated as one single group, and the algorithm terminates.

1. Select an increment sequence t1, t2, ..., tk, where ti > tj for i < j (implied by order), and tk = 1;
2. Perform k rounds of sorting on the sequence based on the number of increments in the sequence;
3. For each round of sorting, divide the sequence to be sorted into several subsequences of length m according to the corresponding increment ti, and perform direct insertion sort on each subtable separately. Only when the increment factor is 1 should the entire sequence be treated as a single table, where the table length equals the total length of the sequence.

Code Implementation

::: code-tabs
@tab Java

public class ShellSort implements IArraySort {
    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // Copy arr to avoid modifying the original parameter content
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        int gap = 1;
        while (gap < arr.length/3) {
            gap = gap * 3 + 1;
        }
        while (gap > 0) {
            for (int i = gap; i < arr.length; i++) {
                int tmp = arr[i];
                int j = i - gap;
                while (j >= 0 && arr[j] > tmp) {
                    arr[j + gap] = arr[j];
                    j -= gap;
                }
                arr[j + gap] = tmp;
            }
            gap = (int) Math.floor(gap / 3);
        }
        return arr;
    }
}

@tab JavaScript

function shellSort(arr) {
    var len = arr.length,
        temp,
        gap = 1;
    while(gap < len/3) {          // Dynamically define the interval sequence
        gap = gap*3+1;
    }
    for (gap; gap > 0; gap = Math.floor(gap/3)) {
        for (var i = gap; i < len; i++) {
            temp = arr[i];
            for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
                arr[j+gap] = arr[j];
            }
            arr[j+gap] = temp;
        }
    }
    return arr;
}

@tab Python

def shellSort(arr):
    import math
    gap=1
    while(gap < len(arr)/3):
        gap = gap*3+1
    while gap > 0:
        for i in range(gap,len(arr)):
            temp = arr[i]
            j = i-gap
            while j >=0 and arr[j] > temp:
                arr[j+gap]=arr[j]
                j-=gap
            arr[j+gap] = temp
        gap = math.floor(gap/3)
    return arr
}

@tab Go

func shellSort(arr []int) []int {
    length := len(arr)
    gap := 1
    for gap < length/3 {
        gap = gap*3 + 1
    }
    for gap > 0 {
        for i := gap; i < length; i++ {
            temp := arr[i]
            j := i - gap
            for j >= 0 && arr[j] > temp {
                arr[j+gap] = arr[j]
                j -= gap
            }
            arr[j+gap] = temp
        }
        gap = int(gap / 3) // Note: integer division in Go is implicit, but explicit cast for clarity if needed by specific type expectations; here logic holds as integers.
    }
    return arr
}

@tab PHP

function shellSort($arr){
    $len = count($arr);
    $temp = 0;
    $gap = 1;
    while($gap < $len / 3) {
        $gap = $gap * 3 + 1;
    }
    for ($gap; $gap > 0; $gap = floor($gap / 3)) {
        for ($i = $gap; $i < $len; $i++) {
            $temp = $arr[$i];
            for ($j = $i - $gap; $j >= 0 && $arr[$j] > $temp; $j -= $gap) {
                $arr[$j+$gap] = $arr[$j];
            }
            $arr[$j+$gap] = $temp;
        }
    }
    return $arr;
}

:::