How to sort in python_What are the methods of sorting in python-Python Tutorial-php.cn

How to sort in python

DDD

Release： 2023-08-29 14:54:36

Original

3483 people have browsed it

Python sorting methods include bubble sort, selection sort, insertion sort, quick sort, merge sort, heap sort, radix sort, etc. Detailed introduction: 1. Bubble sorting, sorting by comparing adjacent elements and exchanging their positions; 2. Selection sorting, sorting by finding the smallest element in the list and placing it at the end of the sorted part ; 3. Insertion sort, sorting by inserting each element into the appropriate position of the sorted part; 4. Quick sort, using the divide and conquer method to divide the list into smaller sublists, etc.

How to sort in python

Operating system for this tutorial: Windows 10 system, Python version 3.11.4, Dell G3 computer.

Python is a powerful programming language that provides a variety of sorting methods to sort data. In this article, we'll cover at least 7 different sorting methods, with detailed code examples.

1. Bubble Sort:

Bubble sort is a simple sorting algorithm that sorts by comparing adjacent elements and exchanging their positions. It iterates through the list repeatedly until no swaps occur.

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

Copy after login

2. Selection Sort:

Selection sort is a simple sorting algorithm that finds the smallest element in the list and places it in the sorted part. Sort at the end.

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

Copy after login

3. Insertion Sort:

Insertion sort is a simple sorting algorithm that sorts by inserting each element into the appropriate position of the sorted part.

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

Copy after login

4. Quick Sort:

Quick sort is an efficient sorting algorithm that uses the divide-and-conquer method to divide the list into smaller sublists and then recursively Sort a sublist.

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

5. Merge Sort:

Merge sort is an efficient sorting algorithm that uses the divide-and-conquer method to divide the list into smaller sublists and then recursively Sort the sublists and finally merge them into an ordered list.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    left = merge_sort(left)
    right = merge_sort(right)
    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

Copy after login

6. Heap Sort:

Heap sort is an efficient sorting algorithm that uses a binary heap data structure for sorting.

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l < n and arr[i] < arr[l]:
        largest = l
    if r < n and arr[largest] < arr[r]:
        largest = r
    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

Copy after login

7. Radix Sort:

Radix sort is a non-comparative sorting algorithm that sorts elements based on the number of digits.

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10
    for i in range(n):
        index = arr[i] // exp
        count[index % 10] += 1
    for i in range(1, 10):
        count[i] += count[i-1]
    i = n - 1
    while i >= 0:
        index = arr[i] // exp
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1
    for i in range(n):
        arr[i] = output[i]
def radix_sort(arr):
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        counting_sort(arr, exp)
        exp *= 10
    return arr

Copy after login

This is a detailed code example of 7 different sorting methods. According to different data sets and performance requirements, choosing a suitable sorting algorithm can improve the efficiency and performance of the code

The above is the detailed content of How to sort in python. For more information, please follow other related articles on the PHP Chinese website!