排序算法冒泡与选择

算法排序

算法

发布日期: 2024-09-11

作者: 小乐

文章字数: 769

阅读时长: 3 分

阅读次数:

一、排序算法概述

1.1 评价维度

时间复杂度：最好、最坏、平均
空间复杂度：原地排序 vs 需要额外空间
稳定性：相等元素排序后相对位置是否改变
比较次数、交换次数

1.2 分类

类型	算法
( O(n^2) )	冒泡、选择、插入
( O(n \log n) )	快速、归并、堆
( O(n) )	计数、基数、桶

二、冒泡排序

2.1 核心思想

重复遍历数组，相邻元素两两比较，大的往后”冒泡”。

2.2 基础实现

public void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
            }
        }
    }
}

2.3 优化版 - 提前终止

public void bubbleSortOptimized(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
                swapped = true;
            }
        }
        if (!swapped) break;  // 无交换说明已排序
    }
}

2.4 进一步优化 - 记录最后交换位置

public void bubbleSortAdvanced(int[] arr) {
    int n = arr.length;
    int sortedBoundary = n - 1;
    
    while (sortedBoundary > 0) {
        int lastSwap = 0;
        for (int j = 0; j < sortedBoundary; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
                lastSwap = j;
            }
        }
        sortedBoundary = lastSwap;
    }
}

2.5 复杂度分析

情况	时间复杂度	说明
最好	( O(n) )	已排序，优化版一次遍历
最坏	( O(n^2) )	逆序
平均	( O(n^2) )
空间	( O(1) )	原地排序
稳定性	稳定	相等不交换

三、选择排序

3.1 核心思想

每轮选择剩余元素中最小（或最大）的，放到已排序序列末尾。

3.2 实现

public void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        if (minIdx != i) {
            swap(arr, i, minIdx);
        }
    }
}

3.3 复杂度分析

情况	时间复杂度	说明
最好	( O(n^2) )	仍需比较
最坏	( O(n^2) )
平均	( O(n^2) )
空间	( O(1) )	原地排序
稳定性	不稳定	交换可能改变相对位置

不稳定性示例：

[5a, 8, 5b, 2] → 选择2和5a交换
[2, 8, 5b, 5a] → 5a和5b相对位置改变

3.4 交换次数优势

选择排序最多 ( n - 1 ) 次交换，适合交换成本高的场景（如链表）。

四、两种算法对比

特性	冒泡排序	选择排序
最好时间	( O(n) )	( O(n^2) )
最坏时间	( O(n^2) )	( O(n^2) )
平均时间	( O(n^2) )	( O(n^2) )
空间	( O(1) )	( O(1) )
稳定性	稳定	不稳定
交换次数	多	少
适用	小数据、基本有序	交换成本高