探索排序算法的奥秘（上）：冒泡排序、选择排序、插入排序

本文详细介绍三种经典的排序算法：冒泡排序、选择排序和插入排序。我们将从算法思想、原理、代码实现（C语言、Python、Java）、性能分析以及使用场景等方面进行深入探讨。

2301_80284862

997人浏览 · 2025-04-27 10:07:51

2301_80284862 · 2025-04-27 10:07:51 发布

在计算机科学中，排序算法是数据处理的基础工具之一。通过对数据进行有序排列，可以极大地提高数据检索和处理的效率。本文将详细介绍三种经典的排序算法：冒泡排序、选择排序和插入排序。我们将从算法思想、原理、代码实现（C语言、Python、Java）、性能分析以及使用场景等方面进行深入探讨。这些排序算法虽然在实际应用中可能不如一些高级排序算法（如快速排序、归并排序）高效，但它们是理解排序算法原理的重要基础。

一、冒泡排序

（一）算法思想

冒泡排序是一种简单的排序算法，它通过重复遍历待排序的数组，比较每对相邻元素，如果它们的顺序错误就把它们交换过来。遍历数组的工作是重复进行的，直到没有再需要交换的元素为止，这意味着数组已经排序完成。冒泡排序的名字由来是因为较小的元素会像气泡一样“浮”到数组的顶部。

（二）算法原理

比较相邻的元素。如果第一个比第二个大（升序），就交换它们两个。
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

（三）代码实现

C语言实现

#include <stdio.h>

