【基础算法】（一）基础排序（冒泡、选择、插入）

冒泡排序 (Bubble Sort)

算法原理

冒泡排序是一种简单的比较排序算法。它的基本思路是通过不断比较相邻元素并交换它们的位置，使得较大的元素逐渐"冒泡"到数组的末尾。

代码实现

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

算法分析

• 时间复杂度：
  • 最好情况(已排序)：O(n)
  • 最坏情况(逆序)：O(n²)
  • 平均情况：O(n²)
• 空间复杂度：O(1)，原地排序
• 稳定性：稳定排序（相等元素不会交换位置）

选择排序 (Selection Sort)

算法原理

选择排序每次遍历都会找到当前未排序部分的最小元素，并将其放到已排序部分的末尾。

代码实现

def select_sort(nums):
    n = len(nums)
    for i in range(n):
        min_index = i
        for j in range(i+1,n):
            if nums[j] < nums[min_index]:
                min_index = j
      
        nums[i], nums[min_index] = nums[min_index], nums[i]

算法分析

• 时间复杂度：无论最好、最坏还是平均情况，都是O(n²)
• 空间复杂度：O(1)，原地排序
• 稳定性：不稳定排序（交换可能改变相等元素的相对位置）

特点

• 交换次数最少（最多n-1次交换）
• 不适用于大规模数据集

插入排序 (Insertion Sort)

算法原理

插入排序通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

代码实现

def insert_sort(nums):
    n = len(nums)
    for i in range(n-1):
        j = i+1
        while nums[j] < nums[j-1] and j>0:
            nums[j], nums[j-1] = nums[j-1], nums[j]
            j -= 1

算法分析

• 时间复杂度：
  • 最好情况(已排序)：O(n)
  • 最坏情况(逆序)：O(n²)
  • 平均情况：O(n²)
• 空间复杂度：O(1)，原地排序
• 稳定性：稳定排序