初阶数据结构学习记录——열셋排序（2）-创新互联

接着上一篇说快排

改进一下上一篇所写的快排。

这里的快排方法是霍尔方法。不过这个方法还没完全。可以发现，排一遍后，就会分成两个区间继续快排，然后左右两个区间又会各自分出两个区间继续排，所以这其实是一个满二叉树结构，因为不一定每个区间都需要排。

现在这个算法的时间复杂度是多少？如果单趟排序，那么应该是一个O(N)。具体应该走多少次？

这个二叉树结构的高度是logN，数据总数为N。第一次排序后，到了第二层，左右两个区间继续排，这时候要排的数据总数就变成N - 1.第三层就变成了N -  3.，然后一直排下去。不过持续减下去N也不会减到0，假设N是1000，那么总体的高度大约就是10，所以最终N也没减少太多。

所以整体时间复杂度应该N * logN。不过快排的时间复杂度也并非是这个，毕竟不可能每次都在排序。对于快排来说，无论是顺序还是逆序，似乎每一次都要排序，这时候的时间复杂度可以看出来是N方，所以有序对于快排来讲就是很不好的情况，相反，无序才是快排最适合的。不过实际中我们无法决定数据是什么序。假如是逆序或者顺序，选择前后两端作为key，都需要所有数据全部走一遍才行。为了解决这个问题，在快排之前，先把大最小以及中间那个数字拿出来做比较，选中杯，这样即使是一个有序的数据集，也不会每次都要全部比较排序一遍；这个方法放到无序数据里也没关系，这对无序并没有多少影响，当然也有可能在无序数据里就正好选出了最小的那个数，但概率确实小，不必考虑。

我们看一下有序和无序数据快排的效率，先改成有序10万个数字。

再改成无序

这当然是在release模式下运行的，如果是在debug下运行，有序数据其实就崩了，因为现在这个快排是个递归写法，对于有序数组，代码需要一直往下开栈，开到最后才停，所以栈爆了。而且，仅从数字上看也能看出，快排面对有序或者接近有序是低效的。

现在我们写一下三数取中算法。不过确定中间值后key还是=begin，只是在这之前把中间值和begin的值互换一下。

加入三数取中后，再看有序快排

这就正常了。再看无序

当然选key问题还有别的解决办法，比如选出随机数做key。

选key结束后，现在这个快排还有另一个问题。快排会逐渐减少排序的数据量，如果N是10，排序两个层后每个区间也就剩两三个数据了，回想一下刚才说的二叉树结构，如果继续使用快排，那么又得选key， 继续调用栈帧，这样的话不高效啊，费空间，而且实际上10个数也是一个很小的数据了，然而10个数我们还需要做好几次递归，小题大做了。所以小数据时就不用快排了，当然其他用递归的排序也不选了，冒泡和选择排序也先去掉，所以就剩直接插入，希尔，堆排序了。

实际上会选择直接插入排序。希尔排序会先预排，让大的数尽快走到后面，然后再插入排序，不过小数据上希尔排序也不一定有优势。

我们看一下10000个数排序

所以总共就差距几毫秒而已。没必要再去做预排序了。而堆排序其实还要向下调整，建堆，所以不如简单的一个思路，直接插入即可。

10个数的递归，是经历三层排序才会结束。如果这样的小数据用插入排序，实际上会省出很多的时间。按照二叉树结构，第一层递归1次，第二层2次，第三层4次，第4层8次，而最后一层就是2的h次方  -   1.即使去掉最后一层，也会减少一半的递归次数，而去掉最后三层就去掉了80%多的次数。可以带入具体的数来计算，会发现最后一层占了一半，而倒数第二层大约占总次数的25%。所以小区间的优化很有必要。

现在写一下代码

做一下测试，这里效果不如三数取中那么明显，所以我们取很大的数，就不看插入排序了。

百万个数据 

千万个

千万个有序

不过这里用的测试很单一，代码很简单，只是看一个大概的效果改变。以及release模式对于递归的优化也很大。

debug下百万无序

有序的话会更快

不过千万个数据debug下就难受了。

挖坑法

快排其实不止这一个方法，这个方法是霍尔方法，而快排还有另外两个办法，挖坑和双指针。

先把代码区分出来，三个方法都取名叫partsort

挖坑法依然要用到key，不过key的用法不一样，key会先存一个值，这个值对应的位置就形成一个坑位，然后左右LR开始走，R找到比key小的，然后和那个坑位互换一下，R形成新的坑位，然后L找比key大的值，和坑位互换一下，L处形成新的坑位。这个方法走完一次后的数据顺序和霍尔方法后的顺序不一样。

这里还是要找中杯。这个方法和霍尔有些像，实现起来也不算难

双指针法

双指针prev，cur，这个方法理解后代码就会很容易写出来。假设选择0下标为key，prev指向0，而cur指向1下标处。cur往后走，如果小于key，那么prev往后走一步，并互换一下；遇到大于key的值后，prev停下，cur继续往后走，等再次找到小的，那么按照上句所写，prev往后走一步，来到一个大的值，互换一下。当然这里持续地往后走，我们一定要考虑越界问题，以及如果cur和prev处于同一位置，那么此时的互换可以避开一下，节省不必要的操作。

两个swap之前和之后的代码暂且不管，重点在中间。cur一开始就在prev的后一步；++prev ！= cur就是避免同位置互换的操作。

非递归快排

以上都是递归排法，但毕竟需要一直开栈，所以非递归写法是很必要的。

这个可以和斐波那契数列的做法相似，数列是把第一个第二个直接写了出来，然后循环，快排的非递归也是改循环，不过需要借助栈。

先想一下递归。先递归左，然后回去再递归右，区间的变化是可以捕捉到的，用栈也一样，栈保存区间，我们就可以和递归一样访问不同的区间了。

假设一个10个数的数组，栈里进去0和9下标后，先放进6和9，再放0和4，这样就能先改变[0, 4]区间的顺序了。

先进入最一开始的左右两端下标。right拿到一个，left拿到一个，选好key，就开始分区间排序。如果说走到最后，区间已经不存在了或者只存在一个值，那就不需要再push了，所以呀有两个if作为判断。只要栈中还有数据，我们就需要继续循环，所以while判断条件是不为空。整个过程也就结束了。

下一篇继续写排序

结束。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