我正在做一項(xiàng)家庭作業(yè)任務(wù)，我應(yīng)該創(chuàng)建一個(gè)執(zhí)行二進(jìn)制插入排序的函數(shù)，但我的函數(shù)似乎無(wú)法正常工作。這里我嘗試將二分查找函數(shù)與插入排序函數(shù)結(jié)合起來（作業(yè)任務(wù)中指定需要采用函數(shù)的形式：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} 運(yùn)行它，輸出將是2 5 1 3 1（如果 lo < hi 并且如果 lo > hi）2 5 3 8 5（如果 lo==hi）不過，我期待的是一個(gè)排序列表...知道我做錯(cuò)了什么嗎？
3 回答
MM們
TA貢獻(xiàn)1886條經(jīng)驗(yàn) 獲得超2個(gè)贊
只是為了給你一個(gè)可能的想法：
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貢獻(xiàn)1865條經(jīng)驗(yàn) 獲得超7個(gè)贊
謝謝您的意見。我稍微改變了功能，現(xiàn)在似乎可以工作了
` public static void insertSort(int[] array, int lo, int hi){ int mid; 整數(shù)位置；
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;
}
}
問題似乎出在最后一部分，我試圖將元素移動(dòng)到正確的位置。該功能可能并不完美，因此歡迎建設(shè)性批評(píng):)
一只萌萌小番薯
TA貢獻(xiàn)1795條經(jīng)驗(yàn) 獲得超7個(gè)贊
每當(dāng)我需要二分搜索時(shí)，我的函數(shù)看起來如下：
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 方法中，調(diào)用如下所示：
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);
}
我希望我能夠幫助你！
添加回答
舉報(bào)
0/150
提交
取消