算法导论第七章题解——插入排序

2012-08-10

算法导论第七章例题——插入排序快速排序的平均意义上的时间复杂度是nlgn，最差意义上的时间复杂度是n*n，算法

算法导论第七章例题——插入排序

快速排序的平均意义上的时间复杂度是nlgn，最差意义上的时间复杂度是n*n，算法的好坏取决于所选取的用于划分数组的元素的大小。

算法的思路是：将数组按照某个元素划分为两个部分，并单独对这两个部分数组进行就地排序，就地排序时重复利用划分的方法将数组分为更小的两部分。

本代码中为了使代码具有平均意义上的时间复杂度，添加了RandomizedPartition函数进行优化，该函数的思路是随机选取介于p和r之间的元素和

r元素互换，然后再按照a[r]进行划分数组。

//Quick_sort//time complexity is nlgn//the way is find an element,and partition the array according to this element#include<iostream>using namespace std;int Partition(int a[],int p,int r){int num=a[r];int i=p-1;int j,temp;//partition the array according to numfor(j=p;j<=r-1;j++){if(a[j]<num){i+=1;temp=a[j];a[j]=a[i];a[i]=temp;}}//Insert the num between the partiontemp=a[r];a[r]=a[i+1];a[i+1]=temp;//return the partition boundrayreturn i+1;}//Randomized Partition,in this function we random select//the element in array,and exchange it with the lase element in array//the target is lowdown the average time complexity !int RandomizedPartition(int a[],int p,int r){//generate i between  p and rint i=rand()%(r+1-p)+p;int temp;temp=a[i];a[i]=a[r];a[r]=temp;return Partition(a,p,r);}//recursive calls QuickSort to cpmplate the sortvoid QuickSort(int a[],int p,int r){int q;if(p<r){q=RandomizedPartition(a,p,r);QuickSort(a,p,q-1);QuickSort(a,q+1,r);}}int main(){int arr[10]={5,2,3,6,1,7,6,9,5,10};QuickSort(arr,0,9);int i;for(i=0;i<10;i++){cout<<arr[i]<<" ";}cout<<endl;return 0;}

热点排行

编程

算法导论第七章题解——插入排序