Shulou(Shulou.com)06/02 Report--

Python in how to achieve insertion sorting, many novices are not very clear about this, in order to help you solve this problem, the following editor will explain in detail for you, people with this need can come to learn, I hope you can gain something.

Insert sort

The time complexity of insertion sorting (Insertion Sort) is also O (n ^ 2), but the idea is quite different from bubble sorting and selective sorting.

Insertion sorting is a bit like "playing cards" in daily life.

Insert sorting ideas: maintain a sorted sublist that is always at the front of the list, and then gradually expand the sublist to the full table

To put it simply: for an input unordered table, it is divided into two parts, the first part is a sorted sublist, and the second part is the data to be sorted. Each insertion sort will find one from the following data to be inserted into the previously sorted sublist (to find its appropriate location), and finally complete the sorting of all the data.

Steps:

The first insert sort: the previous sublist contains only one element, and the data to be inserted starts with the second element. Insert the second element into the appropriate position in the sublist to complete the arrangement of the two elements

Second insert sort: insert the third element into the appropriate place in the sublist to complete the sorting of the first three data items

……

The nth-1st insert sort: the last data is inserted into the appropriate place in the sublist to complete the sorting of all elements

The main purpose of data alignment in insertion sorting is to find the appropriate location of the element to be inserted.

Worst case: alignment to be sent with all elements of the sublist-- O (n ^ 2)

Best-case scenario: each insertion sort only needs to be compared once-O (n)

Find "the right place"

Insert sorting to find specific ideas for the right location:

Take out the element to be inserted (stored in a variable) to vacate the position (record the location), compare the extracted element with the elements from the back to the front of the sublist one by one, and if the element to be inserted is small, move the sublist element backward one bit. The loop stops until the entire sublist is aligned or the element to be inserted is larger than the current sublist element. Insert the element to be inserted into the current position

Is it helpful for you to read the above content? If you want to know more about the relevant knowledge or read more related articles, please follow the industry information channel, thank you for your support.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.