What are the sorting algorithms for arrays?

Array sorting algorithm is used to arrange elements in a specific order. Common types of algorithms include: Bubble sort: swap positions by comparing adjacent elements. Selection sort: Find the smallest element and swap it to the current position. Insertion sort: Insert elements one by one to the correct position. Quick sort: divide and conquer method, select the pivot element to divide the array. Merge Sort: Divide and Conquer, Recursive Sorting and Merging Subarrays.

Introduction and practice of array sorting algorithm

In computer science, the array sorting algorithm is used to sort a set of elements according to a specific An algorithm for sorting in order. Sorting algorithms are divided into many different types based on their principles and efficiency. The following will introduce some common array sorting algorithms and demonstrate their use through practical cases.

Bubble sort

Bubble sort is a simple and easy-to-understand sorting algorithm. Its basic principle is to compare the sizes of adjacent elements in sequence. If the previous If the element is larger than the next element, their positions are swapped. This process is repeated until all elements are in order.

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

Selection sort

Selection sort is also a simple sorting algorithm. Its principle is to find the smallest element of the unsorted part and exchange it with the current position element. . Then repeat the process until all elements are in order.

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

Insertion sort

Insertion sort is a sorting algorithm based on insertion operations. Its basic principle is to insert elements one by one into the correct position of the sorted part until All elements are arranged in order.

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

Quick sort

Quick sort is a divide-and-conquer sorting algorithm. Its principle is to divide the array into two sub-arrays by selecting a pivot element, and then recursively Sort both subarrays until all elements are in order.

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)

Merge sort

Merge sort is a stable and efficient divide-and-conquer sorting algorithm. Its principle is to recursively divide the array into smaller sub-arrays. , then sort and merge the subarrays until all elements are in order.

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

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

Practical case

Suppose we have an unordered listarr = [5, 2, 8, 3, 1, 9] , we can use the quick sort algorithm to sort it, the code is as follows:

arr = [5, 2, 8, 3, 1, 9]
sorted_arr = quick_sort(arr)
print(sorted_arr)  # 输出：[1, 2, 3, 5, 8, 9]

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