JavaScript Hill sort, quick sort, merge sort algorithm_javascript kemahiran

Ambil var a = [4,2,6,3,1,9,5,7,8,0] sebagai contoh.

1. Isih bukit ialah peningkatan pada isihan sisipan. Berikut adalah beberapa cara untuk membandingkan dengan yang lebih jauh dahulu.

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

Proses output:

[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] 

Anda boleh melihatnya daripada output. Selang pusingan pertama ialah 5. Isih tatasusunan selang ini dalam urutan.
Selang masa ialah 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] 

selang ialah 2:

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

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

selang ialah 1:
Selepas mengisih:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9].

2. Teg tatasusunan dengan nilai tertentu dalam tatasusunan. Nilai yang lebih kecil daripada ini diletakkan di sebelah kiri tatasusunan, dan nilai yang lebih besar daripada ini diletakkan di sebelah kanan tatasusunan. Kemudian secara rekursif lakukan operasi yang sama pada tatasusunan kiri dan kanan. sehingga pengisihan selesai. Biasanya nilai pertama dalam tatasusunan ditandakan.
Kod:

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. Gabungkan satu siri urutan yang diisih ke dalam urutan tertib lengkap yang besar. Mula bergabung daripada unit terkecil. Kemudian gabungkan tatasusunan tertib yang digabungkan secara beransur-ansur. Akhirnya mencapai jenis gabungan.
Kaedah untuk menggabungkan dua tatasusunan yang diisih:

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

Isih gabung:

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

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

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 

Dapat dilihat bermula dari unit terkecil.
Dalam pusingan pertama, elemen bersebelahan digabungkan dalam urutan: 6,3; Selepas penggabungan selesai, ia menjadi: [2,4,3,6,1,9,5,7,0,8]

Pusingan kedua menggabungkan 2 elemen sebagai satu unit: [2,4],[3,6]; [1,9],[5,7] [0,8],[ ]; Selepas penggabungan selesai, ia menjadi: [2,3,4,6,1,5,7,9,0,8]

Pusingan ketiga menggabungkan 4 elemen sebagai satu unit: [2,3,4,6],[1,5,7,9] [0,8],[] Selepas penggabungan selesai, ia menjadi: [1,2,3,4,5,6,7,9,0,8];

Pusingan keempat menggabungkan 8 elemen sebagai satu unit: [1,2,3,4,5,6,7,9],[0,8]; Penggabungan selesai. [0,1,2,3,4,5,6,7,8,9];

Di atas adalah keseluruhan kandungan artikel ini, saya harap ia akan membantu kajian semua orang.