首页用c语言写一个折半插入排序代码

用c语言写一个折半插入排序代码

时间: 2025-06-29 12:14:47 浏览: 3

当然可以，折半插入排序是一种改进版的插入排序算法，它通过将数组分为两部分来进行操作，提高了效率。以下是用C语言实现折半插入排序的一个简单版本： ```c #include <stdio.h> void insertion_sort(int arr[], int n) { int i, j, key, mid; for (i = 1; i < n;){ // 找到未排序部分的中间元素 mid = i / 2; key = arr[i]; // 如果中间元素比当前元素大，向左移动中间元素 while (mid > 0 && arr[mid] > key) { arr[mid] = arr[mid - 1]; mid--; } // 将找到合适位置的key插入到已排序部分 arr[mid] = key; // 更新i的位置以便处理剩余未排序的部分 i = mid + 1; } } // 测试函数 int main() { int arr[] = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6}; int n = sizeof(arr) / sizeof(arr[0]); printf("Original array:\n"); for (int i = 0; i < n; i++) printf("%d ", arr[i]); insertion_sort(arr, n); printf("\nSorted array using Half Insertion Sort:\n"); for (int i = 0; i < n; i++) printf("%d ", arr[i]); return 0; } ``` 这个程序首先定义了一个`insertion_sort`函数，然后在`main`函数里创建一个测试数组并调用该函数对数组进行排序。运行后，可以看到输入数组已经被折半插入排序算法正确地排列。

阅读全文