void bubbleSort(int arr[], int n) {
    int i, j, temp;
    for (i = 0; i < n - 1; i++) { // 外层循环控制排序的轮数
        for (j = 0; j < n - 1 - i; j++) { // 内层循环控制每轮的比较次数
            if (arr[j] > arr[j + 1]) { // 相邻元素比较
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp; // 交换元素
            }
        }
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

Python实现

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):  # 外层循环控制排序的轮数
        for j in range(n - 1 - i):  # 内层循环控制每轮的比较次数
            if arr[j] > arr[j + 1]:  # 相邻元素比较
                arr[j], arr[j + 1] = arr[j + 1], arr[j]  # 交换元素

arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("Sorted array is:", arr)

Java实现

public class BubbleSort {
    public static 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]) { // 相邻元素比较
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp; // 交换元素
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(arr);
        System.out.println("Sorted array:");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

（四）性能分析

时间复杂度：在最坏的情况下（数组完全逆序），冒泡排序需要进行n*(n-1)/2次比较和交换操作，因此时间复杂度为O(n^2)。在最好的情况下（数组已经有序），时间复杂度为O(n)。
空间复杂度：冒泡排序只需要一个临时变量用于交换，因此空间复杂度为O(1)。
稳定性：冒泡排序是一种稳定的排序算法，因为相等元素的相对位置不会改变。

（五）使用场景

冒泡排序适用于数据量较小的场景，尤其是在数据已经接近有序的情况下，冒泡排序的性能会更好。由于其简单易懂，冒泡排序也常用于教学目的。

二、选择排序

（一）算法思想

选择排序是一种简单直观的排序算法。它的工作原理是：首先在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中寻找最小（或最大）元素，然后放到已排序序列的末尾。重复这个过程，直到所有元素均排序完毕。

（二）算法原理

遍历整个数组，找到最小（或最大）的元素。
将找到的最小（或最大）元素与数组的第一个元素交换。
重复上述步骤，但每次从剩下的未排序部分中选择最小（或最大）元素，然后将其放到已排序部分的末尾。
重复这个过程，直到整个数组排序完成。

（三）代码实现

C语言实现

#include <stdio.h>

void selectionSort(int arr[], int n) {
    int i, j, min_idx, temp;
    for (i = 0; i < n - 1; i++) { // 外层循环控制排序的轮数
        min_idx = i; // 假设当前位置是最小值的位置
        for (j = i + 1; j < n; j++) { // 内层循环寻找最小值
            if (arr[j] < arr[min_idx]) {
                min_idx = j; // 更新最小值的位置
            }
        }
        if (min_idx != i) { // 如果找到的最小值不是当前位置
            temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp; // 交换元素
        }
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, n);
    printf("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

Python实现

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):  # 外层循环控制排序的轮数
        min_idx = i  # 假设当前位置是最小值的位置
        for j in range(i + 1, n):  # 内层循环寻找最小值
            if arr[j] < arr[min_idx]:
                min_idx = j  # 更新最小值的位置
        if min_idx != i:  # 如果找到的最小值不是当前位置
            arr[i], arr[min_idx] = arr[min_idx], arr[i]  # 交换元素

arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("Sorted array:", arr)

Java实现

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) { // 外层循环控制排序的轮数
            int min_idx = i; // 假设当前位置是最小值的位置
            for (int j = i + 1; j < n; j++) { // 内层循环寻找最小值
                if (arr[j] < arr[min_idx]) {
                    min_idx = j; // 更新最小值的位置
                }
            }
            if (min_idx != i) { // 如果找到的最小值不是当前位置
                int temp = arr[min_idx];
                arr[min_idx] = arr[i];
                arr[i] = temp; // 交换元素
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println("Sorted array:");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

（四）性能分析

时间复杂度：选择排序的时间复杂度为O(n^2)，无论数组是否已经有序，都需要进行n*(n-1)/2次比较，但只有n-1次交换操作。
空间复杂度：选择排序只需要一个临时变量用于交换，因此空间复杂度为O(1)。
稳定性：选择排序是一种不稳定的排序算法，因为相等元素的相对位置可能会改变。

（五）使用场景

选择排序适用于数据量较小的场景，尤其是在内存空间有限的情况下，因为它的空间复杂度较低。选择排序也常用于教学目的，帮助初学者理解排序算法的基本原理。

三、插入排序

（一）算法思想

插入排序是一种简单直观的排序算法。它的工作原理是：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上通常使用in-place排序（即只需用到O(1)的额外空间的排序）。

（二）算法原理

从第一个元素开始，该元素可以认为已经被排序。
取出下一个元素，在已经排序的元素序列中从后向前扫描。
如果该元素（已排序）大于新元素，将该元素移到下一位置。
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
将新元素插入到该位置后。
重复步骤2~5。

（三）代码实现

C语言实现

#include <stdio.h>

void insertionSort(int arr[], int n) {
    int i, j, key;
    for (i = 1; i < n; i++) { // 外层循环控制排序的轮数
        key = arr[i]; // 取出未排序部分的第一个元素
        j = i - 1;
        while (j >= 0 && arr[j] > key) { // 在已排序部分从后向前扫描
            arr[j + 1] = arr[j]; // 如果当前元素大于key，将当前元素向后移动
            j = j - 1;
        }
        arr[j + 1] = key; // 将key插入到正确的位置
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    printf("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

Python实现

def insertion_sort(arr):
    for i in range(1, len(arr)):  # 外层循环控制排序的轮数
        key = arr[i]  # 取出未排序部分的第一个元素
        j = i - 1
        while j >= 0 and arr[j] > key:  # 在已排序部分从后向前扫描
            arr[j + 1] = arr[j]  # 如果当前元素大于key，将当前元素向后移动
            j -= 1
        arr[j + 1] = key  # 将key插入到正确的位置

arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print("Sorted array:", arr)

Java实现

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) { // 外层循环控制排序的轮数
            int key = arr[i]; // 取出未排序部分的第一个元素
            int j = i - 1;
            while (j >= 0 && arr[j] > key) { // 在已排序部分从后向前扫描
                arr[j + 1] = arr[j]; // 如果当前元素大于key，将当前元素向后移动
                j--;
            }
            arr[j + 1] = key; // 将key插入到正确的位置
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        insertionSort(arr);
        System.out.println("Sorted array:");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

（四）性能分析

时间复杂度：在最坏的情况下（数组完全逆序），插入排序需要进行n*(n-1)/2次比较和移动操作，因此时间复杂度为O(n^2)。在最好的情况下（数组已经有序），时间复杂度为O(n)。
空间复杂度：插入排序只需要一个临时变量用于存储当前元素，因此空间复杂度为O(1)。
稳定性：插入排序是一种稳定的排序算法，因为相等元素的相对位置不会改变。

（五）使用场景

插入排序适用于数据量较小的场景，尤其是在数据已经接近有序的情况下，插入排序的性能会更好。插入排序也常用于教学目的，帮助初学者理解排序算法的基本原理。此外，插入排序在某些特定的场景下（如在线排序）也具有一定的优势。

四、总结

排序算法	算法思想	时间复杂度	空间复杂度	稳定性	使用场景
冒泡排序	通过相邻元素的比较和交换，将最大（或最小）元素“浮”到数组的顶部	`O(n^2)`	`O(1)`	稳定	数据量较小，数据接近有序
选择排序	每轮选择最小（或最大）元素放到已排序部分的末尾	`O(n^2)`	`O(1)`	不稳定	数据量较小，内存空间有限
插入排序	通过构建有序序列，将未排序部分的元素插入到已排序部分的正确位置	`O(n^2)`	`O(1)`	稳定	数据量较小，数据接近有序

这三种排序算法虽然在实际应用中可能不如一些高级排序算法（如快速排序、归并排序）高效，但它们是理解排序算法原理的重要基础。感谢您的阅读，欢迎大家一起探讨与学习算法知识。在后续的博客中，我们将继续探讨更多高效的排序算法，如快速排序、归并排序等，敬请期待！！！

天启AI社区

GitCode 天启AI是一款由 GitCode 团队打造的智能助手，基于先进的LLM（大语言模型）与多智能体 Agent 技术构建，致力于为用户提供高效、智能、多模态的创作与开发支持。它不仅支持自然语言对话，还具备处理文件、生成 PPT、撰写分析报告、开发 Web 应用等多项能力，真正做到“一句话，让 Al帮你完成复杂任务”。

更多推荐