Tri JavaScript Hill, tri rapide, tri par fusion algorithm

Tri JavaScript Hill, tri rapide, tri par fusion algorithm_javascript skills

WBOY

Libérer： 2016-05-16 15:01:40

original

1561 Les gens l'ont consulté

Prenons var a = [4,2,6,3,1,9,5,7,8,0] ;

1. Tri en colline. Le tri Hill est une mise à niveau du tri par insertion. Voici quelques façons de comparer en premier avec ceux qui sont plus éloignés.

function shellsort(arr){ 
  var i,k,j,len=arr.length,gap = Math.ceil(len/2),temp; 
  while(gap>0){ 
    for (var k = 0; k < gap; k++) { 
      var tagArr = []; 
      tagArr.push(arr[k]) 
      for (i = k+gap; i < len; i=i+gap) {        
        temp = arr[i]; 
        tagArr.push(temp); 
        for (j=i-gap; j >-1; j=j-gap) { 
          if(arr[j]>temp){ 
            arr[j+gap] = arr[j]; 
          }else{ 
            break; 
          } 
        } 
        arr[j+gap] = temp; 
      } 
      console.log(tagArr,"gap:"+gap);//输出当前进行插入排序的数组。 
      console.log(arr);//输出此轮排序后的数组。 
    } 
    gap = parseInt(gap/2); 
  } 
  return arr; 
}

Copier après la connexion

Sortie du processus :

[4, 9] "gap:5" 
[4, 2, 6, 3, 1, 9, 5, 7, 8, 0] 
[2, 5] "gap:5" 
[4, 2, 6, 3, 1, 9, 5, 7, 8, 0] 
[6, 7] "gap:5" 
[4, 2, 6, 3, 1, 9, 5, 7, 8, 0] 
[3, 8] "gap:5" 
[4, 2, 6, 3, 1, 9, 5, 7, 8, 0] 
[1, 0] "gap:5" 
[4, 2, 6, 3, 0, 9, 5, 7, 8, 1] 
[4, 6, 0, 5, 8] "gap:2" 
[0, 2, 4, 3, 5, 9, 6, 7, 8, 1] 
[2, 3, 9, 7, 1] "gap:2" 
[0, 1, 4, 2, 5, 3, 6, 7, 8, 9] 
[0, 1, 4, 2, 5, 3, 6, 7, 8, 9] "gap:1" 
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Copier après la connexion

Vous pouvez le voir sur la sortie. L'intervalle du premier tour est de 5. Triez les tableaux de ces intervalles dans l’ordre.
L'intervalle est de 5 :

[4, 9] "gap:5" 
[4, 2, 6, 3, 1, 9, 5, 7, 8, 0] 
[2, 5] "gap:5" 
[4, 2, 6, 3, 1, 9, 5, 7, 8, 0] 
[6, 7] "gap:5" 
[4, 2, 6, 3, 1, 9, 5, 7, 8, 0] 
[3, 8] "gap:5" 
[4, 2, 6, 3, 1, 9, 5, 7, 8, 0] 
[1, 0] "gap:5" 
[4, 2, 6, 3, 0, 9, 5, 7, 8, 1] 
[4, 6, 0, 5, 8] "gap:2" 
[0, 2, 4, 3, 5, 9, 6, 7, 8, 1] 
[2, 3, 9, 7, 1] "gap:2" 
[0, 1, 4, 2, 5, 3, 6, 7, 8, 9] 
[0, 1, 4, 2, 5, 3, 6, 7, 8, 9] "gap:1" 
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Copier après la connexion

l'intervalle est de 2 :

[4, 2, 6, 3, 0, 9, 5, 7, 8, 1] 
 4   6   0   5   8 
  2   3   9   7   1

Copier après la connexion

Après tri :
[0, 1, 4, 2, 5, 3, 6, 7, 8, 9]

l'intervalle est 1 :
Après tri :
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9].

2. Tri rapide. Marquez un tableau avec une certaine valeur dans le tableau. Les valeurs inférieures à cela sont placées sur le côté gauche du tableau et les valeurs supérieures à cela sont placées sur le côté droit du tableau. Effectuez ensuite de manière récursive la même opération sur les tableaux gauche et droit. jusqu'à ce que le tri soit terminé. Habituellement, la première valeur du tableau est marquée.
Code :

