C++希尔排序怎么使用

C++希尔排序是一种插入排序，它是一种改进的插入排序，它可以比插入排序更快地完成排序。希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

C++希尔排序的使用方法如下：

（1）首先确定步长，步长的确定方法是将待排序的数据元素个数n，除以2，得到的商为步长d1；然后将d1再除以2，得到的商为步长d2，以此类推，直至得到的商为1，这时的步长就是最小的步长。

（2）然后从最小的步长开始，将相隔步长的元素分别进行插入排序，比如以步长d3为例，则将元素a[0]、a[3]、a[6]……一次进行插入排序；然后以步长d2为例，将元素a[0]、a[2]、a[4]……一次进行插入排序；最后以步长d1为例，将元素a[0]、a[1]、a[2]……一次进行插入排序。

（3）重复上述步骤，直至步长为1，此时所有元素都已经排好序，排序完成。

C++希尔排序的优点是它的运行时间与记录的初始排列无关，它的时间复杂度可以达到O(nlog2n)，而插入排序的时间复杂度为O(n2)，所以C++希尔排序比插入排序的性能好得多。但是由于它的复杂性，它的空间复杂度也比插入排序要高，所以它的应用范围要比插入排序小。