Preface
Python Daily practice is coming , This article has been included in ：《Python Practice every day 》 special column
The purpose of this column is , Help study Python Xiaobai improves programming ability , Train logical thinking , Weekly continuous update , Welcome to subscribe for free ！！！
Selection sort （Selection sort） It is a simple and intuitive sorting algorithm . It works as follows . First, find the minimum in the unsorted sequence （ Big ） Elements , To the beginning of the collating sequence , then , Continue to find the smallest from the remaining unsorted elements （ Big ） Elements , And then at the end of the sorted sequence . And so on , Until all the elements are sorted .
The main advantages of selective sorting are related to data movement . If an element is in the right final position , Then it will not be moved . Select sort to exchange one pair of elements at a time , At least one of them will be moved to its final position , So right. n The table of elements can be sorted at most n-1 Secondary exchange . In all sorts of sorting methods that rely entirely on swapping to move elements , Sorting by choice is a very good .
See the operation process , Let's take a look at the dynamic graph implementation ：
Implementation code ：
import random
# random Library randomly generates a list
sec_list = [random.randint(1, 100) for i in range(8)]
# Gets the current list length
length = len(sec_list)
print(" Unordered list ：" % sec_list)
# The outer loop
for i in range(length - 1):
min_index = i
# The inner loop starts with the last digit of the number that is considered to be the smallest , All the way to the end
for j in range(i + 1, length):
# If the smallest element is larger than the following element
if sec_list[min_index] > sec_list[j]:
# Reassign the smallest element
min_index = j
# When the inner loop performs a full round, the position is changed
sec_list[min_index], sec_list[i] = sec_list[i], sec_list[min_index]
print(" The first %s In good order ：%s" % (i + 1, sec_list))
print(" The result of the final arrangement is ：%s" % sec_list)
Running results ：
- Optimal time complexity ：
O(n2)- Worst time complexity ：
O(n2)- stability ： unstable （ Consider the case in which ascending order selects the maximum each time ）
- Select sort is the same as bubble sort , Need to carry out
N*(N-1)/2Compare it to , But all it takes is N Secondary exchange , When N When a large , The time influence of the number of exchanges is greater , Therefore, the time complexity of sorting isO(N^2).- Although the time complexity of selective sorting and bubble sorting belongs to the same order of magnitude , But there is no doubt that sorting by choice is more efficient , Because it has fewer switching operations , And when the time order of the exchange operation is much larger than that of the comparison operation , The speed of selection sorting is quite fast .
1. Programming white contestant
Many novice programmers have learned basic grammar , But I don't know the purpose of grammar , I don't know how to deepen the image , I don't know how to improve myself , This is the time It's very important to brush one question independently every day （ Refining into a God ）, You can go to the introductory training of programming beginners on Niuke online . This topic is at the entry level of programming , Suitable for Xiaobai who has just learned grammar , The topic involves basic grammar of programming , Basic structure, etc , Each question has practice mode and examination mode , The test mode can be restored for simulation , You can also practice through practice mode .
Link address ： Cattle from | Beginner programming training
2. Advanced programming player
When you have gradually mastered the key points of knowledge after basic practice , Go to this time Learn data structures in special exercises 、 Algorithm basis 、 Fundamentals of computer etc. . Start with the simple , If you feel up, do it in medium difficulty , And more difficult topics . These three are the knowledge points that must be tested in the interview , We can only insist on practicing more every day by ourselves , Refuse to lie flat and continue to brush questions , Continuously improve yourself to impact a satisfactory company .
Link address ： Cattle from | Special exercises
Speed up , Let's attack the big factory together , If you have questions, leave a message in the comment area to answer ！！！
