C语言直接插入排序与直接选择排序原理解析与实现

晚来风

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

原创

本文深入解析C语言中常用的两种基础排序算法：直接插入排序与直接选择排序。通过拆解基本思路、提供完整可运行的C语言代码示例，帮助开发者理解这两种时间复杂度均为 O(n²) 的算法原理及其具体实现细节。

直接插入排序

直接插入排序（Straight Insertion Sort）是一种简单直观的排序方法。其核心思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。

基本原理

初始化有序区：假设数组的第一个元素 a[0] 是有序的，其余元素 a[1] ~ a[n-1] 是无序的。
逐个插入：从第二个元素 a[1] 开始，将其插入到前面已排好的有序子序列中。比较过程中，如果当前元素小于前一个元素，则交换位置或后移，直到找到合适的插入点。
循环结束：重复上述过程，直到处理完最后一个元素 a[n-1]，整个数组即变为有序。

C语言代码实现

以下代码展示了直接插入排序的具体实现。包含核心的 insertsort 函数用于执行排序，以及辅助的 swap 函数用于元素交换。

#include <stdio.h>
#define N 5 

void insertsort(int a[], int n); 
void swap(int *x, int *y); 

// 直接插入排序主函数
void insertsort(int a[], int n){ 
  int i, j;
  // 从第二个元素开始遍历
  for(i=1; i<n; i++){ 
    // 当当前元素小于前一个元素时，向前扫描并交换
    for(j=i; j>0 && a[j]<a[j-1]; j--){ 
      swap(&a[j], &a[j-1]); 
    }   
  }
}

// 交换两个整数的值
void swap(int *x, int *y){ 
  int temp = *x; 
  *x = *y; 
  *y = temp;
} 

int main(void){ 
  int a[N] = {2, 5, 3, 1, 8}; 
  insertsort(a, N); 
  
  // 输出排序后的结果
  int i;
  for(i=0; i<N; i++) 
    printf("%d ", a[i]); 
  return 0; 
}

关键点说明：

swap 函数使用指针传递，确保修改的是原始数组中的值。
内部循环 j-- 实现了从当前位置向前查找插入位置的过程。

直接选择排序

直接选择排序（Straight Selection Sort）也是一种简单的排序算法。它的基本策略是每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子序列的最后，直到全部记录排序完毕。

基本原理

寻找最小值：从第1个位置（索引 0）开始，在剩余的无序部分中找到最小元素的下标。
交换位置：将找到的最小元素与当前位置的元素交换。
缩小范围：接下来从第2个位置（索引 1）开始，重复上述步骤，直到倒数第二个元素处理完毕。

C语言代码实现

以下是直接选择排序的C语言实现。核心在于 selectsort 函数中通过嵌套循环查找最小值索引并进行交换。

#include <stdio.h>
#define N 5 

void selectsort(int a[], int n); 
void swap(int *x, int *y); 

// 直接选择排序主函数
void selectsort(int a[], int n){ 
  int i, j;
  // 遍历到倒数第二个元素即可
  for(i=0; i<n - 1; i++){ 
    int min = i; // 假设当前i是最小值的索引
    // 在未排序部分查找真正的最小值
    for(j=i+1; j<n; j++){ 
      if(a[j] < a[min]){ 
        min = j; 
      }
    }
    // 如果找到的最小值不在当前i位置，则交换
    if(min != i) {
        swap(&a[i], &a[min]); 
    }
  }
}

// 交换两个整数的值
void swap(int *x, int *y){ 
  int temp = *x; 
  *x = *y; 
  *y = temp;
} 

int main(void){ 
  int a[N] = {2, 5, 3, 1, 8}; 
  selectsort(a, N); 
  
  // 输出排序后的结果
  int i;
  for(i=0; i<N; i++) 
    printf("%d ", a[i]); 
  return 0; 
}

优化提示：