4.shellSort.md

Hill sort

Hill sort, also known as the decreasing-increment sorting algorithm, is a more efficient and improved version of insertion sort. But Hill sort is a non-stable sorting algorithm.

Hill sort is an improved method based on the following two properties of insertion sort:

• Insertion sort has high efficiency when operating on almost sorted data, that is, it can achieve the efficiency of linear sorting;
• But insertion sort is generally inefficient, because insertion sort can only move data one bit at a time;

The basic idea of ​​Hill sorting is to first divide the entire sequence of records to be sorted into several sub-sequences for direct insertion sorting, and when the records in the entire sequence are "basically ordered", perform direct insertion sorting on all records in turn.

1. Algorithm steps

1. Choose an incremental sequence t1, t2, ..., tk, where ti > tj, tk = 1;

2. According to the number of incremental sequences k, sort the sequence k times;

3. For each sorting, according to the corresponding increment ti, divide the sequence to be sorted into several subsequences of length m, and perform direct insertion sorting on each subtable. Only when the increment factor is 1, the entire sequence is treated as a table, and the table length is the length of the entire sequence.

2. JavaScript code implementation

function shellSort(arr) {
    var len = arr.length,
        temp,
        gap = 1;
    while(gap < len/3) {          //dynamically define interval sequence/dynamically define 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;
}

3. Python code implementation

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
}

4. Go code implementation

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 = gap / 3
	}
	return arr
}

5. Java code implementation

public class ShellSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // Copy arr without changing the 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;
    }
}

6. PHP code implementation

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;
}

7. C++ 代码实现

void shellSort(vector<int>& arr) {
    int gap = 1;
    while (gap < (int)arr.size() / 3) {
    	gap = gap * 3 + 1;
    }
    for (; gap >= 1; gap /= 3) {
	for (int i = 0; i < gap; ++i) {
	    for (int j = i + gap; j < arr.size(); j += gap) {
		for (int k = j; k - gap >= 0 && arr[k] < arr[k - gap]; k -= gap) {
                    swap(arr[k], arr[k - gap]);
                }
            }
        }
    }
}