插入排序程序有有关问题,求指导~
插入排序程序有问题,求指导~~
下面是我写得插入排序的代码,我在查找插入位置时,采用的是二分查找法,但是运行出现程序终止的问题。不知道错在哪儿了~~求大虾指导~~
------解决方案--------------------
二分查找函数有问题,修改如下:
下面是我写得插入排序的代码,我在查找插入位置时,采用的是二分查找法,但是运行出现程序终止的问题。不知道错在哪儿了~~求大虾指导~~
- C/C++ code
//insertion sort #include <iostream> using namespace std; //在数组a[low]---a[high]查找val插入的位置 int InsertLoc(int *a,int low,int high,int val) { if(low == high) { if(val > *(a + low))return (low + 1); else return low; } int mid = (low + high) / 2; if(val > *(a + mid) && val < *(a + mid + 1)) return mid; else if(val < *(a + mid) && val < *(a + mid + 1)) return InsertLoc(a,low,mid,val); else return InsertLoc(a,mid,high,val); } //改进:用二分查找来找到插入的位置 void InsertionSort(int *a,int n) { int temp,insert_location; for(int i = 1;i < n;++i) { temp = *(a + i); int j = i - 1; insert_location = InsertLoc(a,0,j,temp); cout<<"insert_location:"<<insert_location<<endl; while(j >= insert_location) { *(a + j + 1) = *(a + j); --j; } *(a + insert_location) = temp; } } int main() { int n,temp; cout<<"please input the number of the values that need to sort:"<<endl; cin>>n; int *a = (int*)malloc(n * sizeof(int)); cout<<"please input each value:"<<endl; for(int i = 0;i < n;++i) { cin>>temp; *(a + i) = temp; } InsertionSort(a,n); cout<<"the values after sort:"<<endl; for(int i = 0;i < n;++i) cout<<*(a + i)<<" "; }
------解决方案--------------------
二分查找函数有问题,修改如下:
- C/C++ code
int InsertLoc(int *a,int low,int high,int val) { if(low == high) { if(val > *(a + low))return (low + 1); else return low; } int mid = (low + high) / 2; if(val > *(a + mid)) return InsertLoc(a,mid+1,high,val); else if(val < *(a + mid)) return InsertLoc(a,low,mid-1,val); else return mid; }
------解决方案--------------------