希尔排序 算法

算法思路

1. 插入排序的改进版，选择插入距离远的元素
2. 选择一个间距，将序列分成很多子序列并行插入排序
3. 降低间距，并重复插入元素，直到间距将为1，完成排序。

算法实现

void shell_sort(vector<int> &arr, int beg, int gap) {//gap为1时即直接插入排序
  for (int i = beg + gap; i< arr.size(); i += gap) {
    int tem = arr[i];
    int j = i - gap;
    for (;j >=0 && tem < arr[j]; j -= gap) {
      arr[j+gap] = arr[j];
    }
    arr[j+gap] = tem;
  }
}

void shell(vector<int> &arr) {
  int gap = arr.size() / 2;
  while(gap > 0) {
    int beg = gap - 1;
    while(beg >=0) {//使用当前gap，将所有元素位置按照要求进行调整
      shell_sort(arr, beg, gap);
      beg --;
    }
    gap /= 2;
  }
}      

算法分析