小米面试：台球的希尔排序

 关注

“脚本之家

”，与百万开发者在一起

出处：爱码有道（ID：aimayoudao）

如若转载请联系原公众号

今天，我们来看一道小米面试的题目，很直白，也很简单，那就是希尔排序。

按常理来说，快速排序和堆排序才是常考的内容，希尔排序出现的频率很低。

这也启发大家，在准备笔试面试的时候，不仅要注意深度，也需要注意广度。

图解希尔排序

原始的数组如下，有一点台球的感觉吧：

接下来，我们对这个数组进行希尔排序，希尔排序的本质是缩小增量排序，我们来看看，是如何逐步缩小增量的。

第一步：

元素个数n=10, 那么gap=5, 接下来，我们来分为5组，如下：

在5组内分别进行插入排序，得到的结果为：

第二步：

我们让gap再次减半，也就是gap=2, 于是重新分为2组，如下：

在2组内分别进行插入排序，得到的结果为：

第三步：

我们让gap再次减半，即gap=1, 也就是分为1组，得到的结果为：

在1组内进行插入排序，得到的结果为：

这就是希尔排序的全部过程，思路非常简单，抓住缩小增量这个本质就行。通过不断缩小gap的值，在每个组内进行插入排序。

当然，小米的面试题肯定不会就此让你轻松结束，肯定会问时间复杂度和空间复杂度，所以，在准备面试时也不要忽略基本功。

希尔排序程序

既然思路已经完全说清楚了，那么程序就相对简单了，来看看希尔排序的程序：

#include
using 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 

希尔排序的思路和程序并不难，但常常容易被忽略，导致笔试面试会比较被动。我们也会一步一个脚印，争取每篇文章讲清讲透一件事，也希望大家阅读后有所收获，心情愉快。

  推荐阅读：

每日打卡赢积分兑换书籍入口