C语言二分法插入排序
时间: 2023-11-22 20:48:06 浏览: 113
二分法插入排序是一种高效的排序算法,它结合了二分查找和插入排序的优点。下面是C语言实现的二分法插入排序过程:
```c
void binaryInsertionSort(int arr[], int n) {
int i, loc, j, k, selected;
for (i = 1; i < n; ++i) {
j = i - 1;
selected = arr[i];
loc = binarySearch(arr, selected, 0, j);
while (j >= loc) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = selected;
}
}
int binarySearch(int arr[], int item, int low, int high) {
if (high <= low)
return (item > arr[low]) ? (low + 1) : low;
int mid = (low + high) / 2;
if (item == arr[mid])
return mid + 1;
if (item > arr[mid])
return binarySearch(arr, item, mid + 1, high);
return binarySearch(arr, item, low, mid - 1);
}
```
上述代码中,`binaryInsertionSort`函数实现了二分法插入排序,`binarySearch`函数实现了二分查找。具体过程如下:
1. 对于未排序的元素,从第二个元素开始,将其插入到已排序的元素中。
2. 使用二分查找算法找到插入位置。
3. 将插入位置之后的元素全部向右移动一个位置。
4. 将待排序元素插入到正确的位置。
阅读全文