Refers to a sort in which all elements are stored in memory during sorting

Refers to a sorting in which all elements cannot be stored in memory at the same time during sorting, and they are constantly moved between internal and external memory during the sorting process.

From L[2]~L[n-1], each time the element to be sorted L[i] is inserted into the previously sorted sequence, and the elements larger than L[i] are moved back in order (compare the edges forward, move the element backward)

Best: the elements in the table are already ordered

Worst: reverse order

average

Stablize

Linear tables suitable for sequential storage and linked storage; when it is linked storage, the position of the specified element can be searched from front to back (in fact, most internal sorting algorithms are only suitable for sequential storage)

First fold in half to find the position where the element is to be inserted, and then move all elements after the element to be inserted uniformly.

Number of comparisons: (regardless of the initial state of the table)

Number of moves: depends on the initial state of the sorted table

Stablize

Applies only to sequence tables

Arrange the elements with an interval of d1 (step/increment) into a group, divide the sorting table into several sub-tables, perform direct insertion sorting inside each sub-table, then reduce the increment d2, and repeat the above process until di =1 until

unstable

It is only applicable when the linear table is stored sequentially (because the random access characteristics of sequential storage are used)

Compare the values ​​of adjacent elements from back to front (or from front to back). If they are in reverse order, exchange them until the sequence is compared. The result of each round will be to exchange the smallest element to the first position of the sequence to be sorted (or to the largest element). The elements are swapped to the end of the column to be sorted), and this cycle can be done n-1 times

Best (no exchange occurs in the first sorting pass, jump out of the loop directly)

Worst (in reverse order)

Stablize

The subsequence generated in bubble sorting must be globally ordered (different from direct insertion), and all elements in it must be greater than or less than all elements in the unordered subsequence, and each sorting pass will put an element at its end position

Based on the divide and conquer method, each time a certain element pivot is taken as the benchmark, the sequence is divided into two sub-tables, the left and right, and then recursively sorted within the sub-tables.

Worst (ordered or reversed)

Best (symmetrical, i.e. the sequence is divided into equal parts for each benchmark)

unstable

The algorithm with the best average performance among internal sorting algorithms

No ordered subsequence is generated during the process, but each sorting operation will place the pivot (base) element at its final position.

①For k-way merge sort, k input buffers and 1 output buffer need to be allocated in memory

② Internally sort a total of N records (using an internal sorting algorithm), and generate r internally ordered initial merge segments (r=『N/L], L is the number of input buffers in memory)

③Merging S trips and k routes,

Time to read and write external memory

Time required for internal sorting

Internal merge time

1) Increase the number of merging paths k, and only need multi-way balanced merging

2) Reduce the number of initial merge segments r

In order to prevent the internal merge from being affected by the increase of k, a loser tree is introduced. The k leaf nodes respectively store the records of the k merge segments currently participating in the comparison during the merge process. They are used internally to memorize the "failures" in the left and right subtrees. ", the root node points to the minimum number;

The initial number of comparisons is k-1. After that, only "log2k] times of comparison are needed to select a minimum value.

After the loser tree is introduced, the number of comparisons has nothing to do with k; but as k increases, the number of input buffers may be increased. If the total memory space remains unchanged, the capacity of each buffer needs to be reduced to reduce the number of internal and external memory exchanges. increase

Increase the length of each merge segment (but not fixed length), thereby reducing the number of merge segments

Let the initial file to be sorted be FI, the initial merge segment output file be FO, and the memory work area be WA (can accommodate w records)

1) Input w records from FI to workspace WA.

2) Select the record with the minimum keyword value from WA and record it as the MINIMAX record.

3) Output MINIMAX records to FO.

4) If FI is not empty, input the next record from FI into WA.

5) Select the smallest keyword record from all records in WA with keywords greater than the MINIMAX record as the new MINIMAX record.

6) Repeat 3)~5) until no new MINIMAX record can be selected in WA, thus obtaining an initial merge segment and outputting an end flag of the merge segment to FO.

7) Repeat 2)~6) until WA is empty. From this, all initial merged segments are obtained.

1) Each initial merge segment corresponds to a leaf node, and the number of blocks contained in the merge segment is the leaf weight.

2) Merge tree WPL = the sum of the weighted path lengths of all leaf nodes in the tree

3) The number of disk I/Os during the merge process = WPL of the merged tree*2

1) Supplement the virtual paragraph

2) Construct a k-ary Huffman tree

1) Quick sort is considered to be the best method among current comparison-based internal sorting methods. When the keywords to be sorted are randomly distributed, the average time of quick sort is the shortest.

2) Heap sort requires less auxiliary space than quick sort, and does not suffer from the worst-case scenario that quick sort may have, both sorts are unstable.

3) If the sorting is required to be stable and the time complexity is O(nlog2n), merge sorting can be used.

2-way merge sort treats the list to be sorted as n sub-lists (each sub-list has a length of 1), and then merges them recursively until an ordered list of length n is synthesized.

space efficiency

time efficiency

Stablize

Use the idea of ​​​​multi-keyword sorting to deal with single logical keywords

Most significant bit first (MSD)

Least Significant First (LSD)

The base r=10 requires 10 chain queues; each keyword is 3 bits and requires three "allocation" and "collection" operations.

space efficiency

time efficiency

Stablize

The i-th sorting selects the element with the smallest keyword from L[i...n] and exchanges it with L[i]. Each pass can determine the final position of an element.

Number of comparisons: n(n-1)/2

Number of moves

unstable

heap

Sorting Algorithm

① For a complete binary tree with n nodes, start filtering from the parent node of the last node ("n/2]), and exchange the parent and child nodes to make it called a large root heap (the parent node may continue to move down to the bottom) , and then filter the subtrees rooted at each node ("n/2]~1)

②After outputting the top element of the heap, exchange the last top element of the heap with the top element of the heap, and then recursively exchange the order of the top element of the heap with the larger of the children.

Large root heap creation algorithm

Heap sort algorithm

First place the new node at the end of the heap, then point it upward for the adjustment operation

time complexity

space efficiency

time efficiency

unstable

Suitable for sequential storage (because of random access)