Javascript-Implementierung und Erläuterung des Sortieralgorithmus (99js-Hinweise)_Javascript-Kenntnisse

Blasensortierung

Das Prinzip des Sprudelns besteht darin, das größte Element oder das kleinste Element „schweben zu lassen“

Einfügesortierung, Auswahlsortierung, Schnellsortierung und Blasensortierung sind alles Vergleichssortierungen

Gedanken

Vergleichen Sie zwei benachbarte Zahlen nacheinander, indem Sie die Dezimalzahl voranstellen und die große Zahl hinten.

Schritt 1: Vergleichen Sie die erste und die zweite Zahl, setzen Sie die Dezimalzahlen voran und die großen Zahlen hinten. Um die zweite und die dritte Zahl zu vergleichen, setzen Sie die Dezimalzahl voran und die große Zahl hinten und machen Sie so weiter, bis Sie die letzten beiden Zahlen vergleichen, setzen Sie die Dezimalstelle voran und die große Zahl hinten.
Schritt 2: Im zweiten Durchgang: Beginnen Sie den Vergleich immer noch mit dem ersten Zahlenpaar (da es durch den Austausch der zweiten Zahl und der dritten Zahl bedingt sein kann, dass die erste Zahl nicht mehr kleiner als die zweite Zahl ist), setzen Sie die Dezimal zuerst. Nachdem die große Zahl platziert wurde, wird der Vergleich bis zur vorletzten Zahl fortgesetzt (die vorletzte Stelle ist bereits die größte). Am Ende des zweiten Durchgangs wird eine neue maximale Zahl erhalten an der vorletzten Position (tatsächlich ist in der gesamten Reihenfolge die zweitgrößte Zahl).
Fahren Sie so fort und wiederholen Sie den obigen Vorgang, bis die Sortierung endgültig abgeschlossen ist.
Da beim Sortiervorgang kleine Zahlen immer nach vorne und große Zahlen nach hinten gestellt werden, was dem Aufsteigen von Blasen gleichkommt, spricht man von Blasensortierung.
Animationseffekt der Blasensortierung

Implementierung: Dieser Code ist relativ einfach und der grundlegendste und grundlegendste Code im Algorithmus. . .
Drei Punkte, die Sie beachten sollten

1. Die Methode zum Austauschen von Klassen kann durch die Verwendung von a=[b,b=a][0] in JavaScript gelöst werden, was eine sehr clevere Methode ist,
Ersetzen Sie

Code kopieren Der Code lautet wie folgt:

var,a,b,temp
temp = a;
a=b;
b = Temperatur

Diese Austauschmethode
2. Achten Sie darauf, dass hier der Cache der Schleifenvariablen Array.length
zwischengespeichert wird. 3. Achten Sie auf die eingebettete Schleife, die von der ersten Zahl bis zur n-ten Zahl ab der letzten vergleicht, und n ist die Anzahl der Vergleichsschritte

function bubbleSort(array) {
var l=array.length;
for (var i = 0; i < l; i++) {//比较的step数为数组的长度
for (var j = 0; j < l-i; j++) {//内嵌交换的次数是从第一个数比较到倒数第总长-n个数，n则为比较的step数
if (array[j] < array[j - 1]) {
array[j] = [array[j - 1], array[j - 1] = array[j]][0]//在这里交换元素
}
}
for (var k = 0; k < l; k++) {
console.log(array[k] + ",");
}
console.log('这是第'+(i+1)+'次排序')
}
}
var a = [6,54,6,22,5,7,8,2,34];
bubbleSort(a);

Animationseffekte

Einfügesortierung
Es ist ganz einfach, wir müssen nur die Schritte zum Zeichnen und Einsetzen der Karten befolgen!
Idee:

1 Nehmen wir zunächst an, wir ziehen eine Karte und alle derzeit in unserer Hand befindlichen Karten sind auf empty = [] gesetzt und ziehen einen push(arr[0])
2 Nehmen Sie die nächste Karte heraus, legen Sie sie auf a und scannen Sie alle unsere leeren (bereits sortierten) Karten von hinten nach vorne
3. Wenn die leere[empty.length-n] (sortierte) Karte in Ihrer Hand größer als das neue Element ist, verschieben Sie die Karte an die nächste Position (machen Sie Platz). empty[empty.length-n]= empty[empty. Länge- n 1]
4 Wiederholen Sie Schritt 3, bis Sie feststellen, dass die sortierte Karte empty[empty.length-n] kleiner oder gleich a
ist 5 Fügen Sie a an der Position empty[empty.length-n]=a
ein 6Wiederholen Sie Schritt 2
Allerdings ist es immer noch etwas schwierig, den Javascript-Code zu implementieren. Der Code lautet wie folgt:

function insert(arr) {
var l = arr.length;
var empty = [];//空数组，表示我们的手
empty.push(arr[0]);//我们先摸起来一张
for (var i = 1; i < l; i++) {//注意这里起点是1，因为我们已经摸了一张了！
if (arr[i] > empty[empty.length - 1]) {
empty[empty.length] = arr[i]
} //如果比有序数组empty还大，直接放到末尾
for (var j = empty.length; j > 0 && arr[i] < empty[j - 1]; j--) { //从最大值跟arr进行比较，为了给arr腾空。当arr<有序数组的某一位时，就不用移动了。
empty[j] = empty[j - 1]; //向右移动
empty[j - 1] = arr[i]; //把值放到空出来的位置上
}
//console.log(empty)
}
return empty
}

