One 、 Simple algorithm 【 Interview questions 】
1. Bubble sort
Sorting ideas ： Compare the elements corresponding to two adjacent subscripts , If the conditions are met, exchange positions
# Bubble sort
# 1. Ascending sort
numlist = [24,56,78,8,7,100,45,56,7,8]
# The outer loop ： It controls the number of rounds compared
for i in range(len(numlist) - 1):
# print(" Number of rounds :",i)
# Inner circulation ： It controls the number of comparisons in each round , Both indexes
for j in range(len(numlist) - 1 - i):
# Compare , If the conditions are met, exchange the position
# Conditions ： Index small elements > Index large elements
# print(" The comparison index is ：",j,j + 1)
if numlist[j] > numlist[j + 1]:
numlist[j],numlist[j + 1] = numlist[j + 1],numlist[j]
print(numlist)
print("*" * 50)
# 2. null
numlist = [24,56,78,8,7,100,45,56,7,8]
# The outer loop ： It controls the number of rounds compared
for i in range(len(numlist) - 1):
# Inner circulation ： It controls the number of comparisons in each round , Both indexes
for j in range(len(numlist) - 1 - i):
# Compare , If the conditions are met, exchange the position
# Conditions ： Index small elements > Index large elements
if numlist[j] < numlist[j + 1]:
numlist[j],numlist[j + 1] = numlist[j + 1],numlist[j]
print(numlist)
# 3
numlist = [24,56,78,8,7,100,45,56,7,8]
numlist.sort() # Ascending
print(numlist)
numlist = [24,56,78,8,7,100,45,56,7,8]
numlist.sort(reverse=True) # Descending
print(numlist)
# self-taught ： Insertion sort , Quick sort
2. Selection sort
Sorting ideas ： Fix a subscript , Then compare the elements corresponding to this subscript with the following elements in turn , If the conditions are met, exchange positions
# Selection sort
# 1. Ascending sort
numlist = [24,56,78,8,7,45,67,67,8,100,88]
# The outer loop ： It controls the number of rounds compared
for i in range(len(numlist) - 1):
# print(" Number of rounds :",i)
# Inner circulation ： It controls the number of comparisons in each round , Both indexes
for j in range(i + 1,len(numlist)):
# Compare , If the conditions are met, exchange the position
# Conditions ： Index small elements > Index large elements
# print(" The comparison index is ：",i,j)
if numlist[i] > numlist[j]:
numlist[i],numlist[j] = numlist[j],numlist[i]
print(numlist)
print("*" * 50)
# 2. null
numlist = [24,56,78,8,7,45,67,67,8,100,88]
# The outer loop ： It controls the number of rounds compared
for i in range(len(numlist) - 1):
# Inner circulation ： It controls the number of comparisons in each round , Both indexes
for j in range(i + 1,len(numlist)):
# Compare , If the conditions are met, exchange the position
# Conditions ： Index small elements > Index large elements
if numlist[i] < numlist[j]:
numlist[i],numlist[j] = numlist[j],numlist[i]
print(numlist)
3. In order to find
Look for ideas ： Compare the elements to be found with the elements in the list in turn , If equal , The search is successful
# In order to find
numlist = [24,56,78,8,7,45,67,67,8,100,88]
ele = 66
# 1.index()
# index1 = numlist.index(ele)
# print(index1)
# 2.
for index2 in range(len(numlist)):
if numlist[index2] == ele:
print(" Indexes ：",index2)
# 3. simulation index()
for index2 in range(len(numlist)):
if numlist[index2] == ele:
print(" Indexes ：",index2)
break
else:
print(" The element to be found does not exist ")
4. Binary search
Look for ideas ： In ascending order , Compare the element to be found with the element corresponding to the middle subscript , If it is greater than the element corresponding to the middle subscript , Then go to the right half to find
Be careful ： The premise is that the list is orderly （ Ascending or descending ） Of , Narrow the search scope by halving , Improve search efficiency
# Binary search
# 1. The list is in ascending order
numlist = [24,56,78,8,7,45,67,67,8,100,88]
print(numlist)
numlist.sort()
print(numlist)
ele = 78
left = 0
right = len(numlist) - 1
while left <= right:
# Calculate the middle subscript
middle = (left + right) // 2
# Compare the size of the element corresponding to the middle subscript and the element to be found
if ele > numlist[middle] :
# The right half , to left Reassign
left = middle + 1
elif ele < numlist[middle]:
# The left half , to right Reassign
right = middle - 1
else:
# equal
print(middle)
# Just find the result , You can end the cycle ahead of time
break
else:
print(" The element to be found does not exist ")
print("*" * 50)
# 2. The list is in descending order
numlist = [24,56,78,8,7,45,67,67,8,100,88]
numlist.sort(reverse=True)
ele = 78
left = 0
right = len(numlist) - 1
while left <= right:
# Calculate the middle subscript
middle = (left + right) // 2
# Compare the size of the element corresponding to the middle subscript and the element to be found
if ele > numlist[middle] :
# The left half , to right Reassign
right = middle - 1
elif ele < numlist[middle]:
# The right half , to left Reassign
left = middle + 1
else:
# equal
print(middle)
# Just find the result , You can end the cycle ahead of time
break
else:
print(" The element to be found does not exist ")
