Сортировка Шелла

Сортировка Шелла (англ.Shell sort) — алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами — это сортировка вставками с предварительными «грубыми» проходами. Аналогичный метод усовершенствования пузырьковой сортировки называется сортировка расчёской.

 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
public void sort(int[] source) {
  int dist = source.length/2 - 1;
  boolean run = true;
  while (run) {
    run = false ;
    for (int i = 0; i < source.length - dist; i++) {
      if (source [i] > source [i + dist]) {
        int local = source[i];
        source[i] = source[i + dist];
        source[i + dist] = local;
        run = true;
        if (dist > 1) dist--;
      }
    }
  }
}

Популярные теги