What are the sorting algorithms in Python?

Commonly used sorting algorithms in Python include bubble sort, insertion sort, selection sort, quick sort, merge sort and heap sort. The principles of these sorting algorithms will be introduced below, and corresponding code examples will be given.

1. Bubble sort:
   Bubble sort is a simple and intuitive sorting algorithm. It repeatedly traverses the list to be sorted, comparing the sizes of two adjacent elements, and moving the larger element backward. During each iteration, the largest element "bubbles" to the end of the list.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

2. Insertion sort:
   The basic idea of ​​insertion sort is to insert the elements to be sorted into the correct position one by one in the sorted list. Insertion sort starts from the second element, compares each element to the previous sorted list and inserts it into the appropriate position.

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

3. Selection sort:
   Selection sort traverses the list each time, finds the smallest element and swaps it with the current position. Keep repeating this process until the entire list is sorted.

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

4. Quick sort:
   Quick sort is an efficient sorting algorithm. It uses the idea of ​​​​Divide and Conquer to divide a list into two sublists and then recursively sort the sublists.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

5. Merge sort:
   Merge sort divides the list into two sublists, sorts each sublist, and then merges the sorted sublists together.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

6. Heap sort:
   Heap sort is a tree selection sorting algorithm that uses the properties of binary heaps for sorting. Heaps can be divided into max heaps and min heaps. The root node of the max heap is the largest element, and the root node of the min heap is the smallest element.

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[i] < arr[left]:
        largest = left
    if right < n and arr[largest] < arr[right]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)
    return arr

The above are several commonly used sorting algorithms in Python, and corresponding code examples are provided. Different sorting algorithms are suitable for different situations and data sizes. Choosing an appropriate sorting algorithm according to the actual situation can improve the operating efficiency of the program.

The above is the detailed content of What are the sorting algorithms in Python?. For more information, please follow other related articles on the PHP Chinese website!