C语言二分排序的sort函数
时间: 2023-11-23 10:57:24 浏览: 60
C语言中的二分排序也被称为二分查找排序,可以通过以下sort函数实现:
```
void binarySort(int arr[], int n) {
int i, j;
int left, right, mid, temp;
for(i = 1; i < n; i++) {
left = 0;
right = i-1;
temp = arr[i];
while(left <= right) {
mid = (left + right) / 2;
if(arr[mid] > temp) {
right = mid - 1;
} else {
left = mid + 1;
}
}
for(j = i-1; j >= left; j--) {
arr[j+1] = arr[j];
}
arr[left] = temp;
}
}
```
实现过程:
1. 遍历数组,从第二个元素开始,将该元素作为待排序元素;
2. 将该元素插入到已排序的子数组中,使得插入后的子数组仍然是有序的;
3. 采用二分查找的方式,找到待排序元素应该插入的位置;
4. 将待排序元素插入到该位置。
时间复杂度为O(n^2),空间复杂度为O(1)。
相关问题
C语言代码实现二分插入排序算法
下面是用 C 语言实现二分插入排序算法的代码示例:
```c
#include <stdio.h>
void binaryInsertionSort(int arr[], int n) {
int i, j, key, low, high, mid;
for (i = 1; i < n; i++) {
key = arr[i];
low = 0;
high = i - 1;
while (low <= high) {
mid = (low + high) / 2;
if (key < arr[mid])
high = mid - 1;
else
low = mid + 1;
}
for (j = i - 1; j >= low; j--)
arr[j + 1] = arr[j];
arr[low] = key;
}
}
int main() {
int arr[] = {5, 2, 8, 3, 1};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
binaryInsertionSort(arr, n);
printf("Sorted array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
```
这段代码实现了二分插入排序算法,通过调用 `binaryInsertionSort` 函数将数组按升序排序。在 `main` 函数中,我们定义了一个整数数组 `arr`,然后计算数组的长度 `n`。接着,我们打印原始数组,调用 `binaryInsertionSort` 函数对数组进行排序,并最后打印排序后的数组。
运行这段代码,输出结果如下:
```
Original array: 5 2 8 3 1
Sorted array: 1 2 3 5 8
```
可以看到,原始数组经过二分插入排序后得到了升序排序的结果。
C语言二分法插入排序
二分法插入排序是一种高效的排序算法,它结合了二分查找和插入排序的优点。下面是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. 将待排序元素插入到正确的位置。