首页折半插入排序算法 c 代码

折半插入排序算法 c 代码

时间: 2024-11-18 21:18:55 浏览: 103

折半插入排序（Binary Insertion Sort）是一种优化版的插入排序，它通过将数组分为两部分，一部分是已排序的部分，另一部分是未排序的部分，并针对未排序部分采用二分查找的方式找到合适的位置插入元素，以此提高效率。以下是C语言的一个简单实现： ```c #include <stdio.h> // 二分查找函数，返回值为插入元素的索引 int binarySearch(int arr[], int left, int right, int key) { while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == key) return mid; // 找到目标位置 else if (arr[mid] < key) left = mid + 1; // 向右半部分查找 else right = mid - 1; // 向左半部分查找 } return left; // 如果没找到，返回插入位置 } // 折半插入排序函数 void binaryInsertionSort(int arr[], int n) { for (int i = 1; i < n; i++) { int key = arr[i]; int index = binarySearch(arr, 0, i - 1, key); memmove(&arr[index + 1], &arr[index], (i - index) * sizeof(int)); // 移动元素 arr[index] = key; // 插入元素 } } // 测试函数 int main() { int arr[] = {9, 5, 7, 3, 6, 8}; int n = sizeof(arr) / sizeof(arr[0]); binaryInsertionSort(arr, n); printf("Sorted array: \n"); for (int i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n"); return 0; } ```

阅读全文