经常听人谈起各种排序算法的时间复杂度，这个是O(n2)的，那个是O(n)的，这些人讲起来可谓滔滔不绝，但是你停下来问问他为什么这个是这个复杂度，他是怎么算出来的？往往没几个人能说出来。这个是一个浮躁的社会，大家都追求速度，到处复制，粘贴代码，拿人家的代码跑一便，就说自己会了这个，会了那个..
也许有人觉得算法分析的太深没有用，但是笔者认为，有时候了解细节很重要，比如快速排序算法的时间复杂度，有时候是O(nlgn), 有时候就是O(n2), 在你不知道自己数据特性的情况下，很难选择是否使用快速排序，因为他并不总是最快的。
说了些没用的，让我们进入正题吧：
为了分析快速排序的时间复杂度，请先看下面的主定理：
主定理: T [n] = aT[n/b] + f (n)
其中 a >= 1 and b > 1 是常量 并且 f (n) 是一个渐近正函数， 为了使用这个主定理，您需要考虑下列三种情况：
想必大家都知道快速排序的过程，如果对这个过程有什么不了解，请参考下文：
http://www.cnblogs.com/pugang/archive/2012/06/27/2565093.html
快速排序的每一次划分把一个 问题分解成两个子问题，其中的关系可以用下式表示：
T[n] = 2T[n/2] + O(n) 其中O(n)为PARTITION()的时间复杂度，这里是分解成两个相等规模的子问题，对比主定理，
T [n] = aT[n/b] + f (n)
我们的快速排序中：a = 2, b = 2, f(n) = O(n)
那么为什么还有最坏情况呢？
考虑如下极端情况，
T[n] = T[n-1] + T[1] + O(n)，这里是分解成一个n-1规模的子问题和一个1规模的子问题
问题来了，这一次的划分白玩了，划分之后一边是一个，一边是n-1个，这种极端情况的时间复杂度就是O(n2).
快排代码
+(NSInteger)partition:(NSMutableArray *)arr
{
NSNumber *split = arr.firstObject;
NSInteger i = 0;
NSInteger j = arr.count-1;
while (i!=j) {
while ([arr[j]integerValue]>=split.integerValue) {
j--;
}
while ([arr[i]integerValue]<=split.integerValue) {
i++;
}
if (i>=j) {
break;
}
[self swapeArr:arr index:i andIndex:j];
}
NSNumber *num = arr[j];
arr[j] = split;
arr[0] = num;
return j;
}
+(NSInteger)partition1:(NSMutableArray *)arr
{
NSNumber *firstN = arr.firstObject;
NSInteger i = 0;
NSInteger j = 1;
NSInteger len = arr.count;
while (j<len-1) {
j++;
if ([arr[j]integerValue]<[firstN integerValue]) {
[self swapeArr:arr index:j andIndex:++i];
}
}
[self swapeArr:arr index:i andIndex:0];
return i;
}
快速排序是一个最差时间复杂度为O(n²)的排序算法，这种情况通常出现在选择的轴值(pivot)不能将数组划分为两个长度相等的子数组的时候，比如数组逆序排列的时候，如果选择第一个数作为轴值，划分的子数组的大小分别为0和n-1，此时算法的性能最差。
一个较好的办法是“三数取中”，查看当前数组的第一个、中间一个和最后一个位置的数组，取其中位数，以此来降低轴值选择得不好的可能性。
//将开头、中间、结尾位置的中间一个元素交换到开头
+(void)swap:(NSMutableArray *)arr start:(NSInteger)start end:(NSInteger)end
{
var mid = Math.floor(start+(end-start)/2);
if(this[start]>this[end])
{
this.swap(start,end);
}
if(this[mid]>this[end])
{
this.swap(mid,end);
}
if(this[mid]>this[start])
{
this.swap(mid,start);
}
}
//先进行三数取中，其余地方不变，性能提升非常显著
网友评论