Home > Backend Development > C++ > What are the sorting algorithms for arrays?

What are the sorting algorithms for arrays?

WBOY
Release: 2024-06-02 22:33:59
Original
717 people have browsed it

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.

What are the sorting algorithms for arrays?

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]
Copy after login

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]
Copy after login

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
Copy after login

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)
Copy after login

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
Copy after login

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]
Copy after login

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!

Related labels:
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template