Share commonly used sorting examples in Python

• Stability and significance of sorting algorithm

• Bubble sort

• Complexity and stability Sex

• Selection sort

• Insertion sort

• Hill sort

• Quick sort

• Comparison of efficiency of common sorting algorithms

Stability and significance of sorting algorithms

In the sequence to be sorted, there are records with the same keywords. After sorting, the relative order of these records remains unchanged, then the sorting algorithm is stable.

Unstable sorting cannot complete sorting of multiple keywords. For example, integer sorting, the higher the number of digits, the higher the priority, sorting from high digits to low digits. Then the sorting of each bit requires a stable algorithm, otherwise the correct result cannot be obtained.

That is, When multiple keywords are to be sorted multiple times, a stable algorithm must be used

Bubble sorting



def bubble_sort(alist):
    """
    冒泡排序
    """
    if len(alist) <= 1:
        return alist

    for j in range(len(alist)-1,0,-1):
        for i in range(j):
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]

    return alist

Complexity and Stability

• Optimal time complexity: \(O(n)\) Traversal does not find any elements that can be exchanged, and sorting ends

• Worst time complexity: \(O(n^2)\)

• ##Stability: stable

Selection sort

Selection sort (Selection sort) is a simple and intuitive sorting algorithm. Here's how it works. First, find the smallest (large) element in the unsorted sequence and store it at the beginning of the sorted sequence. Then, continue to find the smallest (large) element from the remaining unsorted elements, and then put it at the end of the sorted sequence. And so on until all elements are sorted.

Insertion sort

Insertion sort builds an ordered sequence. For unsorted data, scan from back to front in the sorted sequence to find the corresponding position and insert it. In the implementation of insertion sort, during the scanning process from back to front, the sorted elements need to be repeatedly and gradually moved backward to provide insertion space for the latest elements.



def insert_sort(alist):
    """
    插入排序
    """
    n = len(alist)
    if n <= 1:
        return alist

    # 从第二个位置，即下表为1的元素开始向前插入
    for i in range(1, n):
        j = i
        # 向前向前比较，如果小于前一个元素，交换两个元素
        while alist[j] < alist[j-1] and j > 0:
            alist[j], alist[j-1] = alist[j-1], alist[j]
            j-=1
    return alist

Complexity and Stability

• Optimal time complexity: O(\(n\)) (ascending order Arrangement, the sequence is already in ascending order)

• Worst time complexity: O(\(n^2\))

• Stability : Stable

Hill Sort

Hill Sort (Shell Sort) is an improvement of insertion sort, and the sorting is not stable. Hill sorting groups records by a certain

increment, and sorts each group using the direct insertion sorting algorithm; as the increment gradually decreases, each group contains more and more keywords. When the amount is reduced to 1, the entire file is divided into one group, and the algorithm terminates.

def shell_sort(alist):
    
    n = len(alist)
    gap = n//2
    
    # gap 变化到0之前，插入算法之行的次数
    while gap > 0:
        
        # 希尔排序， 与普通的插入算法的区别就是gap步长
        for i in range(gap,n):
            j = i
            while alist[j] < alist[j-gap] and j > 0:
                alist[j], alist[j-gap] = alist[j-gap], alist[j]
                j-=gap
    
        gap = gap//2

    return alist

Complexity and Stability

• Optimum time complexity: \(O(n^{1.3})\) (it does not require itself to be ordered)

• Worst time complexity: \(O(n^2)\)

##Stability: Unstable
Quicksort

Quicksort (Quicksort) divides the data to be sorted into two independent parts through one sorting. All the data in one part is smaller than all the data in the other part. , and then use this method to quickly sort the two parts of the data respectively. The entire sorting process can be performed recursively, so that the entire data becomes an ordered sequence.

The steps are:

Pick out an element from the sequence, called the "pivot"
Re- In a sorted sequence, all elements smaller than the base value are placed in front of the base, and all elements larger than the base value are placed behind the base (the same number can go to either side). After this partition, the datum is in the middle of the sequence. This is called a partition operation.
Recursively sort the subarray of elements smaller than the base value and the subarray of elements greater than the base value.
The bottom case of recursion is when the size of the array is zero or one, that is, it has always been sorted. Although it continues to recurse, this algorithm will always end, because in each iteration (iteration), it will put at least one element to its final position.

Comparison of efficiency of common sorting algorithms



The above is the detailed content of Share commonly used sorting examples in Python. For more information, please follow other related articles on the PHP Chinese website!