【排序 - 插入排序 和 希尔排序】

插入排序（Insertion Sort）是一种简单直观的排序算法，它的工作原理是逐步构建有序序列。在排序过程中，它将未排序的元素逐个插入到已排序的部分中，从而在每次插入时扩展已排序序列的长度。

原理介绍

插入排序的基本思想是将数组分为两部分：已排序部分和未排序部分。初始时，已排序部分只包含数组的第一个元素，而未排序部分包含剩余的元素。排序过程中，每次从未排序部分取出一个元素，将它插入到已排序部分的适当位置，使得插入后依然保持已排序部分有序。

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

下面是用C语言实现插入排序的示例代码：

#include <stdio.h> // 函数：实现插入排序 void insertionSort(int arr[], int n) { int i, key, j; for (i = 1; i < n; i++) { key = arr[i]; // 当前需要插入排序的元素 j = i - 1; // 将比key大的元素都向右移动一个位置 while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; // 将key插入到正确的位置 } } // 函数：打印数组元素 void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } // 主函数：测试插入排序的实现 int main() { int arr[] = {12, 11, 13, 5, 6}; int n = sizeof(arr) / sizeof(arr[0]); printf("原始数组: \n"); printArray(arr, n); insertionSort(arr, n); printf("排序后的数组: \n"); printArray(arr, n); return 0; } 12345678910111213141516171819202122232425262728293031323334353637383940 代码解析 insertionSort函数：实现插入排序的主要逻辑。在每次迭代中，将当前需要排序的元素（key）插入到已排序部分的适当位置，通过不断向前比较并移动元素实现插入。printArray函数：用于打印数组元素，方便查看排序结果。main函数：测试插入排序的实现，打印排序前和排序后的数组。 插入排序是一种简单而有效的算法，但对于大规模数据或者需要更快速的排序算法来说，希尔排序（Shell Sort）是一种更优秀的选择。本文将详细介绍插入排序和希尔排序的原理，并提供用C语言实现的代码示例。 希尔排序简介

希尔排序是基于插入排序的一种改进算法，也称为缩小增量排序。它通过将待排序数组分成若干个子序列，对每个子序列进行插入排序，逐渐缩小子序列的长度，最终整体使用插入排序完成排序。

希尔排序算法步骤 选择一个增量序列，按增量序列对原始数组进行分组。对各个分组进行插入排序。逐步缩小增量，重复上述步骤，直至增量为1。最后对整个数组进行插入排序。 希尔排序的C语言实现 #include <stdio.h> void shellSort(int arr[], int n) { int gap, i, j, temp; for (gap = n / 2; gap > 0; gap /= 2) { for (i = gap; i < n; i++) { temp = arr[i]; for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) { arr[j] = arr[j - gap]; } arr[j] = temp; } } } void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { int arr[] = {12, 11, 13, 5, 6}; int n = sizeof(arr) / sizeof(arr[0]); printf("原始数组: \n"); printArray(arr, n); shellSort(arr, n); printf("排序后的数组: \n"); printArray(arr, n); return 0; } 1234567891011121314151617181920212223242526272829303132333435 总结

插入排序和希尔排序都是重要的排序算法，它们虽然在实现上有所不同，但都是基于不断将元素插入已排序序列中的思想。希尔排序通过引入增量的方式优化了插入排序的性能，尤其适合对中等大小的数据集进行排序。通过本文的介绍和代码示例，读者可以更深入地理解这两种排序算法的工作原理和实现方法。