Before we understand the algorithm, let’s take a look at what an algorithm is
Definition: Algorithm (Algorithm) refers to the accurate and complete description of the problem-solving scheme. It is a series of clear instructions to solve the problem. The algorithm represents a systematic method to describe the strategy mechanism of solving the problem. In other words, it is possible to obtain the required output within a limited time for a certain standard input. If an algorithm is flawed or not suitable for a certain problem, executing this algorithm will not solve the problem. Different algorithms may use different time, space or efficiency to accomplish the same task. The pros and cons of an algorithm can be measured by space complexity and time complexity.
Common algorithms in python
Bubble Sort
Efficiency: O(n2)
principle:
Compare adjacent elements, if the first one is greater than the second, swap them two;
Do the same for each pair of adjacent elements, from the first pair at the beginning to the last pair at the end. After finishing, the last element will be the largest number, here can be understood as a trip;
Repeat the above steps for all elements except the last one;
Continue to repeat the above steps for fewer and fewer elements each time, until there is no pair of numbers to compare, and the last number sequence is arranged from largest to smallest;
def bubble_sort(data):"""
Bubble Sort
: param data::return:"""
for i inrange(len(data)-1): #Number of trips
for j inrange(len(data)-i-1): #Traverse the data and exchange in turn
if data[j] data[j+1]: #When the larger number comes first
data[j],data[j+1]=data[j+1],data[j] #Swap the positions of two numbers
if __name__=='__main__':import random
data_list=list(range(30))
random.shuffle(data_list)print("pre:",data_list)bubble_sort(data_list)print("after:",data_list)
# result:
# pre:[22,11,19,16,12,18,20,28,27,4,21,10,9,7,1,6,5,29,8,0,17,26,13,14,15,24,25,23,3,2]
# after:[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29]
Select sort
Efficiency: O(n2)
principle:
Each time an element is selected from the list to be sorted, and it is compared with other numbers in turn. If a number in the list is smaller than the selected number, the positions will be exchanged. After all the numbers are compared, the smallest will be selected Put it on the far left (this process is called a trip);
Repeat the above steps until all the data elements to be sorted are arranged;
demo：
def select_sort(data):"""
Select sort
: param data:List of data to be sorted
: return:"""
for i inrange(len(data)-1): #Number of trips
min_index=i #Record the index of the smallest number from the beginning of i, we start from the leftmost
for j inrange(i+1,len(data)): #The number of cycles required for each pass
if data[j]< data[min_index]: #When a number in the sequence is smaller than the starting number, update the minimum index position
min_index=j
data[i],data[min_index]=data[min_index],data[i] #After one trip, swap the position of the minimum value, the first trip is the smallest
if __name__=='__main__':import random
data_list=list(range(30))
random.shuffle(data_list) #Shuffle list data
print("pre:",data_list)select_sort(data_list)print("after:",data_list)
# result:
# pre:[20,11,22,0,18,21,14,19,7,23,27,29,24,4,17,15,5,10,26,13,25,1,8,16,3,9,2,28,12,6]
# after:[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29]
Insertion sort
Efficiency: O(n2)
principle:
Take sorting from small to large as an example. Element 0 is the first element. Insertion sorting starts from element 1, and inserts as far as possible to the front.
When inserting, the insertion position and the trial position are divided. The initial insertion position of element i is i, and the trial position is i-1. When inserting element i, it is compared with i-1, i-2. The element at the tentative position is larger than the inserted element, then the tentative element is moved backward by one position, and the insertion position of the element i is moved forward by one position until the tentative element is smaller than the inserted element or the inserted element is in the first position.
Repeat the above steps, and finally complete the sorting
demo：
def insert_sort(data):"""
Insertion sort
: param data:List of data to be sorted
: return:"""
for i inrange(1,len(data)): #Unordered area data
tmp = data[i] #The number of benchmarks inserted for the i time
for j inrange(i,-1,-1):if tmp < data[j -1]: #j is the current position, test j-1 position
data[j]= data[j -1] #Move current location
else: #Location is determined as j
break
data[j]= tmp #Restore the current position
if __name__=='__main__':import random
data_list=list(range(30))
random.shuffle(data_list) #Shuffle list data
print("pre:",data_list)insert_sort(data_list)print("after:",data_list)
# result:
# pre:[7,17,10,16,23,24,13,11,2,5,15,29,27,18,4,19,1,9,3,21,0,14,12,25,22,28,20,6,26,8]
# after:[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29]
Heap sort
Heap definition: It is essentially a complete binary tree. If the value of the root node is the smallest value of all nodes, it is called a small root heap, and if the value of the root node is the maximum value of all nodes, it is called a big root heap.
Efficiency: O(nlogn)
principle:
Build the list of data to be sorted into a heap structure (build a heap);
Through operations such as shift_up or shift_down, the top element of the heap is the largest element (for example, a large root heap);
Remove the top element of the pile, put the last element on the top of the pile, readjust the pile, and make the top element of the pile the largest element again (the second largest element compared to the first time);
Repeat 3 operations until the heap is empty, and finally finish sorting;
Merge sort
Efficiency: O(nlogn)
Space complexity: O(n)
principle:
Apply for space so that its size is the sum of two sorted sequences, and this space is used to store the merged sequence;
Set two pointers, the initial positions are the starting positions of the two sorted sequences;
Compare the elements pointed to by the two pointers, select a relatively small element to put into the merge space, and move the pointer to the next position;
Repeat step 3 until a pointer reaches the end of the sequence;
Copy all remaining elements of another sequence directly to the end of the merged sequence.
So far, this article on Is there an algorithm in the python language will be introduced. For more related content, is there an algorithm in python, please search for ZaLou.Cn's previous articles or continue to browse the related articles below. I hope you will support ZaLou more in the future. Cn!
Recommended Posts