This article was adapted from CSDN blogger Java3y

The original link: https://blog.csdn.net/Java_3y/article/details/104897426

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.

Here is a brief introduction to the eight basic sorts and basic data structures


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 recursionCopy the code

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 recursionCopy the code

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 treesCopy the code

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 substitution will cause the following exponents 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: Check the string []{]}{]{}(such a string is valid (aligned)

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.

Contain all the knowledge of Java back-end open source project (star) for 5.8 K: https://github.com/ZhongFuCheng3y/3y

If you want to follow my updated articles and shared dry goods in real time, forward + follow the private message keyword “algorithm”

The content of the PDF document is typed by hand


Left god published algorithm books