Dieses Mal stelle ich Ihnen den einfachsten in JS implementierten Such-, Sortier- und Deduplizierungsalgorithmus vor. Was sind die Vorsichtsmaßnahmen für die Implementierung von Suche, Sortierung und Deduplizierung in JS? Werfen wir einmal einen Blick.
Heute habe ich einen einfachen Sortieralgorithmus zusammengefasst
[Benutzerdefinierte Sortierung]
Suchen Sie zuerst die kleinste Zahl und vergleichen Sie diese Zahl dann mit anderen Zahlen im Array Geben Sie eine Zahl kleiner als diese Zahl ein, vertauschen Sie die Positionen der beiden Zahlen und suchen Sie dann weiter nach der nächstkleineren Zahl für die nächste Vergleichsrunde
var arr = [31, 6, 19, 8, 2, 3]; function findMin(start, arr) { var iMin = arr[start]; var iMinIndex = start; for (var i = start + 1; i < arr.length; i++) { if (arr[i] < iMin) { iMin = arr[i]; iMinIndex = i; } } return iMinIndex; } function sort1(arr) { for (var i = 0; i < arr.length; i++) { var iMinIndex = findMin(i, arr); var car; car = arr[i]; arr[i] = arr[iMinIndex]; arr[iMinIndex] = car; } return arr; } document.write(sort1(arr));
[Lineare Suche]: Suchen Sie eine nach der anderen
//不重复 有序 var arr = [0]; for (var i = 1; i < 100000; i++) { arr[i] = arr[i - 1] + Math.floor(Math.random() * 4 + 1); } function find1(n, arr) { for (var i = 0; i < arr.length; i++) { if (arr[i] == n) { return true; } } return false; } //测试性能 var t1 = new Date().getTime(); for (var i = 0; i < 10000; i++) { var n = Math.random() * 10000; find2(n, 0, arr.length - 1) } alert(new Date().getTime() - t1);
[Binäre Suche]: Teilen Sie es weiterhin in zwei Teile auf
ist eine universelle Methode, nicht unbedingt die beste, aber eine garantierte Methode. (Divide-and-Conquer-Methode)
*** Addieren Sie die Mittelwerte und dividieren Sie durch zwei, gleichmäßig nach links, runden Sie ab
//不重复 有序 var arr = [12, 17, 23, 34, 45, 76, 89]; function find2(n, s, e) { //边界处理 if (s > e) { return false; } else if (s == e) { if (arr[s] == n) { return true; } else { return false; } } var c = Math.floor((s + e) / 2); if (arr[c] == n) { return true; } else { if (n < arr[c]) { return find2(n, s, c); } else { return find2(n, c + 1, e); } } } alert(find2(34, 0, arr.length - 1)); //true false
[Grenzverarbeitung]-----Rekursion , eine Ebene Gehen Sie eine Ebene nach unten, um
//要求数组不重复有顺序\ var arr = [12, 23, 34, 45, 56, 67, 78] function find2(n, s, e) { if (s > e) { return fasle; } else if (s == e) { if (arr[s] == e) { return true; } else { return false; } } var c = Math.floor((s + e) / 2); if (arr[c] == n) { return true; } else { if (n < arr[c]) { return find2(n, s, c); } else { return find2(n, c + 1, e); } } } alert(find2(12, arr.length + 1, 78));
Anwenden
【Mindestwert finden】
var arr = [12, 54, 32, 9, 5, 3, 1, 101, -100, -1000]; function findMin(s, e) { if (s > e) { return []; } else if (s == e) { return arr[s]; } else if (s == e - 1) { if (arr[s] < arr[e]) { return arr[s]; } else { return arr[e]; } } var c = Math.floor((s + e) / 2); var l = findMin(s, c); var r = findMin(c + 1, e); if (l < r) { return l; } else { return r; } } alert(findMin(0, arr.length - 1));
【Array-Deduplizierung】
var arr = [1, 2, 3, 4, 5, 4, 3, 4, 5, 2, 1, 4, 2, 1, 5, 7]; function findInArr(n, arr) { for (var i = 0; i < arr.length; i++) { if (arr[i] == n) { return true; } } return false; } function removeCopy(s, e) { if (s > e) { return []; } else if (s == e) { return [arr[s]]; } else if (s == e - 1) { if (arr[s] == arr[e]) { return [arr[s]]; } else { return [arr[s], arr[e]] } } var c = Math.floor((s + e) / 2); var l = removeCopy(s, c); var r = removeCopy(c + 1, e); for (var i = 0; i < r.length; i++) { if (!findInArr(r[i], l)) { l.push(r[i]); } } return l; } document.write(removeCopy(0, arr.length - 1));
var arr = [34, 32, 1, 76, 55, -100, 99, 101]; function mySort(s, e) { //边界处理 if (s > e) { return []; } else if (s == e) { return [arr[s]] } else if (s == e - 1) { if (arr[s] < arr[e]) { return [arr[s], arr[e]]; } else { return [arr[e], arr[s]]; } } //1.切中间值 var c = Math.floor((s + e) / 2); //2.分半处理 var l = mySort(s, c); var r = mySort(c + 1, e); var res = []; while (l.length > 0 || r.length > 0) { if (l[0] < r[0]) { res.push(l.shift()); } else { res.push(r.shift()); } } if (l.length == 0) { res = res.concat(r); } else if (r.length == 0) { res = res.concat(l); } return res; } //调用 document.write(mySort(0, arr.length - 1));
Bubble sort BubbleSort
Schleifen, wobei jedes Mal zwei Werte herausgenommen und beim nächsten Mal zwei Werte verglichen werden Wert ist kleiner als der aktuelle, dann werden Positionen vertauscht
Die äußere Schleife dient zum Abrufen der Zahlen und die innere Schleife dient zum Austauschen und Vergleichen von Paaren
var arr = [ - 122, -2, 5, 6, 73, 34, 5, 2]; function BubbleSort(arr) { for (var i = 0; i < arr.length; i++) { for (var j = 0; j < arr.length - 1; j++) { if (arr[j] > arr[j + 1]) { var tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp } } } return arr; } document.write(BubbleSort(arr));
[Schnellsortierung] - ------quickSort
erhalten Platzieren Sie für die Zahl in der Mitte des Arrays die Zahl, die kleiner als die mittlere Zahl ist, auf der linken Seite der mittleren Zahl und die größere Zahl als die mittlere Zahl auf der rechten Seite und verknüpfen Sie dann die beiden Zeiten miteinander
function quickSort(arr, s, e) { //边界处理 参与流程 if (arr.length == 0) { return []; } var c = Math.floor((s + e) / 2); var arrC = arr.splice(c, 1); var l = []; var r = []; for (var i = 0; i < arr.length; i++) { if (arr[i] < arrC) { l.push(arr[i]); } else { r.push(arr[i]); } } return quickSort(l).concat(arrC, quickSort(r)); } var arr = [5, 5, 12, 56, 1, 67, -1, -23 - 1]; document.write(quickSort(arr, 0, arr.length - 1));
[Hash] Hash-Hash-Array ------ Häufig verwendete Strukturen in js
Hinzufügen
var arr = []; arr.length = 0; var cont = 0; function hash_add(n) { var pos = n % arr.length; //当空间不足的时候 if (arr[pos]) { while (arr[pos]) { cont++; if (arr[pos] == n) { return; } else { pos++; if (pos == arr.length) { pos = 0; } } } arr[pos] = n; } else { arr[pos] = n; } //空间不足的时候的扩建 if (cont == arr.length) { //d等呗扩建 var oldArr = arr; arr.length = oldArr.length * 2; arr = []; for (var i = 0; i < oldArr.length; i++) { arr.push(oldArr[i]); count = 0; } } } hash_add();
Ich glaube, dass Sie die Methode beherrschen, nachdem Sie den Fall in diesem Artikel gelesen haben. Weitere spannende Informationen finden Sie in anderen verwandten Artikeln auf der chinesischen PHP-Website!
Empfohlene Lektüre:
So verwenden Sie das Vue-basierte Lazy-Loading-Plug-in vue-view-lazy
Das obige ist der detaillierte Inhalt vonJS implementiert den einfachsten Such-, Sortier- und Deduplizierungsalgorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!