Implémentation Javascript et explication de l'algorithme de tri (notes 99js)_compétences Javascript

Tri à bulles

Le principe du bullage est de "faire flotter" le plus gros élément ou le plus petit élément

Le tri par insertion, le tri par sélection, le tri rapide, le tri à bulles sont tous des tris par comparaison

Pensées

Comparez deux nombres adjacents dans l'ordre, en mettant la décimale devant et le grand nombre derrière.

étape 1 : Comparez le premier et le deuxième nombres, mettez les décimales devant et les grands nombres derrière. Pour comparer le deuxième nombre et le troisième nombre, mettez la décimale devant et le grand nombre derrière, et continuez ainsi jusqu'à comparer les deux derniers nombres, mettez la décimale devant et le grand nombre derrière.
étape 2 : Dans la deuxième passe : commencez toujours la comparaison à partir de la première paire de nombres (car cela peut être dû à l'échange du deuxième nombre et du troisième nombre que le premier nombre n'est plus petit que le deuxième nombre), mettez le décimal en premier, Une fois le grand nombre placé, la comparaison se poursuit jusqu'à l'avant-dernier nombre (l'avant-dernière position est déjà la plus grande à la fin du deuxième passage, un nouveau nombre maximum est obtenu). à l'avant-dernière position (en fait, dans toute la séquence se trouve le deuxième plus grand nombre).
Continuez ainsi et répétez le processus ci-dessus jusqu'à ce que le tri soit enfin terminé.
Étant donné que dans le processus de tri, les petits nombres sont toujours placés en avant et les grands nombres en arrière, ce qui équivaut à des bulles qui montent, c'est ce qu'on appelle le tri à bulles.
Effet d'animation de tri à bulles

Implémentation : ce code est relativement simple et est le code le plus basique et le plus basique de l'algorithme. . .
Trois points à noter

1. La méthode d'échange de classes peut être résolue en utilisant a=[b,b=a][0] en JavaScript, qui est une méthode très intelligente,
Remplacer

Copier le code Le code est le suivant :

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

Cette méthode d'échange
2. Faites attention au cache des variables de boucle. Array.length
est mis en cache ici. 3. Faites attention à la boucle intégrée, qui compare du premier nombre au nième nombre à partir du dernier, et n est le nombre d'étapes de comparaison

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

Effets d'animation

Tri par insertion
C'est très simple, il suffit de suivre les étapes pour dessiner et insérer les cartes !
Idée :

1 Tout d'abord, supposons que nous piochions une carte et que toutes les cartes actuellement dans notre main soient définies comme vides = [] et que nous piochions un push(arr[0])
2 Sortez la carte suivante, mettez-la en a, et scannez toutes nos cartes vides (déjà triées) de l'arrière vers l'avant
3. Si la carte vide[empty.length-n] (triée) dans votre main est supérieure au nouvel élément, déplacez la carte à la position suivante (faites de l'espace) vide[empty.length-n]= vide[vide. longueur- n 1]
4 Répétez l'étape 3 jusqu'à ce que vous trouviez que la carte triée est vide[empty.length-n] est inférieure ou égale à a
5 Insérez a dans la position vide[empty.length-n]=a
6Répétez l'étape 2
Cependant, il est encore un peu difficile d'implémenter le code javascript. Le code est le suivant :

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
}

Le point de connaissance le plus important ici est le symbole &&, qui signifie « et », c'est-à-dire que les conditions des deux côtés doivent être remplies pour que l'expression soit vraie.
Le symbole && peut également remplacer if, par exemple if(a){fun()} est égal à a&&b
Un autre point très important
Supposons que le tableau soit arr, alors son "dernier élément" est arr[arr.length-1].

Animation de tri

Tri de sélection
C'est aussi un algorithme de tri simple.

Choses :

Trouvez le plus petit élément - jetez-le dans le tableau - puis trouvez le prochain plus petit élément - jetez-le dans le tableau, et ainsi de suite.
Tout d'abord, recherchez le plus petit élément du tableau non trié. La méthode de recherche peut se faire par jugement et affectation continus, c'est-à-dire : en supposant que le premier élément du tableau, array[0], est le plus petit élément, puis le numéro de série du tableau. "le plus petit élément" du tableau est 0
Parcourez ensuite le tableau. Si le deuxième élément du tableau est plus petit que lui, cela signifie que le deuxième élément est le plus petit élément et mettez à jour "0" en "1".
Une fois le parcours terminé, nous savons que l'indice minimum de l'élément de cette série est "n" ; retirez-le directement et stockez-le à la position de départ de la séquence triée (tableau[n])
Continuez ensuite à rechercher le plus petit élément parmi les éléments non triés restants, puis placez-le à la fin de la séquence triée. Notez que l'indice parcouru à ce moment commence à partir de 1. Parce que nous avons déjà retenu un élément minimal.
Et ainsi de suite jusqu'à ce que tous les éléments soient triés.

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

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