Bubble sort
The principle of bubble is to make the largest element or the smallest element "float"
Insert sort, select sort, quick sort, bubble sort are all comparison sort
Ideas
Compare the two adjacent numbers one by one, put the decimals in front and the big numbers in the back.
step1: Compare the first and second numbers, put the decimal before and the large number after. Compare the second number and the third number, put the decimal before and after the big number, continue like this until the last two numbers are compared, put the decimal before and after the big number.
step2: On the second trip: still start from the first logarithm (because it may be due to the exchange of the second number and the third number, the first number is no longer smaller than the second number), put the decimal before and after putting the big number, compare until the penultimate number (the first position is already the largest at the penultimate position). At the end of the second trip, a new maximum number is obtained at the penultimate position (actually the second largest number in the entire sequence).
If this continues, repeat the above process until the sorting is finally completed.
Since decimals are always placed forward and large numbers are placed backward during the sorting process, which is equivalent to the rise of bubbles, it is called bubble sorting.
Bubble sorting animation effect
Implementation: This code is relatively simple and is the most basic and basic code in the algorithm. . .
Three things to note
1. The method of exchanging classes can be solved in javascript with a=[b,b=a][0].
replace
The code copy 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, where array.length is cached
3. Pay attention to the embedded loop, which is to compare from the first number to the nth last number, and n is the comparison step number
function bubbleSort(array) {var l=array.length;for (var i = 0; i < l; i++) {//The number of steps compared is the length of the array for (var j = 0; j < li; j++) {//The number of inline exchanges is compared from the first number to the total length of the last -n numbers, n is the comparison step if (array[j] < array[j - 1]) {array[j] = [array[j - 1], array[j - 1] = array[j]][0]//Swap elements here}}for (var k = 0; k < l; k++) {console.log(array[k] + ",");}console.log('This is the '+(i+1)+' order')}}var a = [6,54,6,22,5,7,8,2,34];bubbleSort(a);Animation effect
Insertion Sort
It’s very simple, it’s the steps for us to touch and insert cards!
Ideas:
1 First, let's say we touched a card, and all the cards in our hands are set to empty = [] touched a push(arr[0])
2 Take out the next card, set it to a, scan from back to front in all our cards empty (already sorted)
3 If the card in your hand is empty[empty.length-n] (sorted) is greater than the new element, move the card to the next position (release space) empty[empty.length-n]= empty[empty.length-n+1]
4Repeat step 3 until the sorted card empty[empty.length-n] is less than or equal to a
5 Insert a into this position empty[empty.length-n]=a
6 Repeat Step 2
However, JavaScript code is still a bit difficult to implement, the code is as follows:
function insert(arr) {var l = arr.length;var empty = [];//Empty array, indicating our hand empty.push(arr[0]);// Let's touch a picture first for (var i = 1; i < l; i++) {//Note that the starting point here is 1, because we have touched one! if (arr[i] > empty[empty.length - 1]) {empty[empty.length] = arr[i]} //If it is larger than the ordered array empty, put it directly to the end for (var j = empty.length; j > 0 && arr[i] < empty[j - 1]; j--) { //Compare from the maximum value with arr in order to vacate the arr. When arr< a certain bit of an ordered array, there is no need to move it. empty[j] = empty[j - 1]; //Move empty[j - 1] = arr[i]; //Put the value to the empty position}//console.log(empty)}return empty}Then the more important knowledge point here is the && symbol, which means "and", that is, the conditions on both sides must be met before the expression is established.
The && symbol can also replace if, for example, if(a){fun()} is equal to a&&b
Another very important point
Assuming the array is arr, then its "last item" is arr[arr.length-1].
Sort animation
Selection sort
It is also a simple sorting algorithm.
Ideas:
Find the smallest element - throw it into the array - find the small one again - throw it into the array, and so on.
First, find the smallest element in the unsorted array. The method you find can use the means of continuous judgment and assignment, that is,: let the first element array[0] of the array be the smallest element, then the sequence number of the "minimum element" in the array is 0.
Then iterate over the array. If the second element of the array is smaller than that, then the second element is the smallest element and update "0" to "1".
After traversing, we know that the subscript of the smallest element in this series is "n"; it is taken out and stored at the starting position of the sorting sequence (array[n])
Then, continue to look for the smallest element from the remaining unsorted elements, and then place it at the end of the sorted sequence. Note that the subscript of the traversal starts from 1 at this time. Because we have already picked out a smallest element.
And so on until all elements are sorted.
function selectSort(array) {var min;var l = array.length;//Cached length for (var i = 0; i < l; i++) {//Start loop, loop 1 times in total, and you can find l elements min = i;//Suppose the first one is the smallest element for (var j = i + 1; j < l; j++) {//Start loop from the first one, traverse if (array[min] > array[j])//Judge whether the subsequent min = j;//Update the "minimum" subscript}if (min != i) {//Because here, because it is operating in the same array, you can directly exchange elements. For example, the first item of the array is i, then I found that the smallest element is array[min], so I need to exchange this min with i. And so on. array[i]= [array[min],array[min]=array[i]][0];//Swap elements}}return array;}What is still noted here is the writing method of exchange array[i]= [array[min],array[min]=array[i]][0]
It is easy to exchange array[i] and array[min]~
Sort animation
Quick sort
Quick sort is the most powerful sorting algorithm at present, which takes advantage of the idea of recursion.
Ideas
Picking out an element from the array is called "benchmark". This can be directly selected using length/2
Iterate through the array, all elements with smaller than the reference value are placed in front of the reference, and all elements with larger than the reference value are placed behind the reference (the same number can be used to either side). In layman's terms, the man stands on the left and the woman stands on the right. .
Then we get an array array = array lArray composed of parts smaller than the benchmark + array rArray composed of parts larger than the benchmark.
Then we only need to "same" process lArray and rArray~
This requires the use of recursion writing. After processing, lArray is divided into lArray's benchmark, which is smaller than lArray's benchmark and larger than lArray's benchmark. .
Then we keep doing things, the man stands on the left and the woman stands on the right. .
Until we find that the length of lArray has become 1, which is not enough to be divided again, we think the sorting is over.
function quickSort(arr) {var l = arr.length;//Cached array length if(arr.length <= 1){return arr}; //If the lArray and rArray length we get are smaller than 1, then there is no need to line up~var num = Math.floor(arr.length / 2);//Pick the number in the middle of the array. Note that length/2 is not necessarily an integer. Use Math.floor to round var numValue = arr.splice(num, 1)[0];//Use the splice method to take an element, pay attention to the syntax var left = [];//Create the left reference container var right = [];//Create the right reference container for (var i = 0; i < l; i += 1) {//Start traverse the array arr[i] < numValue ? left.push(arr[i]) : right.push(arr[i]);//The man stands on the left and the woman stands on the right. . }return quickSort(left).concat([numValue], quickSort(right))//Recursively, continue to operate on the left and right arrays. }Animation effect:
Note here that although arr.splice(num,1) only draws one number, the result of splice is also an array, which requires [0], otherwise the result will be strangely a bunch of arrays of arrays (1). . .
splice reference://www.VeVB.COM/w3school/js/jsref_splice.htm
Math.floor is a reference for Math objects //www.VeVB.COM/w3school/js/js_obj_math.htm
What is recursion: http://baike.baidu.com/view/96473.htm
In addition to quick sorting, the above four algorithms are all simple sorting algorithms, and these four algorithms are very frequently taken during interviews~
It is still important to emphasize here that the above algorithm uses a lot of relevant knowledge about loops and arrays, so you must memorize it!