First, sorted basic concept
Sort: This is to be arranged in the order of increment (decrease) in the keyword to form a new ordered sequence, called sort. The sequence of N records is {R1, R2, ..., RN}, the corresponding keyword sequence is {K1, K2, ..., KN}, need to determine a sorting P1, P2, ..., PN, which make it respective Keywords meet the relationship between increments (ascending), or decreasing (descending): KP1 £ KP2 £ ... £ KPN or KP1 3 KP2 3 ... 3 KPN
Depending on the location of the sort element, the sorting is sorted and sorted. Sort by: During the sorting process, all elements are adjusted to the order in memory, called within the order. Decoction is the foundation of sorting. The sequencing efficiency is measured with the number of comparisons. Different according to the strategy used, internally sorting can be divided into insert sort, select sort, switching, sorting, sorting, and base sorting, etc.. External Sort: In the case of large amount of data, only block sorting, but blocks and blocks cannot be guaranteed. The outer order is measured with the number of read / write deposits.
Stability of the sorting algorithm: In the sequence to be sorted, there is a plurality of records having the same keyword, sorted, the relative order of these records remain unchanged, and the algorithm is stable; if they are sorted, recorded The algorithm is unstable in the relative order.
The storage structure of the sorting algorithm is usually three: one-dimensional array; linked list; an auxiliary table (such as an index watch).
Second, insertion sorting (Insertion Sort Basic Thought: Divide N-Elements into Dilled and Disorder. Each processing is the element of the unordered number of columns from the elements of the ordered number The front is compared one by one, find the insertion position, insert the element into the appropriate position of the ordered number column.
2.1 Direct Insert Sort (Linear Insert Sort, Stable)
Basic idea: Each time a data element to be sorted, inserted into the appropriate position in the previously ranked number, so that the numerous column is still orderly; until the data element to be sorted is completely inserted. Direct insertion sorting is the simplest sort method. Specific algorithm step: STEP1 is sorted from an ordered number {A1} and unordered number columns {A2, A3, ..., AN}; step2 processes the i = 2, 3, ..., n), number { A1, A2, ..., AI-1} are already in order, and number {AI, AI 1, ..., AN} is disorderly. The AI is compared with AI-1, AI-2, ..., A1 to find the appropriate location to insert the AI. STEP3 Repeat Step2, a total of N-1 insertion processing, and the number is all ordered.
Directly inserted inserted time complexity is O (N2), and the spatial complexity is O (1). [Example]: [Initial Key] [49] 38 65 97 76 13 27 49J = 2 (38) [38 49] 65 97 76 13 27 49J = 3 (65) [38 49 65] 97 76 13 27 49J = 4 (97) [38 49 65 97] 76 13 27 49J = 5 (76) [38 49 65 76 97] 13 27 49J = 6 (13) [13 38 49 65 76 97] 27 49J = 7 (27) [ 13 27 38 49 65 76 97] 49J = 8 (49) [13 27 38 49 49 65 76 97]
Procedure INSERTSORT (VAR R: FileType); // Insert R [1..n] inserted in order, R [0] is a monitor whistle // beginfor i: = 2 to n DO // insert R [2 ], ..., r [n] // beginr [0]: = r [i]; j: = i - 1; while r [0] Procedure SELECTSORT (VAR R: FileType); // Direct sequencing of R [1..n] // BeginFor i: = 1 to n - 1 do // Do N - 1 Select Sort // Begink: = i For j: = i 1 to n DO // Selected minimum elements R [K] // beginif r [K] // Beginif R [J] Fourth, bubbles (stable) 1. Basic idea: Two two two two-two sorted data elements are found to be exchanged, and they are exchanged until there is no in-order data element. 2. Sort Process: Step1 Press the keyword in the longitudinally arranged, then compare each two adjacent keywords from bottom to, if Hungry Day is in reverse order (ie KJ-1> KJ), will two records Exchange position, this operation is repeated until all records are compared, and the exchange is completed. For a bubble treatment, the smallest record of the keyword is arranged at the position of the first record. STEP2 is repeatedly operated on the rear N-1 record, and then schedule the sub-small keyword record in the position of the second record. STEP3 Repeat the above process until no record is required. 3, algorithm analysis: worst case, compare (N2-N) / 2 times, move (N2-N) * 3/2. Algorithm time complexity O (N2). [Example]: 49 13 13 13 13 13 13 38 49 27 27 27 27 27 2765 38 49 38 38 38 49 49 49 49 49 49 49 4913 76 97 65 65 65 65 6527 27 76 97 76 76 76 7649 49 49 76 97 97 97 97Procedure Bubblesort (VAR R: FILETYPE) // Sort from the bottom-up scan // beginFor i: = 1 to n-1 do // Do N-1 Sort // beginnoswap: = true; // Set the sign // for j: = n - 1 DOWNTO 1 do // Scan from the bottom to top // beginiF R [J 1] V. Quick Sort (unstable) 1. Basic ideas: Take a data element in the current sequencing area R [1..H] as a "baseline" (may not be asked x), with this Baseline divides the current unordered zone into two smaller disorder zones: R [1..i-1] and R [i 1..H], and the data elements in the on-left unordered subregion are less than To be equal to the reference element, the data elements in the right silent zone are equal to or equal to the reference element, and the reference X is located at the final order, ie, R [1..I-1] ≤ x.Key ≤ R [i 1 ..H] (1 ≤ i ≤ h), when R [1..i-1] and R [i 1..H] are both empty, the above-described division process is performed until all disorder The data elements in the sub-zone have been sorted. 2. Sort Process: 3, algorithm analysis: The worst case of time complexity is O (N2), preferably the time complexity is O (NLOG2N). [Example]: Initial keyword [49 38 65 97 76 13 27 49] After the first exchange [27 38 65 97 76 13 49 49] After the second exchange [27 38 49 97 76 13 65 49] J to left Scanning, position is unchanged, the third exchange [27 38 13 97 76 49 65 49] I. The position is constant, the fourth exchange [27 38 13 49 76 97 65 49] J to the left scan [ 27 38 13 49 76 97 65 49] (一) Initial key [49 38 65 97 76 13 27 49] After the order [27 38 13] 49 [76 97 65 49] After the sorting [13] 27 [38] 49 [49 65] 76 [97] three After sorting 13 27 38 49 49 [65] 76 97 Sorting Results 13 27 38 49 49 65 76 State after the Sortment PROCEDURE PARTTION (VAR R: FileType; L, H: Integer; Var i: integer) ; // Divide the unordered area R [1, H], i is given to the position of the reference element that has been positioned after this division // begini: = 1; J: = H; x: = r [i ]; // Initialization, X is a reference // REPEATWHILE (R [J]> = X) AND (i Procedure Quicksort (Var R: FileType; S, T: Integer); // Rank to R [S.] // BeginiF S V. Heap Sort1. Basic Thought: Heap Sort is a tree selection, in the ordering process, the R [1..n] is regarded as a complete binary tree, using a complete binary tree The intrinsic relationship between the dual-proof point and the child's node is selected to select the smallest element. 2. Definition of the heap: Sequences K1, K2, K3, ..., Kn of n elements are called a heap, when and only when the sequence satisfies characteristics: ki ≤ k2i ki ≤ k2i 1 (1 ≤ i ≤ [ N / 2]) The stack is essentially a complete binary tree that satisfies the following nature: any non-leaf node in the tree is larger than the keyword equal to the node of his child. For example, sequences 10, 15, 56, 25, 30, 70 are a heap, which corresponds to a complete binary tree as shown above. This pile is the smallest key of the root point (called a pile), which we call it a small root. Conversely, if the keywords in any non-leaves nodes in the full binary tree are larger than the keyword equal to their children, it is called a large root. 3. Sort Process: The stacking is uses a small root heap (or large root heap) to select the record implementation of the keyword small (or maximum) in the current unordered area. We may wish to use large roots to sort. The basic operation of each sort is: Adjust the current unordoaming area to a large root of the key, select the maximum pile record of the keyword, and exchange it and the last record in the disorder zone. In this way, it is exactly the same, and the selection is in contrast, the ordered zone is formed in the tail of the original recording area and gradually enlarged to the entire recording area. [Example]: Building a keyword 42, 13, 91, 23, 24, 16, 05, 88 build PROCEDURE SIFT (VAR R: FileType; I, M: Integer); // In array R [i..m ] Middle adjustment R [I], so that it is a heap that it is a fully binary tree. It is known to be left and right sub-tree (2i 1 <= m) in advance, all pile // beginx: = r [i]; j: = 2 * i; // If j <= m, r [j] Is the left child of R [i] // while j <= m do // If the current is adjusted node R [i] has left child R [J] // beginif (j] and r [j] .key Procedure Heapsort (VAR R: FileType); // Sort R [1..n] // begin for i: = n DIV DOWNTO 1 Do / / Establish initial push // sift (r, i, n) for I: = n DOWNTO 2 do // Perform n-1 sort // begin T: = R [1]; R [1]: = r [i]; r [i]: = t; // will currently The last record exchange // sIft (R, 1, I-1) // in the top recording and heap is heapped // endnd; //HEAPSORT / Six, comparisons and selection of several sort algorithms 1. Select the factors that need to be considered in the sorting method: (1) Number of elements to be arranged n; (2) The size of the element itself; (3) The structure of the keyword and its distribution The situation; (4) The conditions of the language tool, the size of the auxiliary space, etc. 2. Summary: (1) If N is smaller (n <= 50), you can use direct insertion ordering or direct selection. Since the recording mobile operation required for direct insertion sorting is more direct sequencing, it is better when the amount of information of the record itself is large. (2) If the initial state of the file has been basically ordered in the keyword, it is advisable to use direct insertion or bubble sorting. (3) If N is large, the time complexity is used as a sorting method of o (NLOG2N): rapid sorting, stack sorting or sorting. Rapid sorting is currently considered to be the best way in the internal ordering method based on comparison. (4) On the comparison sorting method, each time two keywords are compared, only two possible transfer, so it can be used to describe the comparison determination process with a binary tree, thereby proves that when the file When a keyword is randomly distributed, there is at least O (NLOG2N) at least O (NLOG2N) by means of a "comparison" sorting algorithm. (5) When the amount of information of the record itself is large, in order to avoid a large amount of time moving record, you can use a linked list as a storage structure. Seven, return to sort (stabilization) Merge's ordering method is to merge two (or more) ordered forms into a new ordered list: that is, divided the sequence of sequences into several subsequences, each subsequent sequence is ordered, and then The order of order sequences are combined into an overall ordered sequence. The subsequences of the already orderly subsequences are obtained, and the sequence of completely ordered:, first, each subsequence is in order, and the subsequence is in order. If two ordered tables are merged into a ordered table, it is called 2-way to return. Mental Sort Specific steps: Step1 treat N records to be sorted as an ordered sequence of length 1. The adjacent sequence is two or two ordered and the length of 2 is 2 ordered, and the obtained N / 2 length 2 has a sequence sequence having a sequence of 2 * 2; STEP3 according to STEP2 In a manner, the adjacent sequence sequence is repeated to operate until a ordered sequence is becoming. Eight, Hill sort (reduced increment order, unstable) Hill Sort is a fast sorting method, from D.L.Shell. Basic thinking is: still use the insert method, the sorting process is implemented by switching and moving data items. Take an integer D1 less than n and as the first increment, divide all the records of the file into D1 group, all the records of the D1 times are placed in the same group, in the same group, direct insertion sorting in each group; then take The second increment D2 Example, there are keyword sequence {5, 4, 3, 6, 7, 1, 8, 9} Algorithm implementation: J: = 10; I: = 1; While J> 1 do Begin J: = J DIV 2; Repeat Alldone: = true; For index: = 1 to 10-j DO Begin i: = index j; IF a [index]
Begin Temp: = a [index]; a [index]: = a [i]; a [i]: = TEMP; Alldone: = false; END; END; Until alldone END;
