Tell a story
I heard from my good friends that there was a big brother who made programs, mainly writing algorithms. When HE resigned from his previous company, the company required to sign a confidentiality agreement, and guaranteed that if there was no disclosure, he would still be paid monthly for two years
What? Yeah, you heard me right. That’s it, meow. Why is that? Because he knows algorithms, algorithms are fundamental, and I’m not going to tell you that he makes close to a million dollars a year. See, that’s our little goal to keep learning algorithms, to make $100 million!
The world of algorithms
Hi, welcome to the world of algorithms. Algorithms are everywhere. They’re all around us
- In “The Social Network,” Zuckerberg at the start of Facebook uses a mathematical formula to write an algorithm that compares photos of two girls to which one is prettiest
- Alphago beat the world champion of Go
- Enter X Treasure, it will recommend the products you like
- Order take-out, and next time we’ll recommend your usual place
- Hit a pesticide and try to match players with the same heroes you choose
- The Nuggets probably wouldn’t have room for this article
All of the examples above are actually algorithmic
An algorithm is a process of qualitative change (actually a difference of 1 minute to 1 second).
Program = algorithm + data structure
The current hot AI technology is not a sudden emergence, but also based on the accumulation of various combinations of algorithm experiments to run.
Algorithms are like the brain of a robot, telling the robot how to act, think and so on. Otherwise you think, they are born beautiful cannot abandon, that is impossible
All that said, why do we learn algorithms? To make it a hundred million? Yes or no
No one has a good internal skill, no matter how many moves are empty
For the porters of nature, algorithms can make your programs more efficient
Well, isn’t that enough for your ass?!
Today’s topic starts with simple sorting and search algorithms, which are often asked in middle and advanced interviews. Even these can not answer how to be a senior, do experts, earn it 100 million!
Sorting and search algorithms
Sorting algorithm
There are a lot of commonly used sorting algorithms, such as bubble sort, select sort, insert sort, merge sort, quick sort and heap sort, we will look at these sorting algorithms, to understand the idea
Bubble sort
// Create an arraylist to handle sorting and searching data structuresfunction ArrayList() {
let arr = [];
this.insert = function(item) {// Insert data into the array arr.push(item); }; this.show =function() {// show the structure of the arrayreturn arr.join('<'); }; // Bubble sort looks familiar? That's right, it's often asked in interviews, and it's the easiest sorting algorithm this. BubbleSort =function () {
let len = arr.length;
for (leti = 0; i < len; I ++) {// The inner loop does not need to be compared again because the outer loop has already run one timefor (let j = 0; j < len - 1 - i; j++) {
if(arr[j] > arr[j + 1]) {// Compare the current item with the next item, [arr[j], arr[j +1]] = [ARr [j +1], arr[j]]; }}}}; } // Test case, which can be used in all subsequent algorithmslet arr = [5, 4, 3, 2, 1];
let createList = function(arr) {
let list = new ArrayList();
for (let i = 0; i < arr.length; i++) {
list.insert(arr[i]);
}
return list;
};
letitem = createList(arr); console.log(item.string()); < 4 < 3 < 2 < 1 item.bubblesort (); console.log(item.string()); // 1 < 2 < 3 < 4 < 5Copy the codeBubble sort is the easiest one in terms of implementation, and it’s the worst one in terms of runtime, because it’s O(n^2) because it’s doing two loops
Here’s a look at the bubbling sort workflow:
Selection sort
A selection sort algorithm takes a value in the array as a benchmark, compares it with other values, replaces the benchmark if it is smaller than the benchmark, and so on. No more verbose straight up the code
function ArrayList() {// omit... // selectSort this.selectsort =function () {
let len = arr.length,
min;
for (leti = 0; i < len - 1; i++) { min = i; // We take the first value as the benchmarkfor (letj = i; j < len; J++) {// the inner loop starts from I to the end of the arrayif (arr[min] > arr[j]) { // 比标杆的值还小，就替换新值
min = j;
}
}
if(i ! [arr[I], arr[min]] = [arr[min], arr[I]]; }}}; }Copy the codeSelect sort we can see that there are two nested loops, so the complexity is the same as bubbling sort, so let’s take a look at the select sort workflow
Insertion sort
The insertion sort algorithm assumes that the first item of the array is already sorted, and compares it directly with the second item. If it is larger than the second item, the index and value are swapped, thus sorting by inference
function ArrayList() {// omit... // insertSort this.insertsort =function () {
letlen = arr.length, index, tmp; // By default, the first item is sorted, starting with the second itemfor (leti = 1; i < len; i++) { index = i; TMP = arr[I]; // The index must be greater than 0, and if the value of the previous item in the array is greater than the value of the temporary variable // the value of the previous item is assigned to the current item, and index--while(index > 0 && arr[index - 1] > tmp) { arr[index] = arr[index - 1]; index--; } arr[index] = tmp; // Insert into the correct position after a replacement}}; } // The test cases are written in bubble sortletarr = [3, 5, 1, 4, 2]; // Select * from the top of the list, and select * from the top of the listforThe loop I starts at 1 where index = I -> 1; next -> 2 tmp = arr[1] -> 5; next -> arr[2] -> 1whileNext 2>0 && 5 > 1 Next 1>0 && 3 > 1 ARr [2] = ARr [1] -> 5 ARr [1] = arr[1] -> 5 ARr [1] = arr[1] -> 5 arr[1] = arr[0] -> 3 index--; Arr [index] = TMP -> arr[1] = 5; Next arr[1] = 1 arr[0] = 1 arr[0] = 1Copy the codeAs usual, here is the insert sort workflow:
The sorted array should not be too large
Sometimes I think about the same sorting algorithm, how these three algorithms can’t do this, can’t do that. Try to ask if there is a reliable, everyone precious time can not delay. The answer, of course, is yes. Here we go
Merge sort
First of all, the memory of a great man, Von Neumann, ‘father of the computer’. It’s worth remembering because this is the guy who came up with this really good sorting algorithm. Well, at this time, I want to recite a poem, not simple ah, not simple!
function ArrayList() {// omit... // mergeSort this.mergesort =function() { arr = mergeRecurve(arr); // Use recursion because you need to keep splitting until there is only one item in the array; / / recursionfunction mergeRecurve(arr) {
letlen = arr.length; // If the array has only one item, the stop condition of recursion is returned directlyif (len === 1) return arr;
let mid = Math.floor(len / 2);
let left = arr.slice(0, mid);
letright = arr.slice(mid, len); The merge function merges and sorts smaller arrays into larger arrays. The merge function merges and sorts smaller arrays into larger arrays. The merge function merges and sorts smaller arrays into larger arraysreturn merge(mergeRecurve(left), mergeRecurve(right));
}
functionMerge (left, right) {// Take two arrays and merge them together to return a large arraylet res = [],
lLen = left.length,
rLen = right.length,
l = 0,
r = 0;
while(l < lLen &&r < rLen) {// If the left item is smaller than the right item, add the left item to the larger arrayif(left[l] < right[r]) { res.push(left[l++]); // And proceed to the next comparison}else{ res.push(right[r++]); // Add the smaller items in right to the larger array}} // Add the remaining items in left and right arrays to the larger arraywhile (l < lLen) {
res.push(left[l++]);
}
while (r < rLen) {
res.push(right[r++]);
}
returnres; // Return a large sorted array}}Copy the codeMerge sort is a divide-and-conquer algorithm. Don’t understand divide-and-conquer? It’s easy. You think of it as a dichotomy. We’ll talk about it later, which is to take a big problem and break it into smaller problems, and when each of the smaller problems is solved, the big problem is solved
Implementation idea: cut the original array into small arrays until each array has only one item, and then combine the decimals into a large array, and finally get a sorted large array. You can see the execution process below to understand more
Focus on
letarr = [7, 9, 8]; /* arr = mergeRecurve([7, 9, 8]); Left = [7], right = [9, 8] merge(mergeRecurve([7]), mergeRecurve([9, 8])) So [9, 8] continues to recursively split, left = [9], right = [8] merge([9], [8]) res = [], L = 0, r = 0while(0 < 1 && 0 < 1) {if(9 < 8) {don't go here}else {
res.push(8)
}
}
while (0<1) {
res.push(9);
}
while(1<1) {don't go here}return[8, 9] Go back to the previous level to merge([7], [8, 9]), push to the same process as above */Copy the codeI’m going to introduce you to the most commonly used sort algorithm, quicksort, which performs better than any other sorting algorithm in order nlog to the n
Quick sort
The quicksort algorithm finds an intermediate item in the array as a marker and then creates a double pointer, the first item on the left and the last item on the right. Move the left pointer until it is greater than the value of the marker, then move the right pointer until it is smaller than the marker, then switch positions and repeat the process to achieve a partition
function ArrayList() {// omit... // quickSort this.quicksort =function() { quick(arr, 0, arr.length - 1); / / recursion}function quick(arr, left, right) {
let index;
if(arr.length > 1) { index = partition(arr, left, right); / /if (left < index - 1) {
quick(arr, left, index - 1)
}
if(index < right) { quick(arr, index, right); }}} // Partition functionfunction partition(arr, left, right) {
letpoint = arr[Math.floor((left+right)/2)], i = left, j = right; / / double pointerwhile (i <= j) {
while (arr[i] < point) {
i++;
}
while (arr[j] > point) {
j--;
}
if(i<=j) { [arr[i], arr[j]] = [arr[j], arr[i]]; // switch positions i++; j--; }}returni; }}Copy the codeIt might be a little confusing to look at the code directly, but don’t be afraid to see a cockroach. Let’s just do a little bit of a case-by-case analysis, just look at a simple chestnut
/ *letarr = [7, 9, 8]; Quick ([7, 9, 8], 0, 2); quick([7, 9, 8], 0, 2); Point = [7, 9, 8][math.floor (0+2)/2] -> 9 I -> 0, math.floor (0+2)/2] -> 0, J -> 2 // I and j are double Pointers, one starting from left and one starting from rightwhile(I <= j) {0 <= 2 // The first time 7 < 9 // the next arR [1] -> 9 9 < 9 is not validwhile(arr[i] < 9) { i++; I -> 1} // ARr [2] -> 8 > 9 is not validwhile(arr[j] > 9) { j--; } // I ->1, j->2if(I < = j) {1 < = 2 / / exchange position [arr [I], arr [j]] = [arr [2], arr [1]] - > [8, 9] i++; i -> 2 j--; } // Divide the rearranged array into [7, 8, 9]returni; Return the partition coordinate I -> 2} at this point index is calculated to be 2ifQuick ([7, 8, 9], 0, 1); // index->1,right->-1}if(index < right) {quick([7,8,9], 2, 3); } Follow the above steps to continue to understand, refueling refueling */Copy the codeIs it time to have a cup of coffee to refresh yourself? Didn’t you? It doesn’t matter, then raise their right hand slowly up, high above the head, and…… Give it a good pat on the head, and now we’re all satisfied, refreshed and dripping! Ha ha, no more bullshit. No more bullshit
Above we talked about the sorting algorithm of several different ways, can be said to achieve a preliminary victory, the algorithm is still a long way, the road is long, I will search up and down. Let’s talk about search algorithms
Look at the big screen
Search algorithm
Search algorithm here focuses on the interview is often asked about binary search method
Array.indexof () {array.indexof ();} array.indexof () {array.indexof ()
To put it bluntly, this is actually a kind of search, but its implementation is actually very low, not efficient, look at the code
let arr = [1, 9, 8, 2, 3];
arr.indexOf(8); // 2
arr.indexOf(0); // -1
function ArrayList() {// omit... // indexOf this.indexOf =function(item) {
for (let i = 0; i < arr.length; i++) {
if (item === arr[i]) {
returni; }}return- 1; }; }Copy the codeThe code is actually compared one by one in order, which is a little inefficient. Let’s take a look at our key protection object, binary search
Binary search method
Audiences who watched li Yong’s “Lucky 52” in the early stage should remember a link in which the program would give the guest a product and ask him to guess the price within a certain period of time. According to the quotation, Li Yong would say it was higher or lower until he got the product correctly
For those of you who haven’t seen it, it doesn’t matter. It’s just a game to guess the price. You can say whether it’s high or low or right
I miss when I was a kid, carefree kid, haha
Look at the code
function ArrayList() {// omit... // This. BinarySearch =function(item) { this.quickSort(); // Select * from the listlet low = 0,
high = arr.length - 1,
mid, ele;
while(low <= high) { mid = Math.floor((low + high) / 2); // select arr[mid]; // Use the median value to compare to the search value itemif(ele < item) {// If mid = 4, low = mid = 1; }else if(ele > item) {// high = mid -1; // high = mid -1; }else{// The median value is 4, so bingo, returnreturnmid; }}return- 1; // If (1) {// if (-1) {// if (-1) {// If (-1) { }Copy the codeDichotomous search is over, the program is late, just the right time. Let’s take a look at the above
comb
Sorting algorithm
- Bubble sort -> nested two-layer loop, and the following selection sort performance is poor
- Select sort -> no brains upstairs
- Insert sort -> performs much better, but only for small arrays
- Merge sort -> is a reputable sort algorithm
- Quicksort -> very common sorting algorithm, performance is also very good
Search algorithm
- Dichotomous search method -> Guess what, bet big bet small, small on the small side to find, big on the big side to find
Well, the above content in the interview, when the advanced front-end will also be asked, here also hope to read this article students, interview smoothly, find a satisfactory job
It’s useful, it’s efficient, it’s useful for refactoring
So I will continue to study the content of the learning algorithm, so as to continue to share with you, thank you, slut!