排序算法（ Python 代码实现）|祀梦的个人博客

排序算法简介

比较排序算法

冒泡排序

冒泡排序是一种简单直观的排序算法，它的核心思想是不断比较相邻的元素并交换它们的位置，直到整个序列都变得有序。就像水中的气泡一样，较小的元素逐渐浮到序列的前面，较大的元素慢慢沉到后面。

import random

def func(nums):
    for i in range(1,len(nums)):
        for j in range(len(nums) - i):
            # 每次把大的换到后面去
            if nums[j] > nums[j+1]:
                nums[j],nums[j+1] =  nums[j+1],nums[j]
    return nums

nums = [random.randint(-10,10) for _ in range(random.randint(3,10))]
print(f"排序前:{nums}")
print(f"排序后:{func(nums)}")

选择排序

选择排序是一种简单但不那么高效的排序算法，它的核心思想是每次从未排序部分找到最小（或最大）的元素，然后放到正确的位置。

文章：排序算法--选择排序--详解及代码_选择排序法-CSDN博客

import random

def func(nums):
    # 每次找到待排序列表中的最小的一个，与第一个兑换，默认第一个最小
    for i in range(len(nums)-1):
        idx = i
        for j in range(i+1,len(nums)):
            if nums[j] < nums[idx]:
                idx = j
        nums[i],nums[idx] = nums[idx],nums[i]
    return nums

nums = [random.randint(-10,10) for _ in range(random.randint(3,10))]
print(f"排序前:{nums}")
print(f"排序后:{func(nums)}")

插入排序

插入排序是一种构建有序数组的排序算法，它的核心思想是逐步将未排序的元素插入到已排序的部分，就像整理扑克牌时，把每张新抽到的牌插入正确的位置。

文章：排序算法——直接插入排序（图文超详细！）-CSDN博客

import random

def func(nums):
    for i in range(len(nums)):
        temp = nums[i]
        j = i - 1
        while j >= 0 and nums[j] > temp:
            nums[ j + 1 ] = nums[j]
            j -= 1
        nums[j+1] = temp
    return nums

nums = [random.randint(-10,10) for _ in range(random.randint(3,10))]
print(f"排序前:{nums}")
print(f"排序后:{func(nums)}")

希尔排序

希尔排序是一种改进版的插入排序，通过分组和间隔优化排序过程，以减少数据移动次数，提高效率。

文章：排序算法 —— 希尔排序（图文超详细）-CSDN博客

import random

def func(nums):
    gap = len(nums) // 2
    while gap > 0:
        for i in range(gap,len(nums)):
            temp = nums[i]
            j = i - gap
            while j >= 0 and nums[j] > temp:
                nums[j+gap] = nums[j]
                j -= gap
            nums[j + gap] = temp
        gap //= 2
    return nums

nums = [random.randint(-10,10) for _ in range(random.randint(3,10))]
print(f"排序前:{nums}")
print(f"排序后:{func(nums)}")

归并排序

归并排序是一种基于分治思想的排序算法，它的核心思想是先将数组分成两个部分，分别排序后再合并，最终得到一个有序数组。

文章：排序——归并排序（Merge sort）-CSDN博客

import random

def merge(left, right):
    merged = []
    while left and right:
        if left[0] < right[0]:
            merged.append(left.pop(0))
        else:
            merged.append(right.pop(0))
    return merged + left + right

def func(nums):
    length = len(nums)
    if length == 1:
        return nums
    return merge( func(nums[:length//2]) , func(nums[length//2:]) )

nums = [random.randint(-10,10) for _ in range(random.randint(3,10))]
print(f"排序前:{nums}")
print(f"排序后:{func(nums)}")

快速排序

快速排序是一种高效的分治排序算法，它通过选取一个基准元素（pivot），将数组划分为两部分，并递归地进行排序，从而快速得到有序序列。

文章：blog.csdn.net/qq_39181839/article/details/109478094

import random

def func(nums):
    if len(nums) <= 1:
        return nums
    
    ref = random.choice(nums)
    left,mid,right = [],[],[]
    for num in nums:
        if num < ref:
            left.append(num)
        elif num > ref:
            right.append(num)
        else:
            mid.append(num)
    return func(left) + mid + func(right)

nums = [random.randint(-10,10) for _ in range(random.randint(3,10))]
print(f"排序前:{nums}")
print(f"排序后:{func(nums)}")

非比较排序算法

计数排序

计数排序是一种非比较排序算法，通过统计数组中每个元素出现的次数，并根据计数信息直接确定每个元素的位置，从而实现高效排序，适用于数据范围较小的整数排序。

文章：算法系列十一：十大经典排序算法之——计数排序-CSDN博客

import random

def counting_sort(nums):
    if not nums:
        return []
    min_val = min(nums)
    max_val = max(nums)
    offset = max_val - min_val + 1
    counts = [0] * offset
    for num in nums:
        counts[num - min_val] += 1
    return [min_val + i for i in range(offset) for _ in range(counts[i])]

nums = [random.randint(-10, 10) for _ in range(random.randint(3, 10))]
print(f"排序前: {nums}")
print(f"排序后: {counting_sort(nums)}")