希尔排序

希尔排序实现

 1 #include <iostream>
 2 #include <vector>
 3 
 4 using namespace std;
 5 
 6 void shell_sort(vector<int> &nums)
 7 {
 8     for(int gap = nums.size() / 2; gap > 0; gap /= 2)
 9     {
10         for(int i = gap; i < nums.size(); i++)
11         {
12             int temp = nums[i];
13             for(int j = i - gap; j >= 0 && nums[j] > temp; j -= gap)
14             {
15                 nums[j + gap] = nums[j];//移位法，与交换法swap比，可以减少复制次数
16             }
17             nums[j + gap] = temp;// j + gap 是回溯 循环中 j - gap：循环一次也没有运行 自己赋给自己；循环跑到不满足条件就回溯到最后一个空位置
18         }
19     }
20 }

参考：

1、https://www.cnblogs.com/chengxiao/p/6104371.html

2、参考《C和C++程序员面试秘笈-董山海》第九章排序希尔排序