我正在做一項家庭作業任務，我應該創建一個執行二進制插入排序的函數，但我的函數似乎無法正常工作。這里我嘗試將二分查找函數與插入排序函數結合起來（作業任務中指定需要采用函數的形式：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
提交
取消