說明
插入排序法由未排序的後半部前端取出一個值，插入已排序前半部的適當位置，概念簡單但速度不快。排序加快的原則之一，是讓後一次排序進行時，儘量利用前次排序後的結果，Shell排序法就是基於此概念來改良插入排序法。
解法
Shell排序法最初是D.L Shell於1959提出。假設要排序元素有n個，每次插入排序時並不是針對所有元素，而是取一段間隔。Shell首先將間隔設為n/2，然後跳躍進行插入排序，再來將間隔設為n/4，跳躍進行排序動作，再來間隔設定為n/8、n/16，直到間隔為1的最 後一次排序終止，由於上一次排序動作都會將固定間隔的元素排好，所以間隔越來越小時，某些元素位於正確位置的機率越高，因此最後幾次排序次數將 可以大幅減低。
舉例來說，假設未排序數字如右：89、12、65、97、61、81、27、2、61、98。
數字共有10個，第一次先將間隔設為10 / 2 = 5，此時對間隔為5的數字進行排序，如下所示：
畫線連結部份表示 要一起進行排序的部份，再來將間隔設定為5 / 2的商，也就是2，則第二次插入排序對象如下所示：
再來間隔設定為2 / 2 = 1，此時就是單純插入排序了，由於大部份元素已大致排序過，所以最後一次的插入排序幾乎沒作什麼動作：
後來還有人證明有其它間隔選定法可再加快Shell排序法；Shell排序法概念也可以用來改良氣泡排序法。
實作：C Java Python Scala Ruby JavaScript Haskell
#include <stdio.h>
#define LEN 10
#define SWAP(x,y) {int t; t = x; x = y; y = t;}
void sort(int*, int, int(*)(int, int));
void insertion(int*, int, int, int, int(*)(int, int));
void insert(int*, int, int, int, int(*)(int, int));
int ascending(int, int);
int descending(int, int);
void print(int*, int);
int main(void) {
int number[LEN] = {89, 12, 65, 97, 61, 81, 27, 2, 61, 98};
sort(number, LEN, ascending);
print(number, LEN);
sort(number, LEN, descending);
print(number, LEN);
return 0;
}
void sort(int* number, int len, int(*compar)(int, int)) {
int gap;
for(gap = len / 2; gap > 0; gap /= 2) {
int begin;
for(begin = 0; begin < gap; begin++) {
insertion(number, len, begin, gap, compar);
}
}
}
void insertion(int* number, int len,
int begin, int gap, int(*compar)(int, int)) {
int i;
for(i = begin + gap; i < len; i += gap) {
insert(number, begin, gap, i, compar);
}
}
void insert(int* number, int begin, int gap, int i, int(*compar)(int, int)) {
int j;
for(j = i - gap;
j >= begin && compar(number[j], number[j + gap]) > 0 ; j -= gap) {
SWAP(number[j], number[j + gap]);
}
}
void print(int* arr, int len) {
int i;
for(i = 0; i < len; i++) { printf("%d ", arr[i]); }
printf("\n");
}
int ascending(int a, int b) { return a - b; }
int descending(int a, int b) { return -ascending(a, b); }
import java.util.*;
import static java.lang.System.out;
import static java.util.Collections.swap;
public class Sort {
public static <T extends Comparable<? super T>>
int ascending(T t1, T t2) { return t1.compareTo(t2); }
public static <T extends Comparable<? super T>>
int descending(T t1, T t2) { return -ascending(t1, t2); }
public static <T extends Comparable<? super T>> void shellSort(
List<T> list) {
shellSort(list, Sort::ascending);
}
public static <T> void shellSort(
List<T> list, Comparator<? super T> c) {
for(int gap = list.size() / 2; gap > 0; gap /= 2) {
for(int begin = 0; begin < gap; begin++) {
insertionSort(list, begin, gap, c);
}
}
}
private static <T> void insertionSort(
List<T> list, int begin, int gap, Comparator<? super T> c) {
for(int i = begin + gap; i < list.size(); i += gap) {
insert(list, begin, gap, i, c);
}
}
private static <T> void insert(
List<T> list, int begin, int gap,
int i, Comparator<? super T> c) {
for(int j = i - gap;
j >= begin && c.compare(
list.get(j), list.get(j + gap)) > 0 ; j -= gap) {
swap(list, j, j + gap);
}
}
public static <T extends Comparable<? super T>>
void insertionSort(List<T> list) {
insertionSort(list, Sort::ascending);
}
public static <T> void insertionSort(
List<T> list, Comparator<? super T> c) {
insertionSort(list, 0, 1, c);
}
public static void main(String[] args) {
List<Integer> list =
new ArrayList<>(
Arrays.asList(89, 12, 65, 97, 61, 81, 27, 2, 61, 98));
shellSort(list);
out.println(list);
insertionSort(list, Sort::descending);
out.println(list);
}
}
from functools import reduce
def ascending(a, b): return a - b
def descending(a, b): return -ascending(a, b)
def insertionSort(xs, compare = ascending):
return ([] if not xs
else __insert(xs[0],
insertionSort(xs[1:], compare), compare))
def __insert(x, xs, compare):
return ([x] + xs if not xs or compare(x, xs[0]) <= 0
else [xs[0]] + __insert(x, xs[1:], compare))
def bubbleSort(xs, compare = ascending):
return [] if not xs else __up(xs, compare)
def __up(xs, compare):
if not xs[1:]:
return xs
else:
s = bubbleSort(xs[1:], compare)
return ([s[0]] + __up([xs[0]] + s[1:], compare)
if compare(xs[0], s[0]) > 0
else [xs[0]] + s)
def shellSort(xs, sort = insertionSort, compare = ascending):
return (reduce(lambda xs, gap:
sortWith(gap, xs, sort, compare), gaps(len(list)), xs))
def gaps(len):
gap = len // 2
return [gap] + gaps(gap // 2) if gap > 0 else []
def sortWith(gap, lt, sort, compare):
sortedLts = [sort(lt[begin::gap], compare)
for begin in range(0, gap)]
return [elem for sortedLt in zip(*sortedLts)
for elem in sortedLt]
list = [89, 12, 65, 97, 61, 81, 27, 2, 61, 98]
print(shellSort(list))
print(shellSort(list, compare = descending))
print(shellSort(list, sort = bubbleSort, compare = ascending))object Sort {
def insertion[T](xs: List[T], compare: (T, T) => Boolean): List[T] = {
if(xs.isEmpty) Nil
else insert(xs.head, insertion(xs.tail, compare), compare)
}
private def insert[T](x: T, xs: List[T],
compare: (T, T) => Boolean): List[T] = {
if(xs.isEmpty || x == xs.head || compare(x, xs.head)) x :: xs
else xs.head :: insert(x, xs.tail, compare)
}
def shell[T](xs: List[T], compare: (T, T) => Boolean): List[T] =
(xs /: gaps(list.size))((xs, gap) => sortWith(gap, xs, compare))
private def sortWith[T](gap: Int, lt: List[T],
compare: (T, T) => Boolean): List[T] = {
def subWithGap[T](lt: List[T], begin: Int): List[T] = {
if(begin >= lt.length) Nil
else lt(begin) :: subWithGap(lt, begin + gap)
}
(for(begin <- 0 until gap) yield
insertion(subWithGap(lt, begin), compare)
).toList.transpose.flatten
}
private def gaps(len: Int): List[Int] = {
val gap = len / 2
if(gap > 0) gap :: gaps(gap / 2)
else Nil
}
}
val list = List(89, 12, 65, 97, 61, 81, 27, 2, 61, 98)
println(Sort.shell[Int](list, _ > _))
println(Sort.shell[Int](list, _ < _))class Sort
@@ascending = ->(a, b) { a - b }
@@descending = ->(a, b) { -@@ascending.call(a, b) }
def self.ascending; @@ascending end
def self.descending; @@descending end
def self.insertion(xs, compare)
xs.empty? ? [] : insert(
xs[0], insertion(xs[1..-1], compare), compare)
end
def self.insert(x, xs, compare)
xs.empty? || compare.call(x, xs[0]) <= 0 ?
[x] + xs : [xs[0]] + insert(x, xs[1..-1], compare)
end
private_class_method :insert
def self.shell(xs, compare)
gaps(xs.size).reduce(xs) { |xs, gap|
sortWith(gap, xs, compare)
}
end
def self.gaps(len)
gap = len / 2
gap > 0 ? [gap] + gaps(gap / 2) : []
end
private_class_method :gaps
def self.sortWith(gap, xs, compare)
subWithGap = ->(xs, start) {
start >= xs.size ? [] :
xs[start, 1] + subWithGap.call(xs, start + gap)
}
sorted = (0...gap).map {
|start| insertion(subWithGap.call(xs, start), compare)
}
sorted[0].zip(*sorted[1..-1]).flatten
end
private_class_method :sortWith
end
list = [89, 12, 65, 97, 61, 81, 27, 2, 61, 98]
print(Sort.shell(list, Sort.descending).to_s + "\n")
print(Sort.shell(list, Sort.ascending).to_s + "\n")
function swap(list, i, j) {
var ele = list[i];
list[i] = list[j];
list[j] = ele;
}
function ascending(a, b) {return a - b;}
function descending(a, b) {return -ascending(a, b);}
function insert(list, begin, gap, i, compare) {
for(var j = i - gap; j >= begin && compare(
list[j], list[j + gap]) > 0; j -= gap) {
swap(list, j, j + gap);
}
}
function insertionSort(list, begin, gap, compare) {
for(var i = begin + gap; i < list.length; i += gap) {
insert(list, begin, gap, i, compare);
}
}
function shellSort(list, compare) {
for(var gap = parseInt(list.length / 2);
gap > 0; gap = parseInt(gap / 2)) {
for(var begin = 0; begin < gap; begin++) {
insertionSort(list, begin, gap, compare);
}
}
}
var list = [89, 12, 65, 97, 61, 81, 27, 2, 61, 98];
shellSort(list, descending);
print(list);
import Data.List (transpose)
ascending a b = a - b
descending a b = -ascending a b
insert x xs compare =
if xs == [] || (compare x \$ head xs) <= 0
then x : xs
else head xs : insert x (tail xs) compare
insertionSort xs compare =
if xs == []
then []
else insert (head xs) (insertionSort (tail xs) compare) compare
gaps len =
if gap > 0 then gap : gaps (gap `div` 2)
else []
where gap = len `div` 2
sortWith gap xs compare =
foldl (++) [] (transpose [insertionSort (subWithGap xs begin) compare |
begin <- [0 .. gap - 1]])
where
subWithGap xs begin =
if begin >= length xs then []
else (xs !! begin) : subWithGap xs (begin + gap)
shellSort xs compare =
foldl (\xs gap -> sortWith gap xs compare) xs (gaps \$ length xs)
main = sequence [print \$ shellSort list ascending,
print \$ shellSort list descending]
where list = [89, 12, 65, 97, 61, 81, 27, 2, 61, 98]