用折半查找法给随机的10个数的排出大小,用C语言的数组,不用指针
时间: 2024-09-27 15:14:48 浏览: 30
折半查找法,也称二分查找,通常用于有序序列中查找特定元素。为了将随机的10个数从小到大排序,我们可以采用选择排序的思想结合折半查找辅助优化,虽然这并不是标准的折半查找算法,但它可以在不知道元素具体值的情况下进行操作。
以下是简单的步骤和C语言实现示例:
1. 创建一个长度为10的整型数组,存储随机生成的10个数。
2. 使用一个循环遍历数组,每次从剩余未排序部分的中间元素开始,找到其中最小的一个并交换到已排序部分的末尾。
3. 在每次迭代中,可以利用折半查找找到剩余数中的最小元素。但是,由于数据未排序,这里不需要真正的二分查找,而是简单地比较数组的前一半。
```c
#include <stdio.h>
#include <stdlib.h>
// 比较函数,用于辅助查找最小值
int compare(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
void selection_sort_with_half_search(int arr[], int n) {
for (int i = 0; i < n; i++) {
// 只有当需要排序的元素小于等于剩余的一半时,才进行折半查找简化
if (i > n / 2) {
// 找到未排序部分最小值
int min_index = i;
for (int j = i + 1; j < n; j++) {
if (compare(&arr[j], &arr[min_index]) < 0)
min_index = j;
}
// 将找到的最小值与当前未排序的第一个元素交换
int temp = arr[i];
arr[i] = arr[min_index];
arr[min_index] = temp;
} else {
// 对剩余的未排序部分进行简单比较
int min_index = i;
for (int j = i + 1; j < n; j++)
if (arr[j] < arr[min_index])
min_index = j;
int temp = arr[i];
arr[i] = arr[min_index];
arr[min_index] = temp;
}
}
}
int main() {
int size = 10;
int* arr = malloc(size * sizeof(int));
// 随机填充数组
srand(time(0));
for (int i = 0; i < size; i++)
arr[i] = rand() % 100; // 示例中随机生成0到99之间的数
printf("Original array:\n");
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
selection_sort_with_half_search(arr, size);
printf("\nSorted array using half search optimization:\n");
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
free(arr);
return 0;
}
```