Der wichtigere Wissenspunkt hier ist das &&-Symbol, das „und“ bedeutet, das heißt, die Bedingungen auf beiden Seiten müssen erfüllt sein, damit der Ausdruck wahr ist.
Das &&-Symbol kann auch if ersetzen, zum Beispiel wenn(a){fun()} gleich a&&b
ist Ein weiterer sehr wichtiger Punkt
Angenommen, das Array ist arr, dann ist sein „letztes Element“ arr[arr.length-1].

Animation sortieren

Auswahlsortierung
Es ist auch ein einfacher Sortieralgorithmus.

Dinge:

Finden Sie das kleinste Element – ​​werfen Sie es in das Array – suchen Sie dann das nächstkleinere Element – ​​werfen Sie es in das Array und so weiter.
Suchen Sie zunächst das kleinste Element im unsortierten Array. Die Methode zum Finden kann durch kontinuierliche Beurteilung und Zuweisung erfolgen, d. h. unter der Annahme, dass das erste Element des Arrays, Array [0], das kleinste Element ist, dann die Seriennummer „Kleinstes Element“ im Array ist 0
Durchlaufen Sie dann das Array. Wenn das zweite Element des Arrays kleiner ist, bedeutet dies, dass das zweite Element das kleinste Element ist, und aktualisieren Sie „0“ auf „1“.
Nachdem die Durchquerung abgeschlossen ist, wissen wir, dass der minimale Elementindex dieser Reihe „n“ ist. Nehmen Sie ihn direkt heraus und speichern Sie ihn an der Startposition der sortierten Sequenz (Array[n])
Suchen Sie dann weiterhin das kleinste Element aus den verbleibenden unsortierten Elementen und fügen Sie es am Ende der sortierten Sequenz ein. Beachten Sie, dass der zu diesem Zeitpunkt durchlaufene Index bei 1 beginnt. Denn ein minimales Element haben wir bereits herausgesucht.
Und so weiter, bis alle Elemente sortiert sind.

function selectSort(array) {
var min;
var l = array.length;//缓存长度
for (var i = 0; i < l; i++) {//开始进行循环，一共循环l次，就可以找出l个元素了
min = i;//假设第一个为最小元素
for (var j = i + 1; j < l; j++) {//从第一个开始循环，遍历
if (array[min] > array[j])//判断之后的是否比前面的小
min = j;//更新“最小”的下标
}
if (min != i) {//这里因为是在同一个数组内进行操作，所以直接交换元素即可。比如数组第一项是i，那么我找出了最小元素为array[min],那么我就需要把这个min跟i交换。以此类推。
array[i]= [array[min],array[min]=array[i]][0];//交换元素
}
}
return array;
}

这里仍然注意的是交换的写法 array[i]= [array[min],array[min]=array[i]][0]
可以方便的把array[i]与array[min]交换~

排序动画

快速排序
 
快速排序是目前最强大的排序算法，算法利用了递归的思想。
 
思路

从数组中挑出一个元素，称为 “基准”，这个可以直接利用length/2挑出来
遍历数组，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。通俗来讲：男的站左边，女的站右边。。
之后我们得到了一个这样的数组 array= 比基准小的部分组成的数组lArray+基准+比基准大的部分组成的数组rArray。
那么我们之后只需要再把lArray,rArray进行“同样的”处理即可~
这就需要用到 递归 的写法了。处理之后，lArray又分成了 lArray的基准，比lArray基准还小的，比lArray基准还大的。。
那么我们不断的进行操作，男的站左边，女的站右边。。
直到我们发现，lArray的长度变成1了，不足以再分下去了，我们认为排序结束。

function quickSort(arr) {
var l = arr.length;//缓存数组长度
if(arr.length <= 1){return arr}; //如果我们拿到的lArray,rArray长度比1都小，那就不用排了~
var num = Math.floor(arr.length / 2);//取数组中间的那个数。注意length/2不一定是整数，用Math.floor取整
var numValue = arr.splice(num, 1)[0];//利用splice方法，取一个元素出来，注意语法
var left = [];//创建左边基准容器
var right = [];//创建右边基准容器
for (var i = 0; i < l; i += 1) {//开始遍历数组
arr[i] < numValue &#63; left.push(arr[i]) : right.push(arr[i]);//男的站左边，女的站右边。。
}
return quickSort(left).concat([numValue], quickSort(right))//递归，继续对左右数组进行操作。
}

动画效果：

这里注意 arr.splice(num,1)虽然只抽了一个数，但splice的结果也是数组，需要[0],要不然结果就会很奇葩的出现一堆array(1)的数组了。。。
splice的参考：http://www.jb51.net/w3school/js/jsref_splice.htm
Math.floor即Math对象的参考http://www.jb51.net/w3school/js/js_obj_math.htm
递归是什么：http://baike.baidu.com/view/96473.htm

以上四个算法除了快速排序，都是简单排序算法，而这四个算法在面试中考的都非常频繁~
在这里仍然要强调一点，以上的算法大量使用了循环及数组的相关知识，一定要背熟！