因为智能推荐推了P1177, 快速排序的模板题… 多亏这道题, 让我从连最基础的快排都不会写, 到现在能写出速度比sort快的快排. 靠的是最近几天不停的翻博客和追着老师问. 今天要好好总结下这几天所学习的东西.

最初看着别人的博客, 学会了一个算是最经典的快速排序. 但是性能算是最差的那种. 因此就稳炸喽.
[cc lang=”c”]
void swap(int *a,int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}

int part(int a[],int begin,int end)
{
int mid = a[begin]; // 取最左的元素作为基准
while(begin < end) { while(begin < end && a[end] > mid) // 直到找到一个比轴值小的元素
{
end –;
}
swap(&a[begin],&a[end]); // 这样就能把小的元素排到左边
while(begin < end && a[begin] < mid) // 直到找到一个比轴值大的元素 { begin ++; } swap(&a[begin],&a[end]); // 这样就能把大的元素排到右边 } return begin; } void quicksort(int a[],int begin,int end) { if(begin < end) { mid = part(a,begin,end); // 获取轴值的下标 // 分治的思想 quicksort(a,begin,mid - 1); // 对轴值前面的部分进行快排 quicksort(a,mid + 1,end); // 对轴值后面的部分进行快排 } } [/cc] 这个写法问题就在于太慢了. 在part函数中, 每次循环交换两次元素会导致效率减慢. 并且是以最左或者最右的元素作为固定基准. 如果碰到随机的序列还算好. 如果碰到大部分有序的序列. 每次都这样取基准就会相当于冒泡排序一样. 时间复杂为O(n^2). 提交上去只ac了前面两个点.后面都为tle

在学习上述经典快排的博客后面, 还介绍了一种对快排的优化. 于是就对着来写了一下.
[cc lang=”c”]
void quicksort(int a[],int begin,int end,int k)
{
if(end – begin > k)
{
int mid = part(a,begin,end);
quicksort(a,begin,mid – 1,k);
quicksort(a,mid + 1,end,k);
}
}

void quicksortimprove(int a[],int begin,int end,int k)
{
quicksort(a,begin,end,k);

int temp,j;
for(int i = begin + 1;i <= end;i ++) { temp = a[i]; for(j = i;j > 0 && j[j – 1] > temp;j –)
{
a[j] = a[j – 1];
}
a[j] = temp;
}
}
[/cc]
该算法是在经典排序的基础上, 增加了一个常量k. 增加一次插入排序. 排序的一开始先对序列进行经典快排, 当begin和end的距离小于k值的时候, 停止快速排序.在所有快排结束后, 使用插入排序. 这样的更改, 对一些大部分有序的序列进行排序所耗的时间会比前一个算法快很多. 因为当序列是大部分有序的时候, 快速排序递归到后面的效率就会相当低, 相当于冒泡. 于是只需要通过快速排序, 把大部分序列变为有序. 然后使用插入排序排剩下的乱序. 而为什么要用插入排序呢, 因为当最优(或者说基本有序)的时候, 插入排序的时间复杂为O(n). 通过这样优化, 提交后发现能通过3个点了, 但是还是不能完全ac.

后来尝试更换基准的选择方式. 随机选择任何一个元素作为基准.  这样就不会出现固定基准的尴尬之处, 当序列是有序的时候, 沦为冒泡排序. 但是因为是随机选择, 虽然能对有序序列排序了, 但是对随机序列排序所用的时间会比用固定基准的时候久. (因为随机 不稳定
[cc lang=”c”]
void quicksort(int a[],int i,int j)
{
if(i >= j)
{
return;
}
int mid = a[rand() % j + 1];
int begin = i, end = j;
while(begin < end) { while(a[begin] < mid) { begin ++; } while(a[end] > mid)
{
end –;
}
if(begin <= end) { swap(&a[begin],&a[end]); begin ++; end --; } } quicksort(a,i,end); quicksort(a,begin,j); } [/cc] 同时还更改了交换的方式, 同时扫描两边的元素,  当左边找到比基准大,右边找到比基准小 进行交换(排升序 让小的去右边 大的去左边 相对上面的那种, 这种相当于是一次排两个元素. 于是总体效率应该是比最初的经典快稍微一点. 提交一看, 有一个之前tle的测试点ac了, 之前一个ac的点变为tle, 其他还是tle. 可能随机基准对一些情况还是不太好用. 也许如果结合随机基准、插入排序优化、优化交换方法, 有可能就能ac了. 但是我并没有这样尝试xD 而是直接找了个更加效率的算法. 该算法, 同样的都是更改基准的选择. 而这个算法的基准选择方式就是 取中(直接取序列的中间部分的元素作为基准) 不是三数取中(取最左、中、最右3个元素. 通过比较, 选择大小中间的数(也就是第二大或者第二小的数)作为基准. 不需要调换位置) 理论上三数取中比单纯取中更快, 但是我 懒 的 写!
[cc lang=”c”]
void quicksort(int a[],int begin,int end)
{
if(begin <= end) // 递归的结束条件 { return; } int mid = a[(begin + end) / 2]; // 取中间位置的值作基准 int i = begin, j = end; while(i <= j) // 可以不等于 但是不等于会让算法耗时变长 为什么?? 明明操作变多了 { while(a[i] < mid) { i ++; } while(a[j] > mid)
{
j –;
}

if(i <= j) // 之所以条件加多了个等于 是想让他自己交换自己(没意义)?? { // 然后再让哨兵前进和后退, 分割序列 为后面的递归准备 swap(&a[i],&a[j]); i ++; j --; } } if(begin < j) // 避免越界 { quicksort(a,begin,j); } if(end > i)
{
quicksort(a,i,end);
}
}
[/cc]

取中作为基准后, 提交就全部都ac了, 相比随机数 优势还是很明显的. 当然还可以在此基础上加上插入排序优化. 还有很多很多种优化方式. 但是还没有空尝试, 现在是先把这几天学到的总结下. 免得忘掉了.

关于取中的一些额外事情:

取中, 我一直认为这样交换以后, 左右的i和j都会到达轴值坐标(也就是中间). 然后我就错误的认为, 递归的两部分可以写成, 端坐标到轴坐标+-1. 并且一开始测试的时候, 结果还真的是正常的. 提交oj后, 发现有两个点能ac 但是其他的点是wa 却不是tle问题. 跟老师研究了好久, 发现我所想的情况, 只适合测试数据为奇数个的时候, 偶数的时候大多数是错误的. 错误代码如下:
[cc lang=”c”]
void quicksort(int a[],int begin,int end)
{
if(begin >= end)
{
return;
}
int t = (begin + end) / 2;
int mid = a[t];
int i = begin, j = end;

while(i <= j) { while(a[i] < mid) { i ++; } while(a[j] > mid)
{
j –;
}

if(i <= j) { swap(&a[i],&a[j]); i ++; j --; } } if(begin < j) { quicksort(a,begin,t - 1); // 轴值的前一个 } if(end > i)
{
quicksort(a,t + 1,end); // 轴值的后一个
}
}
[/cc]

在测试数据为4 2 4 5 1的时候 能够正确排出1 2 4 4 5
在测试数据为4 2 4 5 1 3的时候 结果却为2 3 1 4 4 5

如图所示, 当n为偶数时, i和j并不会在轴坐标, 如果此时还用t-1 t +2作为分割的范围, 就出现错误了.


发表评论

电子邮件地址不会被公开。 必填项已用*标注

Related Posts

OIer

归并排序学习总结 & P1309

背景 之所以突然说到归并排序,是因为P1309这道题要用到&#8230 Read more…

OIer

队列和广度优先搜索

队列(queue) 队列是什么 队列是一种特殊的线性表. 是一种先进先 Read more…

OIer

最长不下降子序列 和 最长上升子序列 nlog优化

最长不下降子序列 跟 最长上升子序列不一样 跟最大子段和容易混淆 不下 Read more…