The most basic algorithm should be the sorting algorithm. Today, let's briefly introduce several common sorting algorithms

Bubble sorting

Bubble sorting visits the sorted element list once every round, and compares two adjacent elements in turn. If the order of the two elements is incorrect, exchange them and adjust the order. In this way, the maximum value of each round of comparison will float to the top, that is, it will become the last value. According to this idea, the last element of each round does not need to participate in the next round of comparison (because it is already the largest).

python implementation:

def bubble_sort(arr):
    for i in range(1, len(arr)):  
    # This indicates how many times to sort. For example, if there are only two elements, it must be sorted only once, so the number of times from 1 to element length
        for j in range(0, len(arr)-i):
        # This represents the loop from the first element to the following elements. i is subtracted because the elements after len(arr)-i have been sorted
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
				# The step here is to put the largest element in the last position of the element currently being sorted
				#(some of those already arranged will not participate in sorting)
    return arr

Select sort

The idea of selecting sorting is to select the smallest value on the left every time and execute len(arr)-1 time.

python implementation:

def selection_sort(arr):
    for i in range(len(arr)-1):
        min_num_index = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_num_index]:
                min_num_index = j
        if i != min_num_index:
            arr[i], arr[min_num_index] = arr[min_num_index], arr[i]
    return arr

Quick sort

Quick sort is a little more complicated. It will set the boundary value, divide the array into left and right parts through the boundary value, and then continue to set the boundary value in each part and continue to group until one of the remaining boundary values becomes empty. That is, if you do it according to this method, it will become a recursive method. Of course, there should be no recursion, but it will be more troublesome to write.

Here we introduce how to use recursion to realize quick sorting:

def quick_sort(arr):
    if arr == []:   # Here is the end condition of recursion. In fact, only one element in arr can also be used as the end condition,
    # But it is better to set it to null, because if there is only one element in the arr, one side of the next partition is definitely null
        return arr
    else:
        delimiter = arr[0]  # If arr is not empty, the specified number of separators is set to the first element of arr
        left = quick_sort([num for num in arr[1:] if num <= delimiter])
        # All elements less than the number of separators are placed on the left, and their own methods are called recursively
        right = quick_sort([num for num in arr[1:] if num > delimiter])
        # Elements larger than the number of separators are placed on the right, and their own methods are called recursively
        return left + [delimiter] + right   # Finally, return the sorted left + separator + right
    return arr

Insert sort

The idea of insert sorting is to insert the subsequent unordered elements into the previously sorted elements every time.

python implementation:

def insert_sort(arr):
    for i in range(1, len(arr)): # Here we loop each element once
        for j in range(i, 0, -1):  # Loops forward from the element currently looped to
            if arr[j] < arr[j-1]:  # If this number is smaller than the previous number, the two numbers will change order,
						            # And since it is judged from the first element,
						            # So the smallest element goes directly to the far left. It's kind of like bubble sort
                arr[j], arr[j-1] = arr[j-1], arr[j]
    return arr

Merge sort

Merging and sorting is relatively complex. The idea is to continuously divide the list into two groups, and then continuously merge the separated data. During merging, the two groups of data are orderly each time. Therefore, it is very convenient to sort (that is, take one data from the left (or right) of the two groups of data for comparison each time, Which side is smaller (or larger) will be taken out and listed in the new list, and the group that has taken one data will take another data and compare it with the data of the other group left before. The complexity of this sorting method is relatively small).

python implementation:

def delete_first(l):  
# Here I define a function to delete the first element of the list every time,
# If there is a duplicate element in the python list, the duplicate value in the list will be deleted by using the pop or remove function,
# So I set up a function to delete the first element each time
    if len(l) == 1:
        l= []
    else:
        l= l[1:]
    return l
    
def merge_sort(arr):
    if len(arr) <= 1:  # Here is the end condition
        return arr
    else:
        middle = len(arr)//2 # separate from the middle of the list
        left = merge_sort(arr[:middle])  # Same recursion
        right = merge_sort(arr[middle:])
        arr = []  # The final results are stored here
        while len(left) and len(right):  # If the two groups of data to be compared are not empty, continue the comparison
            if left[0] >= right[0]:  # If the left of the first element is large, the first element on the right is added to the result
                arr.append(right[0])
                right = delete_first(right) # Delete the first element (because it is already in the result)
            else:
                arr.append(left[0])  # Same as above, but the right side is larger
                left = delete_first(left)
        extra = left+right  # Because one side of the list may be finished first, the two tables are added at last
        #(here, because one side must be empty, the direct addition order will not change to avoid judging which side has elements)
        for i in extra:
            arr.append(i)
            # Just put the remaining elements directly at the end of the result(
            # This is no problem to understand, because the remaining elements are the largest ones, otherwise they would have been sorted before)
    return arr

Shell Sort

The idea of hill sorting is to sort the elements to be sorted in different numbers at each interval. At the beginning, the interval is large and gradually reduced to very small (stop when the interval is 0). The interval here is realized in the form of remainder, and then divide the previous remainder by 2 every time. Hill sort is an improved way of insertion sort.

python implementation:

def shell_sort(arr):
    n = len(arr)
    gap = n // 2 # initial interval
    while gap > 0:
        for i in range(gap, n):   # Insert sorting. Since the values at i-gap and I will be compared, you can sort backwards from gap
            while i >= gap and arr[i - gap] > arr[i]:  # Here, insert and sort each set of selected data         
                arr[i - gap], arr[i] = arr[i], arr[i - gap]
                i -= gap # Insert the embodiment of sorting (insert data into the previously sorted data)
        gap //=Since the sorting order is # easier before, it will be easier after
        # The / / = sign here indicates the remainder of gap
    return arr

Ding!

In fact, in addition to the sorting methods described above, there are other sorting algorithms, such as cardinality sorting, heap sorting, etc., but these are relatively less commonly used. In addition, I have not been in contact with them, so I won't introduce them here. If you are interested, you can check it yourself.

Reference: greedy college machine learning course: https://www.bilibili.com/video/BV1X34y1S7DW