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

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; 
} 

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] 

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] 

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 

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)); 
} 

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; 
} 

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; 
} 

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 

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.