小米面试：台球的希尔排序
The following article is from 爱码有道 Author 点击关注👉👉
如若转载请联系原公众号
今天，我们来看一道小米面试的题目，很直白，也很简单，那就是希尔排序。
按常理来说，快速排序和堆排序才是常考的内容，希尔排序出现的频率很低。
这也启发大家，在准备笔试面试的时候，不仅要注意深度，也需要注意广度。
图解希尔排序
原始的数组如下，有一点台球的感觉吧：
接下来，我们对这个数组进行希尔排序，希尔排序的本质是缩小增量排序，我们来看看，是如何逐步缩小增量的。
第一步：
元素个数n=10, 那么gap=5, 接下来，我们来分为5组，如下：
在5组内分别进行插入排序，得到的结果为：
第二步：
我们让gap再次减半，也就是gap=2, 于是重新分为2组，如下：
在2组内分别进行插入排序，得到的结果为：
第三步：
我们让gap再次减半，即gap=1, 也就是分为1组，得到的结果为：
在1组内进行插入排序，得到的结果为：
这就是希尔排序的全部过程，思路非常简单，抓住缩小增量这个本质就行。通过不断缩小gap的值，在每个组内进行插入排序。
当然，小米的面试题肯定不会就此让你轻松结束，肯定会问时间复杂度和空间复杂度，所以，在准备面试时也不要忽略基本功。
希尔排序程序
既然思路已经完全说清楚了，那么程序就相对简单了，来看看希尔排序的程序：
#includeusing namespace std;
void print(int a[], int n){ for(int i = 0; i < n; i++) { cout << a[i] << " "; } cout << endl << endl;}
void shellSort(int a[], int n){ int i, j, pivotKey, gap; for(gap = n/2; gap > 0; gap--) { for(i = gap; i < n; i++) { pivotKey = a[i]; for(j = i - gap; j >= 0 && a[j] > pivotKey; j -= gap) { a[j + gap] = a[j]; }
a[j + gap] = pivotKey; } }} int main(){ int a[] = {4, 5, 6, 3, 2, 1, 9, 0, 8, 7}; int n = sizeof(a) / sizeof(a[0]); shellSort(a, n); print(a, n); return 0;}结果为：
0 1 2 3 4 5 6 7 8 9
希尔排序的思路和程序并不难，但常常容易被忽略，导致笔试面试会比较被动。我们也会一步一个脚印，争取每篇文章讲清讲透一件事，也希望大家阅读后有所收获，心情愉快。
推荐阅读：
每日打卡赢积分兑换书籍入口