我正在做一项家庭作业任务，我应该创建一个执行二进制插入排序的函数，但我的函数似乎无法正常工作。这里我尝试将二分查找函数与插入排序函数结合起来（作业任务中指定需要采用函数的形式：insertionSort(int[] array, int lo, int hi)） public static void insertionSort(int[] array, int lo, int hi){ int mid; int pos; for (int i = 1; i < array.length; i++) { int x= array[i]; while (lo < hi) { mid = lo + (hi -lo)/2; if (x == array[mid]) { pos = mid; } if (x > array[mid]) { lo = mid+1; } else if (x < array[mid]) { hi = mid-1; } } pos = lo; for (int j = i; j > pos; j--) { array[j] = array[j-1]; } array[pos] = x; } }如果我尝试使用列表 {2,5,1,8,3} 运行它，输出将是2 5 1 3 1（如果 lo < hi 并且如果 lo > hi）2 5 3 8 5（如果 lo==hi）不过，我期待的是一个排序列表...知道我做错了什么吗？
3 回答
MM们
TA贡献1886条经验 获得超2个赞
只是为了给你一个可能的想法：
public static void insertionSort(int[] array) {
if (array.length <= 1) {
return;
}
// Start with an initially sorted part.
int loSorted = array.length - 1;
//int hiSorted = array.length;
while (loSorted > 0) {
// Take one from the array
int x = array[0];
// Where in the sorted part to insert?
int insertI = insertPosition(array, loSorted);
// Insert x at insertI
...
--loSorted;
}
}
鸿蒙传说
TA贡献1865条经验 获得超7个赞
谢谢您的意见。我稍微改变了功能，现在似乎可以工作了
` public static void insertSort(int[] array, int lo, int hi){ int mid; 整数位置；
for (int i = 1; i < array.length; i++) {
int j = i -1;
int x = array[i];
while (lo <= hi) {
mid = lo + (hi -lo)/2;
if (x == array[mid]) {
pos = mid;
break;
}
if (x > array[mid]) {
lo = mid+1;
}
else if (x < array[mid]) {
hi = mid-1;
}
}
while (j >= 0 && array[j] > x) {
array[j + 1] = array[j];
j = j - 1;
}
array[j + 1] = x;
}
}
问题似乎出在最后一部分，我试图将元素移动到正确的位置。该功能可能并不完美，因此欢迎建设性批评:)
一只萌萌小番薯
TA贡献1795条经验 获得超7个赞
每当我需要二分搜索时，我的函数看起来如下：
public static void binarySearch(int arr[], int first, int last, int key){
int mid = (first + last)/2;
while( first <= last ){
if ( arr[mid] < key ){
first = mid + 1;
}else if ( arr[mid] == key ){
System.out.println("Element is found at index: " + mid);
break;
}else{
last = mid - 1;
}
mid = (first + last)/2;
}
if ( first > last ){
System.out.println("Element is not found!");
}
}
在您的 main 方法中，调用如下所示：
public static void main(String[] args) {
int arr[] = {10,20,30,40,50};
int key = 30;
int last=arr.length-1;
binarySearch(arr,0,last,key);
}
我希望我能够帮助你！
添加回答
举报
0/150
提交
取消