插入排序
插入排序的间隔gap=1
void insertSort(){
int arr[] = {9,8,7,6,5,4,3,2,1,0};
int len = 0;
for(int i=1; i < len; i++){
int p = i;
int value = arr[p];
while(p>=1 && arr[p-1] > value ){
arr[p] = arr[p-1];
p = p - 1;
}
arr[p] = value;
}
for(int i = 0; i < len; i++){
printf("%d, ", arr[i]);
}
printf("\n");
}
希尔排序
希尔排序就是在插入排序的基础上增加插入间隔, 间隔gap的初始值为 len/2, 每轮缩减 1/2, 直至 gap缩减到1, 退化为插入排序
其实就是把插入排序的1改为gap即可
void insertSort(){
int arr[] = {9,8,7,6,5,4,3,2,1,0};
int len = 0;
for(int gap=len/2; gap>=1; gap=gap/2){
for(int i=gap; i < len; I++){
int p = i;
int value = arr[p];
while(p>=gap && arr[p-gap] > value ){
arr[p] = arr[p-gap];
p = p - gap;
}
arr[p] = value;
}
}
网友评论