当前位置：首页 > article >正文

数据结构：用C语言实现插入排序

article 2025/3/22 1:10:05

概要

整体架构流程

技术名词解释

代码实现

1、直接插入排序

2、折半插入排序

3、希尔排序

小结

概要

插入排序是一种简单直观的排序算法，适用于小规模数据或部分有序的数据集。它的工作原理类似于整理扑克牌，通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

整体架构流程

插入排序的基本流程如下：

初始化：从第二个元素开始，假设第一个元素已经是有序的。
比较与插入：将当前元素与已排序部分的元素从后向前比较，找到合适的位置插入。
重复：重复上述步骤，直到所有元素都被排序。

技术名词解释

直接插入排序：最基本的插入排序，逐个比较并插入。
折半插入排序：在查找插入位置时使用二分查找，减少比较次数。
希尔排序：通过分组进行插入排序，逐步缩小分组间隔，最终完成排序。

代码实现

这里有三种实现方式，分别为直接插入排序、折半插入排序和希尔排序，其中main函数定义了一个测试数组，调用插入排序函数并输出结果。代码的每一步操作都有详细的注释。

1、直接插入排序

#include <stdio.h>
#include <stdlib.h>

typedef struct SqList {
	int* arr;
	int length;
} SqList;

// 直接插入排序
void insertSort(SqList list) {
    // 两个计数器
	int i = 0;
	int j = 0;
	
	for (i = 2; i <= list.length; i++) {
        // 检查是否需要排序
		if (list.arr[i] < list.arr[i - 1]) {
			list.arr[0] = list.arr[i]; // 复制为哨兵

			for (j = i - 1; list.arr[j] > list.arr[0]; j--) {
				list.arr[j + 1] = list.arr[j]; // 后移元素
			}
			list.arr[j + 1] = list.arr[0]; // 插入到正确位置
		}
	}
}

int main() {
	// 初始化数据
	SqList list;
	list.length = 10;
	list.arr = calloc(list.length + 1, sizeof(int));

	// 输入
	int i = 0;
	for (i = 1; i <= list.length; i++) {
		scanf("%d", list.arr + i);
	}

	insertSort(list); // 排序

	// 输出
	for (i = 1; i <= list.length; i++) {
		printf("%d ", list.arr[i]);
	}

	return 0;
}

2、折半插入排序

#include <stdio.h>
#include <stdlib.h>

typedef struct SqList {
	int* arr;
	int length;
} SqList;

// 折半插入排序
void insertSort(SqList list) {
	// 两个计数器
	int i = 0;
	int j = 0;

	for (i = 2; i <= list.length; i++) {
		// 检验是否需要排序
		if (list.arr[i - 1] > list.arr[i]) {
			list.arr[0] = list.arr[i]; // 复制为哨兵

			int left = 1;
			int right = list.length;
			int mid = (right - left) / 2 + left;
			
			// 寻找要插入的位置
			while (left <= right) {
				mid = (right - left) / 2 + left;
				
				if (list.arr[0] > list.arr[mid]) {
					left = mid + 1;
				}
				else
				{
					right = mid - 1;
				}
			}

			// 插入操作
			for (j = i - 1; j > right + 1; j--) {
				list.arr[j + 1] = list.arr[j]; // 后移元素
			}
			list.arr[right + 1] = list.arr[0]; // 插入到正确位置
		}
	}
}

int main() {
	// 初始化数据
	SqList list;
	list.length = 10;
	list.arr = calloc(list.length + 1, sizeof(int));

	// 输入
	int i = 0;
	for (i = 1; i <= list.length; i++) {
		scanf("%d", list.arr + i);
	}

	insertSort(list); // 排序

	// 输出
	for (i = 1; i <= list.length; i++) {
		printf("%d ", list.arr[i]);
	}

	return 0;
}

3、希尔排序

#include <stdio.h>
#include <stdlib.h>

typedef struct SqList {
	int* arr;
	int length;
} SqList;

// 每一趟的操作
void shellInsert(SqList list, int dk) {
	// 两个计数器
	int i = 0;
	int j = 0;

	for (i = dk + 1; i <= list.length; i++) {
		// 判断是否需要排序
		if (list.arr[i] < list.arr[i - dk]) {
			list.arr[0] = list.arr[i]; // 复制为哨兵

			// 开始排序
			for (j = i - dk; (j > 0) && (list.arr[j] > list.arr[0]); j -= dk) {
				list.arr[j + dk] = list.arr[j];
			}
			list.arr[j + dk] = list.arr[0]; // 插入到正确位置
		}
	}
}

void shellSort(SqList list, int dlta[], int t) {
	// 按增量序列 dlta 对顺序表 list 作希尔排序
	int i = 0;
	for (i = 0; i < t; i++) {
		shellInsert(list, dlta[i]); // 一趟增量为 dlta[i] 的插入排序
	}
}

int main() {
	// 初始化数据
	SqList list;
	list.length = 10;
	list.arr = calloc(list.length + 1, sizeof(int));
	int dlta[] = { 5, 3, 1 }; // 增量序列
	int t = sizeof(dlta) / sizeof(dlta[0]); // 序列长度

	// 输入
	int i = 0;
	for (i = 1; i <= list.length; i++) {
		scanf("%d", list.arr + i);
	}

	shellSort(list, dlta, t); // 排序

	// 输出
	for (i = 1; i <= list.length; i++) {
		printf("%d ", list.arr[i]);
	}

	return 0;
}