快速排序:

快速排序在基本逆序的情況下時(shí)間復(fù)雜度時(shí)O(n*n),雖然他在最壞情況下效率很差.但是快排在實(shí)際應(yīng)用中通常是最好的選擇,應(yīng)為他的平均性能是最好的.他的期望時(shí)間復(fù)雜度時(shí)

O(n lgn), 而且O(nlgn)中的常數(shù)因子很小, 另外他還能進(jìn)行原址排序,甚至在虛存環(huán)境中也能很好的工作.

快速排序使用了分治思想.

#include<iostream>using namespace std;void exchange(int *a,int *b){int t=*a;*a=*b;*b=t;}int  partition(int *a,int left,int right){int key=a[right];int i=left-1;int j=left;for(;j<=right-1;++j)    {        if(a[j]<a[right])        {        ++i;        exchange(&a[i],&a[j]);        }    }    exchange(&a[i+1],&a[right]);return i+1;}void quick_sort(int *a,int left,int right){if(left<right)    {        int q=partition(a,left,right);        quick_sort(a,left,q-1);        quick_sort(a,q+1,right);    }}void output(int *a,int len){for(int i=0;i<len;++i)cout<<a[i]<<"  ";cout<<endl;}int main(){int a[8]={2,8,7,1,3,5,6,4};quick_sort(a,0,7);output(a,8);return 0;}

素組元素最壞情況劃分:快排在數(shù)組元素基本逆序和基本正序的情況下partition的次數(shù)是相同的是O(n*n),  遞歸式是T(n)=T(n-1)+T(0)+O(n).

數(shù)組元素在最好情況下劃分:

每次partition的劃分比例大概是是n/2和n/2   ,  遞歸式是: T(n)=2T(n/2)+O(n).由主定理第二條知道 時(shí)間復(fù)雜度是O(n lg n) .

快排的隨機(jī)化版本：

基本上和上面的一樣，不同之處是：在parttition()函數(shù)里面主元是隨機(jī)出來(lái)的，這就避免了當(dāng)數(shù)據(jù)基本有序是快排的時(shí)間復(fù)雜度為Ｏ(n*n)，這樣保證每次劃分時(shí)基本平衡的．

#include<iostream>#include<stdio.h>#include<stdlib.h>#include<time.h>using namespace std;void exchange(int *a,int *b){int t=*a;*a=*b;*b=t;}int  partition(int *a,int left,int right)//快排的隨機(jī)化版本{srand((int)time(0));//隨機(jī)出主元int rand_key=rand()%(right-left+1)+left;//exchange(&a[rand_key],&a[right]);//int key=a[right];int i=left-1;int j=left;for(;j<=right-1;++j)    {        if(a[j]<a[right])        {        ++i;        exchange(&a[i],&a[j]);        }    }    exchange(&a[i+1],&a[right]);return i+1;}void quick_sort(int *a,int left,int right){if(left<right)    {        int q=partition(a,left,right);        quick_sort(a,left,q-1);        quick_sort(a,q+1,right);    }}void output(int *a,int len){for(int i=0;i<len;++i)cout<<a[i]<<"  ";cout<<endl;}int main(){int a[8]={2,8,7,1,3,5,6,4};quick_sort(a,0,7);output(a,8);return 0;}