1.4 Shell Sort
Category Algorithm
Shell sort, also known as the diminishing increment sort algorithm, is a more efficient improved version of insertion sort. However, shell sort is an unstable sorting algorithm.
The idea of shell sort is based on the following two properties of insertion sort:
Insertion sort is efficient when operating on data that is almost sorted, that is, it can achieve linear sorting efficiency;
However, insertion sort is generally inefficient because it can only move data one position at a time;
The basic idea of shell sort is: first, divide the entire sequence of records to be sorted into several subsequences for direct insertion sort, and when the records in the entire sequence are "basically ordered," then perform direct insertion sort for all records.
1. Algorithm Steps
Select an increment sequence t1, t2, ..., tk, where ti > tj, tk = 1;
Sort the sequence in k passes according to the number of increments;
In each pass, according to the corresponding increment ti, divide the sequence to be sorted into several subsequences of length m, and perform direct insertion sort for each subsequence. 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. Animated Demonstration
Code Implementation
JavaScript
Example
function shellSort(arr) {
var len = arr.length,
temp,
gap = 1;
while(gap < len/3) { // Dynamically define the gap 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;
}
Python
Example
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
return arr
Go
Example
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
}
Java
Example
public static void shellSort(int[] arr) {
int length = arr.length;
int temp;
for (int step = length / 2; step >= 1; step /= 2) {
for (int i = step; i < length; i++) {
temp = arr[i];
int j = i - step;
while (j >= 0 && arr[j] > temp) {
arr[j + step] = arr[j];
j -= step;
}
arr[j + step] = temp;
}
}
}
PHP
Example
``` 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