Day 3: 9/23/2003
Sorting is my own algorithm that I feel the most headache, often mix it. I don't know how you learned, if not bad, please tell me some experience!
Look up
First, knowledge point / static lookup -> array
1, what is looking for
/ Dynamic Find -> Chain Tree
l Sequence lookup, time complexity O (N)
l Folding: Condition: Order; Time Combination O (NLOG2N) (Time complexity is actually the height of the tree)
l Index Find: Conditions: All elements of the i 1 block are larger than all elements of the first block.
Algorithm: Determine the block (i) time complexity of X in X: m / 2
Search in the first block X-time complexity: N / 2
Total time complexity: (m n) / 2
L Binary Sort Tree 1) Definition: The left subtree key value is greater than the root node key value; the right sub-key value is smaller than the root key value, and the left and right subtree is a binary sequence tree.
2) Features: Sub-order traversal ordered -> (Delete node to use this property)
3) Finding of the binary sort tree: If the root is greater than the tree to look, the front left subtree moves forward. If the root is smaller than the tree to look, advance to the right tree.
4) Insertion of nodes -> Structure method of binary sorting tree
5) Node deletion (difficult to point) 1, the right one is placed on the rightmost side of the left subtree
2, the left subclands on the left side of the right tree
· AVL tree (binary balance tree): The height of the left and right substrongs can only be 1 layer, ie | h | <= 1 its sub-tree is the same.
· B Tree: N-order B tree is full of conditions 1) Each node (outside) contains N ~ 2N offset.
2) All leaf nodes are on the same layer.
3) All subtots of the B tree are also a B tree.
Features: Reduce the number of layers, reduce the number of comparisons.
Sort
First, knowledge points
1, sorting definition
/ Sort: Only in memory
2, sorted classification
/ External Sort: Sorting with Inner and Externality
Sort: / Direct Insert Sort
1) Insert Sort
/ shell sort
/Bubble Sort
2) Exchange Sort
/ Quick sort
/ Simple Select Sort
3) Select sort pile
/ Championship Sort
4) Multiplexing (Second Road)
5) Base sort (multiple strand sorting)
3, time complexity (in the morning title, don't ask for a brothers and sisters!)
* * * * * * 15 * * * 15 * * *
/ Stable * * * * * * * 15 15 * * * * (no before and after)
Sort
/ Unstable * * * * * * * * 15 15 * * * * (before and after changing)
It is organized: choice, Hill, Heap, rapid sorting is unstable; direct insertion, bubbling, merge sorting is stable. L championship Sort: 13 16 11 18 21 3 17 6
/ / / / / / /
13 11 3 6
/ / / /
11 3
/ /
3 (win, take it out, and make it infinite & Go ON)
L Multiple Sort: 13 16 11 18 21 3 17 6
/ / / / / / /
13, 16 11, 18 3, 21 6, 17
/ / / /
11, 13, 16, 18 3, 6, 17, 21
/ /
3, 6, 11, 13, 16, 17, 18, 21
l Shell Sort Algorithm: 1) Define a step size (or increment) array D [m]; where: D [m-1] = 1 (the last increment must be 1, otherwise it may not be complete)
2) A co-row m, where the quantity of the i-th is d [i], divides the entire sequence into D [i] subsequent sequence, respectively, inserted the D [i] subsequent sequence.
The procedure is as follows: for (i = 0; i {for (j = 0; j {Direct insertion sorting of the i-th sequence; Note: The difference between the subscript is d [i]; } } l Rapid Sort (Smaller) Data (Bigger) D [] I-> 13 16 11 18 21 3 17 6 24 8 <-J Let's look forward from the front, then look after it will come back. Thought: empty one inserted one, I empty j moves, J empty i moves (here I, J refers to the subscript referred to I, J two pointers). One execution algorithm: 1) make Temp = D [0] (hub), i = 0, j = N-1; 2) When the odd times, start from the J position forward to the first element than TEMP, find the position of the replacement to i (D [i] = d [j]; i ;) I should move. 3) When I started from i, I started to find the first number of TEMP, (d [j] = d [i]; j -;) 4) When i = j, end the loop. D [I] = TEMP; Rapid sort by recursive pairs, because rapid sorting is a typical recursive algorithm. l Pile sort Definition: d [n] Satisfaction: d [i] D [i]> d [2i 1] && D [i]> D [2i 2] small heap (small under small) Judging whether the heap should be converted into a tree. Total sort N-1 time Adjustment (focus) Procedure: Flag = 0; While (i <= n-1) { IF (D [i] {IF (D [2 * i 1]> D [2 * i 2]) 8 24 {d [i] <-> d [2 * i 1]; 24 21 -> 8 21 i = 2 * i 1; Else { D [i] <-> d [2 * i 2]; I = 2 * i 2; } } Else Flag = 1; // is a pile } Stacking process: Base sort (multi-keyword sort) Poker: 1) Size -> Assignment 2) Colors -> allocation, collection Thought: Distribute and collect. Build Links: The number of linked list is related to the number of values in keywords. Example: Sort the nine three digits of the lower dead: 321 214 665 102 874 699 210 333 600 Define an array with ten elements: A [0] a [1] a [2] a [3] a [4] a [5] a [6] a [7] a [8] a [9] First 趟 (个): 210 321 102 333 214 665 699 600 874 Results: 210 600 321 102 333 214 874 665 699 A [0] a [1] a [2] a [3] a [4] a [5] a [6] a [7] a [8] a [9] The second (ten): 600 210 321 333 665 874 699 102 214 Results: 600 102 210 214 321 333 665 874 699 A [0] a [1] a [2] a [3] a [4] a [5] a [6] a [7] a [8] a [9] Third 趟 (百): 102 210 321 600 874 214 333 665 699 RESULTS: 102 210 214 321 333 600 665 699 874 (Sedense Success) Recently, I'm very good. This should be his website. He always said that his website is not enough, now it will help him promote it! Http://zhgpa.vicp.net / bbs, everyone has time to go, huh, huh! Thank you everyone, you will recommend a website to you: http://kaowang.com/, a very good test site. Learn a lot of stuff. ! Eight major class algorithms The final one of the programmer exam in the afternoon is generally the eight major algorithms. Everyone should pay attention to recursive, because recent years have been examined, and some will also test two questions. It can be said that if we don't master the recursive, there is no master C. And the recursive is the difficulty of C. In order to control the qualification rate, the programmer exam will not make us easily pass, for the Chinese software industry, I think it should be like this. / Data structure (discrete) Iteration / numerical calculation (continuous) The enumeration strategy is very bad Push Recursion Backtrack Divide greedy Dynamic planning Among them: The four algorithm ideas of recursive, recursive, and grants, and dynamic planning are basically similar. They all become a small problem, but the technical differences.
