原本我们是打算说类模板的，但现在看来，关于排序算法的篇幅却占了半壁江山，想了下，还是决定更改一下标题名，以便为了大家将来想要查看排序算法的时候方便一些。
上一讲我们说了冒泡排序，插入排序，希尔排序和并归排序，所以今天我们来看看关于堆排序和快速排序的问题，首先我们来看看堆排序。
堆排序，据说是最优大O运行时间算法，这个算法的思想简单点说就是从数组中删除一个最大（或者最小）的元素，这时原来的数组就会腾出一个空间出来，这个空间就拿来让村我们删除的元素，这么说直接吧，如果我这么说还有不了解的，那么容我想一下还有什么通俗点的说法，哦，
对了，就是如果我们想要顺序排序（从小到大）的话我们就把依次把数组里的最大的数提取出来，然后从数组原来的位置往前放，这样到最后的时候我们的排序也就完成了。
嗯，听起来倒是容易，虽说堆排序，我们并没有浪费太多的空间，而且效率也还算客观的了，当然比不上标准库里的算法（这个问题待会看看能不能给大家一个答案），但是实现起来却有些棘手，如果我们要从数组里面删除一个最大的元素，这个如果处理不好，会浪费很多时间，但是如果处理得当，其实也就是一个常数时间啦，那就是我们总是从数组的最前面删除，但是大家可能会好奇，既然每次删除的第一个都是最大抑或是最小的，那么这岂不是早就已经排好序了吗？是啊，听起来像是这样，其实我们这里想说的当然不是了，如果那样做的话岂不是要排序两次？我脑子进水了吧。如果对二叉树熟悉的朋友一定想到了，我们可以建立一个二叉堆，根的元素永远是最大的，所以我们只需要删除根部的元素，然后让他嫁接到最后的叶子上，当然这似乎又回到递归上面了，好了，说到这里，大家也应该猜到实现方案应该像什么样子的了，我觉得应该可以像这养：
—————————————-
//驱动程序
template<typename T>
void heapsort(vector<T>&
a)
{
for(int i=a.size()/2;
i>=0;
i–)
{
binaryheap(a,i,a.size());
}
for(int j=a.size()-1;
j>0;
j–)
{
swap(a[0],a[j]);
binaryheap(a,0,j);
}
}
//i表示父亲的索引，所以这里是返回左孩子的索引
inline
int leftchild(int i)
{
return 2*i+1;
}
//建立二叉堆，保证每对作为根的儿子（只要是有儿子，就算他是别的儿子他也算是根）左边一定小于等于右边。
template<typename T>
void binaryheap(vector<T>&
a,int i,int n)
{
int child;
T temp;
for(temp = a[i];
leftchild(i)<n;
i=child)
{
child = leftchild(i);
if(child != n-1 &
&
a[child]<=a[child+1])
child++;
if(temp <a[child])
a[i] = a[child];
else
break;
}
a[i] = temp;
}
—————————————-
好了，关于堆排序，就到这里吧，下面我们来看看快速排序。什么是快速排序，就是排序最快的排序方法，不过，我想说这只是理论上的，当然他有他存在的道理，那就是他用理论击败了一切，大家可能会说，那是因为你自己的实现方式有问题吧，嗯，我承认，我确实是遇到了这个问题，因为我自己写的快速排序确实不快，而我却没有理清楚是为什么，当然，在上我代码之前，我们先来看看什么是快速排序。
快速排序之所以被程序快速排序是因为使用了高度优化的内部循环，这里极为重要，因为稍有不慎就会弄巧成拙，快速却快不起来，最多就就是比插入排序好点了，看到此处，大家是不是要惊呼出来：啊，怎么可能？是你自己的问题吧。嗯，好吧，我们继续来探究快速为什么会快不起来的原因。
再说这之前，首先得明白怎么快速排序的实现原理。
1）从数组中取出一个元素来充当枢纽元素v。
2）将比枢纽元素小的王前段扔，将比枢纽元素的往后面扔。
3）分别对两边的数组进行快速排序，还是递归，递归好像不是省时间的灯啊，不过我们有给决解方案，那就是当每个分组比较小的时候我们就采用插入排序这种对小数据极为有效的方案来替代，这样可以节约不少的时间。
快拍的原理就是这些，如果处理得好，他可以以O(NlogN)的时间运行，效率极高，但是如果处理不好，就是O(N^2)，那么关键的地方在哪里呢？
1）枢纽元素v的选取，为什么会这么说呢？如果我们一个大数组，我们选择了最小的一个或者最大的一个作为枢纽元素，那么这个和不选又有什么区别呢？不是空浪费时间吗？所以，有些人选择枢纽元素会经常选取第一个或者最后一个，这有着极为严重的隐患。
2）一般比较好使的是使用随机数，但是随机数的生成却是极为昂贵的，所以对节省不了多少时间呢。
3）被认可的方案是三数中值法，这种方案通常是取头取尾和取中间一个数，他们分别为：array[left],array[center],array[right]，然后我们再对这三个数进行排序，当然是按序排序了，拍好序后，我们将array[center]和array[right-1]交换位置，为什么这样做呢？当然是防止越界了，因为这样一来，我们可以从array[2]和array[right-2]开始对比，将比v大的扔到一组，将比v小的扔到一组。
好吧，下面是我的实现方案，这是一个有问题的实现方案，问题出在三数中值上面，他效率太低，不如堆排，不如希排，根本配不上快拍的称呼，这就是我为什么会说快拍只存在于理论之中的道理，就算根据同一理念，不同的人会设计出不同的方案。
————————————-
template<typename T>
void quicksort(vector<T>&
a)
{
quicksort(a,0,a.size()-1);
}
template<typename T>
const T&
mid(vector<T>&
a,int left,int right)
{
int center = (left + right)/2;
if(a[center] <a[left])
swap(a[center],a[left]);
if(a[right] <a[left])
swap(a[right],a[left]);
if(a[center] <a[right])
swap(a[center],a[right]);
swap(a[center],a[right-1]);
return a[right-1];
}
template<typename T>
void quicksort(vector<T>&
a,int left,int right)
{
if(left+10 <right)
{
T pivot = mid(a,left,right);
int i=left,j=right-1;
for(;
;
)
{
while(a[++i] <pivot)
;
while(pivot <= a[–j])
;
if(i<j)
swap(a[i],a[j]);
else
break;
}
quicksort(a,left,i-1);
quicksort(a,i+1,right);
}
else
insertionsort(a);
//这里为了效率调用我们的插入排序
}
———————————–
现在我们来测试一下heapsort和quicksort的效率，让大家开开眼界，也好让大家看看这个快拍的问题到底出在哪里：
————————————-
这是堆排的效率，其实还是不错的，排100万数据也就要6秒的时间而已，不过和标准库的sort比起还是要差了很多。
下面，我们再来看看我们这个快拍的效率：
——————————————-
我操，大概10多分钟了还没计算出来，算了。大家知道很慢就行，看了10000数据量的排序大家就知道了：
——————————————
标准的算法明天再给出来，今天章节不够用了。
原文始发于微信公众号（
C/C++的编程教室
）：第四十七讲 排序算法（2）
|