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

Editor to share with you how to use python to achieve the insertion sorting algorithm, I hope you have something to gain after reading this article, let's discuss it together!

Insert sort popular understanding: insert sort is to take an element from an array and compare it with one or more elements in front of it, and insert it into the right place according to its size. We should pay attention to the difference between the distinction and the selection sort: the selection sort and the insert sort actually artificially cut the array into the front and back halves, and the elements in the first half of the selection sort are always sorted. Each element in the second half is compared with the element in the'0' index position in the second half of the array, and the insertion sort is when the array is traversed each time. Take an element from the second half of the array element and compare it with the first half of the element one by one. If it is larger than a certain element, it will be placed behind it, and if it is smaller than a certain element, it will be placed in front of it. Here, larger or smaller than a certain value is compared by going forward one at a time. If the above description is not clear, the following example can help to further understand:

Def insert_sort (alist):''insert sort' 'length = len (alist) # the first element is not moved by default Start with the element with index 1 and compare it with the previous element: print (I) for j in range (print (I) for j in range): # flashback to take the value if alist in range one by one [j] < if alist [j-1]: Alist [j-1], alist [j] = alist [j] Alist [j-1] # outputs the array print (alist) after this comparison

Return alist

If _ _ name__ = ='_ _ main__': alist = [3, insert_sort 2, 1, 7, 6, 5, 3] print (alist))

Code flow: first get the list length, the number of outer for loops for the list length minus 1, the number of each loop in the inner loop theoretically increases one by one, because the elements in the first half of the array increase one more each time after a complete traversal, while the latter half is exactly the opposite, decreasing by one at a time. Let's take a look at how it is implemented through the results:

1 # first result [2, 3, 1, 7, 6, 5, 3] 2 # second result [1, 2, 3, 7, 6, 5, 3] 3 # third result [1, 2, 3, 7, 6, 5, 3] 4 # fourth result [1, 2, 3, 6, 5, 3] 5 # fifth result [1, 2, 3, 5, 6, 7, 3] 6 # sixth result [1, 2, 3, 3, 5, 6, 7]

# final result [1, 2, 3, 3, 5, 6, 7]

Result analysis: when the first round is ergodic, the index value of 1 in the original array alist is 2, which is compared with the value 3 of 0 index, and if it is less than 3, the exchange is carried out, and the final result is obtained [2, 3, 1, 7, 6, and 5] In the second traversal, the value of index 1 of 2 is less than the value of index 3, and the exchange result is [2 for 1, 3, 7, 6, 5, 3], which is not over yet, because the loop list of the inner Liao loop is [2 Jing 1 language 1], and then the value of 1 index is less than the value 2 of 0 index. At this time, the final result of this round can be obtained [1, 2, 3, 7, 6, 5, 3], and so on.

Complexity: the complexity of the insertion sort is n-square at best, regardless of whether the original array is ordered or not, always take each element behind it and compare the size of all the elements in front of it one by one, because you can't guarantee that the element you take is smaller than every element in front of it.

After reading this article, I believe you have a certain understanding of "how to use python to achieve insertion sorting algorithm". If you want to know more about it, you are welcome to follow the industry information channel. Thank you for reading!

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.