Nehmen Sie var a = [4,2,6,3,1,9,5,7,8,0];
1. Hügelsortierung. Die Hill-Sortierung ist eine Weiterentwicklung der Einfügungssortierung. Hier sind einige Möglichkeiten, zunächst mit weiter entfernten Orten zu vergleichen.
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;
}
Prozessausgabe:
[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]
Sie können es der Ausgabe entnehmen. Das Intervall der ersten Runde beträgt 5. Sortieren Sie die Arrays dieser Intervalle der Reihe nach.
Das Intervall ist 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]
Intervall ist 2:
[4, 2, 6, 3, 0, 9, 5, 7, 8, 1] 4 6 0 5 8 2 3 9 7 1
Nach dem Sortieren:
[0, 1, 4, 2, 5, 3, 6, 7, 8, 9]
Intervall ist 1:
Nach dem Sortieren:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9].
2. Schnelle Sortierung. Kennzeichnen Sie ein Array mit einem bestimmten Wert im Array. Kleinere Werte werden auf der linken Seite des Arrays platziert, und größere Werte werden auf der rechten Seite des Arrays platziert. Führen Sie dann rekursiv dieselbe Operation für das linke und rechte Array aus. bis die Sortierung abgeschlossen ist. Normalerweise wird der erste Wert im Array markiert.
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. Sortierung zusammenführen. Fügen Sie eine Reihe sortierter Teilsequenzen zu einer großen, vollständig geordneten Sequenz zusammen. Beginnen Sie mit der Zusammenführung von den kleinsten Einheiten. Führen Sie dann nach und nach die zusammengeführten geordneten Arrays zusammen. Schließlich wird die Zusammenführungssortierung erreicht.
Methode zum Zusammenführen zweier sortierter Arrays:
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;
} Sortierung zusammenführen:
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;
}
Sortieren [4,2,6,3,1,9,5,7,8,0] Ausgabe:
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
Man erkennt, dass man schon bei der kleinsten Einheit ansetzen kann.
In der ersten Runde werden benachbarte Elemente der Reihe nach zusammengeführt: 1,9; 5,7;
Nach Abschluss der Fusion wird daraus: [2,4,3,6,1,9,5,7,0,8]
Die zweite Runde kombiniert 2 Elemente als Einheit: [2,4],[3,6]; [1,9],[5,7];
Nach Abschluss der Fusion wird daraus: [2,3,4,6,1,5,7,9,0,8]
Die dritte Runde kombiniert 4 Elemente als Einheit: [2,3,4,6],[1,5,7,9],[]
Nach Abschluss der Fusion wird daraus: [1,2,3,4,5,6,7,9,0,8];
Die vierte Runde kombiniert 8 Elemente als Einheit: [1,2,3,4,5,6,7,9],[0,8];
Die Zusammenführung ist abgeschlossen. [0,1,2,3,4,5,6,7,8,9];
