Javascript implementation and explanation of sorting algorithm (99js notes)

Bubble sort

The principle of bubbling is to "float" the largest element or the smallest element

Insertion sort, selection sort, quick sort, bubble sort are all comparison sort

Thoughts

Compare two adjacent numbers in sequence, putting the decimal in front and the large number in the back.

step1: Compare the first and second numbers, put the decimals in front and the large numbers in the back. To compare the second number and the third number, put the decimal in front and the large number in the back, and continue like this until comparing the last two numbers, put the decimal in front and the large number in the back.
step2: In the second pass: still start the comparison from the first pair of numbers (because it may be due to the exchange of the second number and the third number that the first number is no longer smaller than the second number), put the decimal first, After the large number is placed, the comparison is continued until the second to last number (the first to last position is already the largest). At the end of the second pass, a new maximum number is obtained at the second to last position (in fact, in the entire sequence is the second largest number).
Continue like this and repeat the above process until the sorting is finally completed.
Since in the sorting process, small numbers are always placed forward and large numbers are placed backward, which is equivalent to bubbles rising, so it is called bubble sorting.
Bubble sort animation effect

Implementation: This code is relatively simple and is the most basic and basic code in the algorithm. . .
Three points to note

1. The method of exchanging classes can be solved by using a=[b,b=a][0] in JavaScript, which is a very clever method,
Replace

Copy code The code is as follows:

var,a,b,temp

temp = a;

a=b;

b = temp

This exchange method
2. Pay attention to the cache of loop variables. Array.length
is cached here. 3. Pay attention to the embedded loop, which compares from the first number to the nth number from the last, and n is the number of steps for comparison

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

Copy after login

Animation effects

Insertion Sort
It’s very simple, just the steps for us to draw and insert the cards!
Idea:

1 First, suppose we draw a card, and all the cards currently in our hand are set to empty = [] and draw a push(arr[0])
2 Take out the next card, set it to a, and scan all our cards empty (already sorted) from back to front
3. If the empty[empty.length-n] (sorted) card in your hand is greater than the new element, move the card to the next position (make space) empty[empty.length-n]= empty[empty.length- n 1]
4 Repeat step 3 until you find the sorted card empty[empty.length-n] is less than or equal to a
5Insert a into the position empty[empty.length-n]=a
6Repeat step 2
However, it is still a little difficult to implement the javascript code. The code is as follows:

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
}

Copy after login

The more important knowledge point here is the && symbol, which means "and", that is, the conditions on both sides must be met for the expression to be true.
The && symbol can also replace if, for example if(a){fun()} is equal to a&&b
Another very important point
Assume the array is arr, then its "last item" is arr[arr.length-1].

Sort animation

Selection sort
It is also a simple sorting algorithm.

Things:

Find the smallest element - throw it into the array - then find the next smallest element - throw it into the array, and so on.
First, find the smallest element in the unsorted array. The method of finding can be through continuous judgment and assignment, that is: assuming the first element of the array, array[0], is the smallest element, then the serial number of the "smallest element" in the array is 0
Then traverse the array. If the second element of the array is smaller than it, it means that the second element is the smallest element, and update "0" to "1".
After the traversal is completed, we know that the minimum element subscript of this series is "n"; directly take it out and store it at the starting position of the sorted sequence (array[n])
Then, continue to find the smallest element from the remaining unsorted elements, and then put it at the end of the sorted sequence. Note that the subscript traversed at this time starts from 1. Because we have already picked out a minimal element.
And so on until all elements are sorted.

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

Copy after login

这里仍然注意的是交换的写法 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))//递归，继续对左右数组进行操作。
}

Copy after login

动画效果：

这里注意 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

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