Heim  >  Artikel  >  Web-Frontend  >  Detaillierte Erklärung der Heap-Sortierung in JavaScript

Detaillierte Erklärung der Heap-Sortierung in JavaScript

韦小宝
韦小宝Original
2018-03-14 14:22:192093Durchsuche

In diesem Artikel geht es um die Heap-Sortierung in JavaScript. Wenn Sie sich mit der Heap-Sortierung in JavaScript nicht auskennen, werfen wir einen Blick auf diesen Artikel Punkt

Heap-Sortierung kann als Auswahlsortierung bezeichnet werden, die das Konzept eines Heaps zum Sortieren verwendet. In zwei Methoden unterteilt:

1, Big Top Heap: Der Wert jedes Knotens ist größer oder gleich dem Wert seines untergeordneten Knotens und wird im Heap-Sortieralgorithmus in aufsteigender Reihenfolge verwendet

2. Kleiner oberer Heap: Der Wert jedes Knotens ist kleiner oder gleich dem Wert seines untergeordneten Knotens und wird im Heap-Sortieralgorithmus in absteigender Reihenfolge verwendet

Demonstration der Heap-Sort-Animation

Detaillierte Erklärung der Heap-Sortierung in JavaScript

JavaScript-Code-Implementierung:

var len;    //因为声明的多个函数都需要数据长度,所以把len设置成为全局变量function buildMaxHeap(arr) {   //建立大顶堆  
    len = arr.length;  
    for (var i = Math.floor(len/2); i >= 0; i--) {  
        heapify(arr, i);  
    }}function heapify(arr, i) {     //堆调整  
    var left = 2 * i + 1,  
        right = 2 * i + 2,  
        largest = i;  
  
    if (left < len && arr[left] > arr[largest]) {  
        largest = left;  
    }  
  
    if (right < len && arr[right] > arr[largest]) {  
        largest = right;  
    }  
  
    if (largest != i) {  
        swap(arr, i, largest);  
        heapify(arr, largest);  
    }}function swap(arr, i, j) {  
    var temp = arr[i];  
    arr[i] = arr[j];  
    arr[j] = temp;}function heapSort(arr) {  
    buildMaxHeap(arr);  
  
    for (var i = arr.length-1; i > 0; i--) {  
        swap(arr, 0, i);  
        len--;  
        heapify(arr, 0);  
    }  
    return arr;}

Das Obige ist der gesamte Inhalt dieses Artikels Darüber hinaus können Sie es selbst umsetzen. Es ist einfach, beide Seiten zu beherrschen!

Verwandte Empfehlungen:

JavascriptHeap-SortierungDetaillierte Erklärung des Algorithmus

Das obige ist der detaillierte Inhalt vonDetaillierte Erklärung der Heap-Sortierung in JavaScript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn