C语言实现选择排序、插入排序与冒泡排序详解

Ruby

发布时间：2026-10-13| 6人浏览过

原创

选择排序、直接插入排序和冒泡排序是C语言学习中不可绕开的三个基础排序算法。它们的时间复杂度均为O(n^2)，但核心逻辑与稳定性各异。本文将通过原理拆解与标准代码示例，展示如何在C语言中实现这三种算法。

选择排序 (Selection Sort)

选择排序是一种简单直观的排序算法。其核心思想是每一轮从未排序的序列中找到最小（或最大）的元素，将其放置到已排序序列的末尾。该算法在原地进行交换操作，不占用额外内存空间。

算法特性：

时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：不稳定

第1步：理解选择排序逻辑

外层循环控制已排序序列的边界，内层循环遍历剩余元素寻找最小值的索引。找到后若位置不正确，则执行交换操作。

/*
 * @brief  selection sort
 */
void
selection_sort(int a[], int n)
{
  int i, j, min, tmp;
  
  for (i = 0; i < n - 1; ++i) {
    min = i;
    for (j = i+1; j < n; ++j) {
      if (a[j] < a[min]) {
        min = j;
      }
    }
    if (min != i) {
      tmp = a[min];
      a[min] = a[i];
      a[i] = tmp;  
    }        
  }
}

直接插入排序 (Insertion Sort)

直接插入排序类似于整理扑克牌的过程。它将数组分为“已排序”和“未排序”两部分，逐个将未排序元素插入到已排序部分的正确位置上。当待插入元素比已排序部分小，就依次后移较大的元素。

算法特性：

时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：稳定

第2步：构建插入排序循环

从第二个元素开始遍历，当前元素暂存为num。将num与前面的已排序元素比较，大于num的元素后移一位，直到找到合适位置后放入num。

/* @brief insetion sort
 * insert the new element to the sorted subarray
 */
void
insertion_sort(int a[], int n)
{
  int i, j, num;

  for (i = 1; i < n; ++i) {
    num = a[i];
    for (j = i - 1; j >= 0 && a[j] > num; --j)
      a[j+1] = a[j];
    a[j+1] = num;
  }
}

冒泡排序 (Bubble Sort)

冒泡排序通过重复遍历数组来工作。它比较相邻的两个元素，如果顺序错误就把它们交换过来。重复地进行直到没有再需要交换，也就是说该数列已经排序完成。较小的值会像气泡一样逐渐浮向顶端（数组前端）。

算法特性：

时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：稳定

第3步：完成冒泡交换逻辑

外层循环控制遍历次数，内层循环从数组尾部向前比对。如果发现前一个元素大于后一个元素，便进行位置互换。一次完整遍历可将最小的元素置换到首位。

/* @brief  bubble sort
 * move the smallest element to the front in every single loop
 */
void
bubble_sort(int a[], int n)
{
  int i, j, tmp;

  for (i = 0; i < n; ++i) {
    for (j = n - 1; j > i; --j) {
      if (a[j] < a[j-1]) {
        tmp = a[j];
        a[j] = a[j-1];
        a[j-1] = tmp;
      }
    }
  }
}