排序 quick_sort 快排 算法　　随机函数　rand() 快速排序的随机化版本

快速排序:

快速排序在基本逆序的情况下时间复杂度时O(n*n),虽然他在最坏情况下效率很差.但是快排在实际应用中通常是最好的选择,应为他的平均性能是最好的.他的期望时间复杂度时

O(n lgn), 而且O(nlgn)中的常数因子很小, 另外他还能进行原址排序,甚至在虚存环境中也能很好的工作.

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

#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;}

素组元素最坏情况划分:快排在数组元素基本逆序和基本正序的情况下partition的次数是相同的是O(n*n),  递归式是T(n)=T(n-1)+T(0)+O(n).

数组元素在最好情况下划分:

每次partition的划分比例大概是是n/2和n/2   ,  递归式是: T(n)=2T(n/2)+O(n).由主定理第二条知道 时间复杂度是O(n lg n) .

快排的随机化版本：

基本上和上面的一样，不同之处是：在parttition()函数里面主元是随机出来的，这就避免了当数据基本有序是快排的时间复杂度为Ｏ(n*n)，这样保证每次划分时基本平衡的．

#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)//快排的随机化版本{srand((int)time(0));//随机出主元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;}