preface

I’ve been at work for a while and sometimes joke with my colleagues, “If you asked me to write a quicksort by hand right now, I’m not sure I could do it.”

It’s really easy to forget if you haven’t been working with algorithms for a while. Don’t believe it? Now you’re wondering if you can write a heap sort by hand.

As anyone who has experienced college admissions knows, algorithms and data structures are inevitable.

In the written test, the most important thing is to rely on algorithm questions. Big companies like Pinduoduo and Toutiao will ask you several algorithmic questions. If you don’t have an AC, you won’t have a chance to get an interview.

In the interview (live or video) will also ask algorithm questions, the difficulty is certainly not as difficult as the written test. Imagine a situation where, in the middle of an interview, the interviewer asks you to reverse the binary tree and ask yourself if you still know how to do it.

Without further ado, if you’re still in college you can get started with sorting and all kinds of basic data structures. I spent a week putting together a nice PDF of eight basic sorts and linked lists/binary trees/stacks/queues.

This PDF reading experience is certainly better than the public account and the major blog platform articles. PDF content pure hand play, have don’t understand can ask me.

Here is a brief introduction to the eight basic sort and basic data structure, each sort of idea and basic explanation and source code in PDF.

Bubble sort

The first time you sort the array, the maximum value is at the end of the array. Because they switch, it takes n minus one sort.

Code implementation points: two for loops, the outer loop controls the number of sorts, the inner loop controls the number of comparisons. After each trip, the number of comparisons should be reduced by 1

Selection sort

Find the largest element in the array and swap it with the last element. When there’s only one number, you don’t have to pick it, so you have to sort n minus 1 times

There are two for loops. The outer loop controls the number of cycles sorted, and the inner loop finds the maximum number of cycles and swaps with the last element of the current cycle array

Insertion sort

Insert an element into an ordered array. It is initially unknown if there is any ordered data, so the first element is treated as ordered. Compare it to an ordered array. If it is larger, insert it directly. If it is smaller, move the array element to find a suitable place to insert it. When you only have one number, you don’t need to insert, so you need n minus 1 sort

Code implementation: a for loop inserts a while loop. The outer for loop controls the number of runs that need to be sorted. The while loop finds the appropriate insertion position (and the insertion position cannot be less than 0).

Quick sort

The prerequisite for learning quicksort is to understand recursion

Find an element (node) in the array and place the smaller element (node) to the left and the larger element (node) to the right. Once you go down, the ones smaller than the nodes are on the left, and the ones larger than the nodes are on the right. Keep doing this… .

Code implementation: fulcrum in the middle, using L and R to represent the smallest and largest positions of the array. Keep comparing until you find numbers that are smaller (larger) than the fulcrum, and then switch, decreasing the range. Recurse L to the element (j) before the fulcrum. Recursively fulcrum from the next element (I) to the element R

Merge sort

The prerequisite for mergesort is to understand recursion

Merge two sorted arrays into one ordered array. Compare and merge elements separated as ordered arrays. Keep breaking and merging until there is only one element

Code implementation: in the first sort is essentially two elements (as two already ordered array) to merge, continue to perform such operations, the final array ordered, split left, right, merge…

Heap sort

A prerequisite for learning heap sorting is to understand binary trees

The root node is larger than the left child and the right child. To build a heap, compare the size of the root node with the size of the left child and the size of the right child. Swap the largest node to the root node until the largest node is at the top of the tree. It is then swapped with the last element of the array

Code implementation: replace as long as the left or right subtree is greater than the current root node. The replacement will cause the following subtrees to change, so comparisons will also be made until each node achieves the condition of parent > child

Hill sorting

Hill sort is an enhanced version of insert sort. Hill sort divides the array into N groups for insertion sort, ** until the array is macroscopically ordered, ** when the array is finally inserted, it does not have to move so many positions

The hill increment is gap = gap / 2, but there is more for loop than normal insert sort.

Radix sort (bucket sort)

Radix sort (bucket sort) : cut the number into a, ten, hundreds, thousands into different buckets, put once according to the bucket order recycling once, until the largest number of digits put ~ then the array is in order

Code implementation: first find the maximum value of the array, and then according to the maximum value /10 as a condition for the loop (as long as >0, then there are bits). Combine the ones place, the tens place,… Distribute to the bucket and recycle each time you distribute

recursive

Recursion is used very, very often in algorithms, sorting algorithm quicksort and merge sort need to use recursion (at least recursion is the most convenient implementation).

To use recursion you must know two conditions: the recursive exit (the condition that terminates recursion) and the recursive expression (the rule)

Tip: In recursion it is common to cut the problem into two parts (1 and the idea of the whole). This allows us to quickly find recursive expressions (patterns).

Hanrota implementation:

Basic data structure

Linked lists, queues, binary trees, and stacks are all very basic data structures. There are algorithms for each data structure, such as:

  • LeetCode No206: Reverse linked lists
  • LeetCode No20: Verifies the string[] {]} {] {} (Is such a string valid (alignment)
  • LeetCode No104: Maximum depth of tree
  • LeetCode No102: Sequence traversal tree
  • .

Data structures such as dictionary tree, red-black tree and graph should be able to do, but linked lists, queues, binary trees and stacks of data structures (LeetCode simple) should be able to do.

The last

Finally, the sorting algorithm/data structure code may not be optimal, and the code implementation is written in a way that is easy to understand. Almost every line of code has a comment that should make sense.

There are several reasons why you should write the most basic algorithms and data structures now that you have been working on them for a while:

  • I am a pairtypographyPeople who are pursuing if early following my classmates may find that MY GitHub, article navigationread.meIt will be replaced frequently. Now,GitHubThe navigation wasn’t to my liking (it was too long), and the earlier article, to be honest, wasn’t very well formatted, so I decided to redo it.
  • My article will be distributed to several platforms, but no one will read the article after it is posted, and the graph bed may be suspended because of the anti-theft chain of the platform. And because so many readers ask me, “Can you convert your articles to PDF? “
  • I’ve written a lot of serial-level articles that don’t change much and are perfect for persistence.

For the above reasons, I decided to put together my series of articles into a PDF/HTML/WORD document. To be honest, it took me a long time to create this document. In order to prevent white piao, concern my public number reply “888” can be obtained.

The content of the document is typed by hand. If you don’t understand anything, you can ask me directly (the official number has my contact information).

The last issue of “Servlet” PDF received a good response on wechat, the target was 180 views, although I was a little short of the target, but I still made this issue!

If you’re looking at more than 500 this time, a series will come out next week. What do you want to see

Open source project (5.8K STAR) :Github.com/ZhongFuChen…

If you want to follow my updated articles and shared dry goods in real time, you can search Java3y on wechat.

The content of the PDF document is typed by hand. If you don’t understand anything, you can ask me directly (the official account has my contact information).