希爾排序 算法

算法思路

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;
  }
}      

算法分析