經(jīng)常聽人談起各種排序算法的時(shí)間復(fù)雜度，這個(gè)是O(n2)的，那個(gè)是O(n)的，這些人講起來(lái)可謂滔滔不絕，但是你停下來(lái)問問他為什么這個(gè)是這個(gè)復(fù)雜度，他是怎么算出來(lái)的？往往沒幾個(gè)人能說出來(lái)。這個(gè)是一個(gè)浮躁的社會(huì)，大家都追求速度，到處復(fù)制，粘貼代碼，拿人家的代碼跑一便，就說自己會(huì)了這個(gè)，會(huì)了那個(gè)..
也許有人覺得算法分析的太深沒有用，但是筆者認(rèn)為，有時(shí)候了解細(xì)節(jié)很重要，比如快速排序算法的時(shí)間復(fù)雜度，有時(shí)候是O(nlgn), 有時(shí)候就是O(n2), 在你不知道自己數(shù)據(jù)特性的情況下，很難選擇是否使用快速排序，因?yàn)樗⒉豢偸亲羁斓摹?/p>
說了些沒用的，讓我們進(jìn)入正題吧：
為了分析快速排序的時(shí)間復(fù)雜度，請(qǐng)先看下面的主定理：
主定理: T [n] = aT[n/b] + f (n)
其中 a >= 1 and b > 1 是常量 并且 f (n) 是一個(gè)漸近正函數(shù)， 為了使用這個(gè)主定理，您需要考慮下列三種情況：
想必大家都知道快速排序的過程，如果對(duì)這個(gè)過程有什么不了解，請(qǐng)參考下文：
http://www.cnblogs.com/pugang/archive/2012/06/27/2565093.html
快速排序的每一次劃分把一個(gè) 問題分解成兩個(gè)子問題，其中的關(guān)系可以用下式表示：
T[n] = 2T[n/2] + O(n) 其中O(n)為PARTITION()的時(shí)間復(fù)雜度，這里是分解成兩個(gè)相等規(guī)模的子問題，對(duì)比主定理，
T [n] = aT[n/b] + f (n)
我們的快速排序中：a = 2, b = 2, f(n) = O(n)
那么為什么還有最壞情況呢？
考慮如下極端情況，
T[n] = T[n-1] + T[1] + O(n)，這里是分解成一個(gè)n-1規(guī)模的子問題和一個(gè)1規(guī)模的子問題
問題來(lái)了，這一次的劃分白玩了，劃分之后一邊是一個(gè)，一邊是n-1個(gè)，這種極端情況的時(shí)間復(fù)雜度就是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;
}
快速排序是一個(gè)最差時(shí)間復(fù)雜度為O(n2)的排序算法，這種情況通常出現(xiàn)在選擇的軸值(pivot)不能將數(shù)組劃分為兩個(gè)長(zhǎng)度相等的子數(shù)組的時(shí)候，比如數(shù)組逆序排列的時(shí)候，如果選擇第一個(gè)數(shù)作為軸值，劃分的子數(shù)組的大小分別為0和n-1，此時(shí)算法的性能最差。
一個(gè)較好的辦法是“三數(shù)取中”，查看當(dāng)前數(shù)組的第一個(gè)、中間一個(gè)和最后一個(gè)位置的數(shù)組，取其中位數(shù)，以此來(lái)降低軸值選擇得不好的可能性。
//將開頭、中間、結(jié)尾位置的中間一個(gè)元素交換到開頭
+(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);
}
}
//先進(jìn)行三數(shù)取中，其余地方不變，性能提升非常顯著
