JavaScript Hill sort, quick sort, merge sort algorithm_javascript kemahiran-tutorial js-php.cn

JavaScript Hill sort, quick sort, merge sort algorithm_javascript kemahiran

WBOY

Lepaskan： 2016-05-16 15:01:40

asal

1610 orang telah melayarinya

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

Salin selepas log masuk

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]

Salin selepas log masuk

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]

Salin selepas log masuk

selang ialah 2:

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

Salin selepas log masuk

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

Salin selepas log masuk

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

Salin selepas log masuk

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

Salin selepas log masuk

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

Salin selepas log masuk

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.