Detailed summary of various sorting algorithms (Java implementation)

1、 Insert class sort

1. Insert sorting directly

Idea: insert the i-th into the appropriate position in the first I-1

Time complexity: t (n) = O (n) ²)。

Space complexity: s (n) = O (1).

Stability: stable sorting.

If you encounter an element that is equal to the inserted element, the inserted element puts the element you want to insert after the equal element.

Therefore, the sequence of equal elements has not changed. The sequence out of the original unordered sequence is the sequence after the sequence is arranged, so the insertion sequence is stable

Sentinels have two functions:

① Before entering the search (insertion position) cycle, it saves a copy of R [i], so that the content of R [i] will not be lost due to the backward movement of the record;

② Its main function is to "monitor" whether the subscript variable J is out of bounds in the search loop. Once out of bounds (i.e. J = 0), because R [0] It can be compared with yourself that if the cycle determination condition is not established, the search cycle ends, so as to avoid detecting whether J exceeds the boundary every time in the cycle (that is, the cycle determination condition "J > = 1" is omitted)

2. Sort by half insertion

Idea: insert the data into the ordered sequence, and determine the position by constantly comparing the size with the middle point

Time complexity: the comparison time is reduced to o (NSN), but the time cost of moving elements remains unchanged, so the time complexity is always o (n) ²)。

Space complexity: s (n) = O (1).

Stability: stable sorting.

3. Hill sort

Idea: also known as reduced incremental sorting method. The sequence to be sorted is divided into several smaller subsequences, and then sorted by direct insertion sorting method one by one. Finally, a more ordered sequence is sorted once, mainly to reduce the number of moves and improve efficiency. The principle should be that the number of times from disorder to order will be less than that from disorder to order.

Time complexity: O (1.5 power of n)

Space complexity: O (1)

Stability: unstable sorting. {2,4,1,2}, a group of 2 and 1, a group of 4 and 2, Hill sorting, the first 2 and the last 2 will change in position.

2、 Exchange class sorting

1. Bubble sorting

Time complexity: t (n) = O (n) ²)。

Space complexity: s (n) = O (1).

Stability: stable sorting.

2. Quick sort

Idea: to improve bubble sorting, divide the data to be sorted into two independent parts through one-time sorting. All the data in one part is smaller than all the data in the other part, and then quickly sort the two parts of data according to this method. The whole sorting process can be recursive, so as to turn the whole data into an ordered sequence.

Time complexity: average t (n) = O (NSN), worst o (n) ²)。

Spatial complexity: s (n) = O (SN).

Stability: unstable sorting

First, take the first number of the array as a key, set an I and j as the identification before and after, and then take the key to traverse the array from the back to the front, and j --, until we find the first number less than the key, and then exchange the two values. After the exchange, we take the key to traverse from I to the back, and I + +; The loop continues until I = J ends. When it ends here, we will find that values greater than the key will run after the key

3、 Select class sort

1. Simple selection and sorting

Time complexity: t (n) = O (n) ²)。

Space complexity: s (n) = O (1).

Stability: unstable sorting

Idea:

1) Find the element with the smallest keyword from the sequence to be sorted

2) If the smallest element is not in the first place, it is interchanged with the first element

3) From the remaining n-1 elements, find the element with the smallest keyword and repeat steps 1) and 2)

2. Tree selection and sorting

Idea: in order to reduce the number of comparisons, compare the smaller values in pairs until the minimum output is obtained, and then set it to ∞ in the original position for comparison. Until all are output.

Time complexity: t (n) = O (NSN).

Space complexity: it is simpler to select sorting, adding n-1 additional storage space to store the intermediate comparison results, that is, all root nodes of the tree structure. S(n) = O(n)。

Stability: stable sorting.

3. Heap sorting

[to be]

4、 And Merge sort

Merge sort:

Idea: suppose that the initial sequence has n records, first treat the n records as n ordered subsequences, the length of each subsequence is 1, and then merge them in pairs to obtain an ordered subsequence with the whole length of 2 (when n is an odd number, the length of the last sequence is 1)

On this basis, after merging the ordered subsequences with length 2, several ordered subsequences with length 4 are obtained

This is repeated until an ordered sequence of length n is obtained.

Time complexity: t (n) = O (NSN)

Space complexity: s (n) = O (n)

Stability: stable sorting

5、 Allocation class sorting

1. Multi keyword sorting:

[to be]

2. Chain cardinality sorting:

Idea: allocate first and then collect, that is, collect according to a secondary keyword, then collect (the first sort), and then allocate a new sequence with another keyword, and then collect it to complete another sort. In this way, after all keywords are allocated and collected, the sorting is completed.

Time complexity: t (n) = O (d (n + RD))

Space complexity: s (n) = O (RD)

Stability: stable sorting

The above detailed summary of various sorting algorithms (Java implementation) is all the content shared by Xiaobian. I hope it can give you a reference and support programming tips.