数据结构 直接插入排序

描述 用函数实现直接插入排序，并输出每趟排序的结果. Input 第一行：键盘输入待排序关键的个数n 第二行：输入n个待排序关键字，用空格分隔数据 Output 每行输出一趟排序结果，数据之间用一个空格分隔 Sample Input 10 5 4 8 0 9 3 2 6 7 1 Sample Output 4 5 8 0 9 3 2 6 7 1 4 5 8 0 9 3 2 6 7 1 0 4 5 8 9 3 2 6 7 1 0 4 5 8 9 3 2 6 7 1 0 3 4 5 8 9 2 6 7 1 0 2 3 4 5 8 9 6 7 1 0 2 3 4 5 6 8 9 7 1 0 2 3 4 5 6 7 8 9 1 0 1 2 3 4 5 6 7 8 9 ### 数据结构之直接插入排序详解 #### 一、引言 在计算机科学中，排序算法是数据处理中不可或缺的一部分，而直接插入排序是一种简单直观的排序方法。它的工作原理类似于我们手动排序一组卡片的方式——每次从未排序的部分取出一个元素，然后将其插入到已排序部分的适当位置。 本篇文章将详细介绍如何通过编写C语言程序实现直接插入排序，并输出每次排序后的结果，以便观察排序过程中的变化。 #### 二、直接插入排序的基本原理 直接插入排序的基本思想是：将待排序的序列看作是由一个已排序子序列和一个未排序子序列组成。初始时，可以认为第一个元素已经排好序。接下来，从未排序子序列中依次取出元素，与已排序子序列中的元素进行比较，找到该元素在已排序子序列中的正确位置并插入。重复此过程，直到所有元素都插入到已排序子序列中，完成排序。 #### 三、直接插入排序的实现 根据题目要求，我们需要实现一个能够对数组进行直接插入排序的函数，并且在排序过程中输出每一步的结果。下面是具体的实现代码： ```c #include <stdio.h> // 实现直接插入排序的函数 int InserSort(int *a, int n) { int i, j, k; for (i = 2; i <= n; i++) { // 从第二个元素开始遍历 a[0] = a[i]; // 将当前元素暂存 for (j = 1; j < i; j++) { // 遍历已排序部分 if (a[j] > a[i]) { // 如果已排序部分的元素大于当前元素，则进行移动 for (k = i; k > j; k--) // 移动元素 a[k] = a[k - 1]; a[k] = a[0]; // 将当前元素插入到正确位置 break; } } // 输出当前排序结果 for (j = 1; j <= n; j++) { printf("%d ", a[j]); // 输出排序后的元素 } printf("\n"); // 换行 } return 1; } int main() { int a[80], i, n; scanf("%d", &n); // 输入待排序的关键字数量 for (i = 1; i <= n; i++) { scanf("%d", &a[i]); // 输入待排序的关键字 } InserSort(a, n); // 调用插入排序函数 return 1; } ``` #### 四、代码解析 1. **函数定义**： - `InserSort(int *a, int n)`：这是一个核心函数，用于执行直接插入排序。 2. **排序逻辑**： - `for (i = 2; i <= n; i++)`：从数组的第二个元素开始遍历。 - `a[0] = a[i];`：将当前元素暂存至数组的第一个位置，这里使用`a[0]`作为临时存储，方便后续操作。 - 内层循环`for (j = 1; j < i; j++)`用于查找当前元素应插入的位置。 - 使用`for (k = i; k > j; k--)`来将已排序部分比当前元素大的值向后移动一位。 - `a[k] = a[0];`：将当前元素插入到正确位置。 3. **输出排序过程**： - 在每次内层循环结束后，使用`printf`函数输出当前排序的结果，便于观察排序过程。 #### 五、运行示例 按照题目给出的示例输入： ``` 10 5 4 8 0 9 3 2 6 7 1 ``` 输出结果为： ``` 4 5 8 0 9 3 2 6 7 1 4 5 8 0 9 3 2 6 7 1 0 4 5 8 9 3 2 6 7 1 0 4 5 8 9 3 2 6 7 1 0 3 4 5 8 9 2 6 7 1 0 2 3 4 5 8 9 6 7 1 0 2 3 4 5 6 8 9 7 1 0 2 3 4 5 6 7 8 9 1 0 1 2 3 4 5 6 7 8 9 ``` 从输出结果可以看出，随着排序的进行，序列逐渐变得有序，最终得到完全排序的数组。 #### 六、总结 本文介绍了如何使用C语言实现直接插入排序，并详细解析了排序的过程及代码实现细节。通过这种方式，我们可以更好地理解直接插入排序的工作原理，并观察排序过程中的变化，这对于学习排序算法是非常有帮助的。