function quickSort(arr){ 
  var len = arr.length,leftArr=[],rightArr=[],tag; 
  if(len<2){ 
    return arr; 
  } 
  tag = arr[0]; 
  for(i=1;i<len;i++){ 
    if(arr[i]<=tag){ 
      leftArr.push(arr[i]) 
    }else{ 
      rightArr.push(arr[i]); 
    } 
  } 
  return quickSort(leftArr).concat(tag,quickSort(rightArr)); 
}

Copier après la connexion

3. Trier par fusion. Fusionnez une série de sous-séquences triées en une grande séquence ordonnée complète. Commencez la fusion à partir de la plus petite unité. Fusionnez ensuite progressivement les tableaux ordonnés fusionnés. Enfin, réalisez le tri par fusion.
Méthode pour fusionner deux tableaux triés :

function subSort(arr1,arr2){ 
 
  var len1 = arr1.length,len2 = arr2.length,i=0,j=0,arr3=[],bArr1 = arr1.slice(),bArr2 = arr2.slice(); 
 
  while(bArr1.length!=0 || bArr2.length!=0){ 
    if(bArr1.length == 0){ 
      arr3 = arr3.concat(bArr2); 
      bArr2.length = 0; 
    }else if(bArr2.length == 0){ 
      arr3 = arr3.concat(bArr1); 
      bArr1.length = 0; 
    }else{ 
      if(bArr1[0]<=bArr2[0]){ 
        arr3.push(bArr1[0]); 
        bArr1.shift(); 
      }else{ 
        arr3.push(bArr2[0]); 
        bArr2.shift(); 
      } 
    } 
  } 
  return arr3; 
}

Copier après la connexion

Tri par fusion :

function mergeSort(arr){ 
  var len= arr.length,arrleft=[],arrright =[],gap=1,maxgap=len-1,gapArr=[],glen,n; 
  while(gap<maxgap){ 
    gap = Math.pow(2,n); 
    if(gap<=maxgap){ 
      gapArr.push(gap); 
    } 
    n++; 
  } 
  glen = gapArr.length; 
  for (var i = 0; i < glen; i++) { 
    gap = gapArr[i]; 
    for (var j = 0; j < len; j=j+gap*2) { 
      arrleft = arr.slice(j, j+gap); 
      arrright = arr.slice(j+gap,j+gap*2); 
      console.log("left:"+arrleft,"right:"+arrright); 
      arr = arr.slice(0,j).concat(subSort(arrleft,arrright),arr.slice(j+gap*2)); 
    } 
  } 
  return arr; 
}

Copier après la connexion

Trier [4,2,6,3,1,9,5,7,8,0] Sortie :

left:4 right:2 
left:6 right:3 
left:1 right:9 
left:5 right:7 
left:8 right:0 
left:2,4 right:3,6 
left:1,9 right:5,7 
left:0,8 right: 
left:2,3,4,6 right:1,5,7,9 
left:0,8 right: 
left:1,2,3,4,5,6,7,9 right:0,8

Copier après la connexion

On voit cela à partir de la plus petite unité.
Au premier tour, les éléments adjacents sont fusionnés dans l'ordre : 4,2 ; Une fois la fusion terminée, cela devient : [2,4,3,6,1,9,5,7,0,8]

Le deuxième tour combine 2 éléments comme une unité : [2,4],[3,6] ; [1,9],[5,7] ; 🎜> Une fois la fusion terminée, cela devient : [2,3,4,6,1,5,7,9,0,8]
Le troisième tour combine 4 éléments comme une unité : [
2,3,4,6],[1,5,7,9] [0,8],[] ; Une fois la fusion terminée, cela devient : [1,2,3,4,5,6,7,9,0,8];
Le quatrième tour combine 8 éléments comme une unité :
[1,2,3,4,5,6,7,9],[0,8]; La fusion est terminée. [0,1,2,3,4,5,6,7,8,9];
Ce qui précède représente l’intégralité du contenu de cet article, j’espère qu’il sera utile à l’étude de chacun.