var a = [4,2,6,3,1,9,5,7,8,0];例として。
1。ヒルソート。 Hill Sortingは、挿入並べ替えに加えられたアップグレードです。最初に距離を持つ人と比較する方法です。
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; }プロセス出力:
[4、2、6、3、9、9、5、7、8、0] [1、0] "GAP:5" [4、2、6、3、3、1、9、5、5、7、8、0] [6、7] "GAP:5" [4、2、6、3、1、9、5、7、8、0] [3、8] 0] "GAP:5" [4、2、6、3、9、5、7、8、0] [1、0] "GAP:5" [4、2、2、6、3、1、9、5、7、8、0] [1、0] "GAP:5" [4、2、6、3、3、3、0、9、5、7、8、8] 8、0] [1、0] "ギャップ:5" [4、2、6、3、0、9、5、7、8、8、8、8、8] [6、7] [6、7] [4、2、6、3、1、9、5、7、8、0] [1、0] 9、5、7、8、0] [1、0] "GAP:5" [4、2、3、5、9、6、7、8、1] [2、3、9、9、7、1] "GAP:2" [0、1、4、4、2、5、3、6、7、8、9]
出力から見ることができます。最初のラウンド間の間隔は5です。これらの間隔の配列を順番に並べ替えます。
間隔は5です。
[4、2、6、3、9、9、5、7、8、0] [1、0] "GAP:5" [4、2、6、3、3、1、9、5、5、7、8、0] [6、7] "GAP:5" [4、2、6、3、1、9、5、7、8、0] [3、8] 0] "GAP:5" [4、2、6、3、9、5、7、8、0] [1、0] "GAP:5" [4、2、2、6、3、1、9、5、7、8、0] [1、0] "GAP:5" [4、2、6、3、3、3、0、9、5、7、8、8] 8、0] [1、0] "ギャップ:5" [4、2、6、3、0、9、5、7、8、8、8、8、8] [6、7] [6、7] [4、2、6、3、1、9、5、7、8、0] [1、0] 9、5、7、8、0] [1、0] "GAP:5" [4、2、3、5、9、6、7、8、1] [2、3、9、9、7、1] "GAP:2" [0、1、4、4、2、5、3、6、7、8、9]
間隔は2です。
[4、2、6、3、0、9、5、7、8、1] 4 6 0 5 8 2 3 9 7 1
ソート後:
[0、1、4、2、5、3、6、7、8、9]
間隔は1です。
ソート後:
[0、1、2、3、4、5、6、7、8、9]。
2。クイックソート。配列に値が付いたアレイを作成します。値をこれより小さく配列の左側に置き、これよりも大きい配列を配列の右側に配置します。次に、左右の配列で同じ操作を再帰的に実行します。ソートが完了するまで。通常、配列の最初の値がマークされます。
コード:
関数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]); }} quicksort(leftarr).concat(tag、quicksort(rightArr))を返します。 }3。注文と並べ替え。一連のソートされたサブシーケンスを、大きく完全な順序付けられたシーケンスにマージします。最小のユニットから始まるマージ。次に、マージされた順序付けられた配列を徐々にマージします。最後に、マージソートが達成されます。
2つの順序付けられた配列をマージする方法:
関数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(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(); }} arr3を返します。 }ソートをマージ:
関数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 "、右:"+arrright); arr = arr.slice(0、j).concat(subsort(arrleft、arrright)、arr.slice(j+gap*2)); }} return arr; }ソート[4,2,6,3,1,9,5,7,8,0]出力:
左:2右:2左:6右:3左:1右:9左:5右:7右:7右:8右:8左:2,4左:1,9右:1,9右:5,7左:0,8右:左:2,3,4,6右:1,5,7,9
最小のユニットから始まることがわかります。
最初のラウンドは、隣接する要素をシーケンスでマージします: 4,2; 6,3; 1,9; 5,7; 8,0
マージが完了すると、[2,4,3,6,1,9,5,7,0,8]になります。
2回目のラウンドは、2つの要素の1つの単位でマージします。[ 2,4]、[3,6]; [1,9]、[5,7]; [0,8]、[];
マージが完了すると、[2,3,4,6,1,5,7,9,0,8]になります。
3回目のラウンドは、4つの要素の1つの単位でマージします。[ 2,3,4,6]、[1,5,7,9]; [0,8]、[]
マージが完了すると、次のようになります。
第4ラウンドは、8つの要素の1つの単位でマージします。 [1,2,3,4,5,6,7,9]、[0,8];
マージが完了しました。 [0,1,2,3,4,5,6,7,8,9];
上記はこの記事に関するものです。すべての人の学習に役立つことを願っています。