What is simple insertion sort

Simple insertion sort is an effective algorithm that divides a set of sequences to be sorted into two parts: sorted and unsorted. In the initial state, the sorted sequence only contains the first element. , the elements in the unsorted sequence are "N-1" elements except the first one, and then the elements in the unsorted sequence are inserted into the sorted sequence one by one.

Simple insertion sort

Divide a set of sequences to be sorted into sorted and The two unsorted parts. 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, the elements in the unsorted sequence are inserted one by one into in a sorted sequence. 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

Related introduction:

The so-called sorting algorithm refers to reordering one or more sets of data according to a predetermined pattern through specific algorithm factors. This new sequence follows certain rules and reflects certain patterns. Therefore, the processed data is easy to filter and calculate, which greatly improves calculation efficiency. For sorting, we first require it to have a certain degree of stability, that is, when two identical elements appear in a sequence at the same time, after a certain sorting algorithm, the relative positions of the two before and after sorting will not change. In other words, even if there are two identical elements, they are different during the sorting process and are not allowed to be confused.

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