问题描述
- 二分排序法的代码，有一个问题
-
void print(int a[], int n ,int i){cout<<i <<":";
for(int j= 0; j<8; j++){
cout<<a[j] <<" ";
}
cout<<endl;
}
/**
- 直接插入排序的一般形式
- @param int dk 缩小增量，如果是直接插入排序，dk=1
- */
void ShellInsertSort(int a[], int n, int dk)
{
for(int i= dk; i<n; ++i){
if(a[i] < a[i-dk]){ //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入
int j = i-dk;
int x = a[i]; //复制为哨兵，即存储待排序元素
a[i] = a[i-dk]; //首先后移一个元素
while(x < a[j]){ //查找在有序表的插入位置
a[j+dk] = a[j];
j -= dk; //元素后移
} a[j+dk] = x; //插入到正确位置 } print(a, n,i ); }}
/**
- 先按增量d（n/2,n为要排序数的个数进行希尔排序
- */
void shellSort(int a[], int n){
int dk = n/2;
while( dk >= 1 ){
ShellInsertSort(a, n, dk);
dk = dk/2;
}
}
int main(){
int a[8] = {3,1,5,7,2,4,9,6};
//ShellInsertSort(a,8,1); //直接插入排序
shellSort(a,8); //希尔插入排序
print(a,8,8);
}
ShellInsertSort函数内部为什么要用：j -=dk;第一次减之后不就是负数了吗？那while判断x < a[j]中不会出错吗？
解决方案
不会的，因为第一次时a[i] = a[i-dk]，使得x不会小于a[j]，也就不会执行while循环了
解决方案二：
这段代码执行的条件就是a[i]<a[i-dk],后面有x=a[i];j=i-dk;
那么第一次判断时，x<a[j]就可以理解为a[i]<a[i-dk],所以while语句是一定是要执行的。
我想问的是：
j -=dk;第一次减之后不就是负数了吗？那while判断x < a[j]中不会出错吗？
解决方案三：
一个排序问题