What is insertion sort?

Insertion sorting has two types: simple insertion sorting and Hill sorting. The time complexity of simple insertion sorting is [O(N2) stable sorting], and the time complexity of Hill sorting is [and incremental sequence. Select related, non-stable sorting].

Insertion sort

Simple insertion sort

Put the group to be sorted The sequence is divided into two parts: sorted and unsorted. In the initial state, the sorted sequence only contains the first element, and the elements in the unsorted sequence are N-1 elements except the first one; thereafter there will be no The elements in the sorted sequence are inserted into the sorted sequence one by one. In this way, after N-1 insertions, the number of elements in the unsorted sequence is 0, then the sorting is completed

Time complexity: O(N2) Stable sorting

Hill sorting

Divide a set of elements to be sorted into several sequences at certain intervals, and perform insertion sorting respectively. The "interval" set at the beginning is larger, and the interval is gradually reduced in each round of sorting, until the "interval" is 1, that is, the last step is to perform simple insertion sorting

Time complexity: and increment The selection of sequences is related to unstable sorting

The above is the detailed content of What is insertion sort?. For more information, please follow other related articles on the PHP Chinese website!