插入排序

插入排序的间隔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;
}

}