JS implementiert die Hill-Sortierung

Dieser Artikel stellt hauptsächlich die Implementierung der Hill-Sortierung in JS vor, die einen gewissen Referenzwert hat. Jetzt können Freunde in Not darauf verweisen.

Hill-Sortierung ist im Wesentlichen eine Einfügungssortierung. Die Sequenz wird jedoch in gleichen Abständen gruppiert und in jeder Gruppe wird eine Einfügungssortierung durchgeführt. Diese Optimierung reduziert die ursprüngliche Zeitkomplexität von O(n^2) auf O(nlogn).

Grundidee

Hill-Sortierung besteht darin, die Arrays in bestimmten Intervallen zu gruppieren und dann in jeder Gruppe eine Einfügungssortierung durchzuführen. Anschließend wird das Intervall schrittweise verringert und in jeder Gruppierung eine Einfügungssortierung durchgeführt ... bis Das Intervall ist gleich 1. Führen Sie eine Einfügungssortierung und ein Ende durch.

Dann stellt sich die Frage, wie groß sollte das Intervall sein und wie kann man es reduzieren? Normalerweise nehmen wir das anfängliche Intervall als die Hälfte der Länge der Sequenz an: Lücke = Länge/2 und reduzieren es in der Form Lücke = Lücke/2. Der gesamte Prozess wird unten im Detail dargestellt.

Das ursprüngliche Array-Array lautet wie folgt:

---

Nehmen Sie zunächst das Intervall als Lücke = Länge/2 = 4 und teilen Sie das Array in 4 Gruppen wie folgt: Implementieren Sie die Einfügungssortierung für jede Gruppe:

---

Bei der ersten Sortierung werden die kleineren Elemente jeder Gruppe an eine relativ vordere Position verschoben (dies Zustand kann als n-sortiert bezeichnet werden, d. h. Gruppierung mit n als Lücke und geordnet). Fahren Sie dann mit der Gruppierung fort, Lücke = Lücke/2 = 2, und implementieren Sie die Einfügungssortierung für jede Gruppe:

---

Fahren Sie mit der Gruppierung des Arrays fort, Lücke = Lücke/2 = 1Das heißt, alle Elemente bilden eine Gruppe und der Einfügungssortierungsalgorithmus ist abgeschlossen:

Code-Implementierung

Verwendung der inneren Schleife Die Einfügungssortierung ist im Grunde die gleiche wie die normale Einfügungssortierung, außer dass die Schrittgröße jeder Bewegung zu einer Lücke statt zu 1 wird:

// shellSort
function shellSort(arr) {
  for(let gap = Math.floor(arr.length/2); gap > 0; gap = Math.floor(gap/2)) {
    // 内层循环与插入排序的写法基本一致，只是每次移动的步长变为 gap
    for(let i = gap; i  0; j -= gap) {
        if(temp >= arr[j-gap]) {
          break;
        }
        arr[j] = arr[j-gap];
      }
      arr[j] = temp;
    }
  }
  return arr;
}

// example
let arr = [2,5,10,7,10,32,90,9,11,1,0,10];
alert(shellSort(arr));

Das Obige ist der gesamte Inhalt dieses Artikels, I Ich hoffe, dass es für alle beim Lernen hilfreich sein wird. Weitere Informationen finden Sie auf der PHP-Chinese-Website für verwandte Inhalte!

Verwandte Empfehlungen:

Jquery fügt Ladeübergangsmaske hinzu

Vue, um eine Steigerung des digitalen Scrollens zu erreichen Wirkung

Das obige ist der detaillierte Inhalt vonJS implementiert die Hill-Sortierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!