算法导论第7章—快速排序

本文主要是介绍算法导论第7章—快速排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

快速排序

#include<iostream>
using namespace std;void Print(int *A,int p,int r){for(int i=p;i<=r;i++)cout<<A[i]<<" ";cout<<endl;
}int Partition(int *A,int p,int r){int x=A[r];int i=p-1;for(int j=p;j<=r-1;j++){if(A[j]<=x){i++;swap(A[i],A[j]);}}swap(A[i+1],A[r]);return i+1;
}void QuickSort(int *A,int p,int r){if(p<r){int q=Partition(A,p,r);QuickSort(A,p,q-1);QuickSort(A,q+1,r);}
}int main(){int A[100];int p,r;cout<<"请输入p,q的值:";cin>>p>>r;cout<<"请输入数字：";for(int i=p;i<=r;i++)cin>>A[i];cout<<"快速排序前：";Print(A,p,r);cout<<"快速排序后：";QuickSort(A,p,r);Print(A,p,r);return 0;
}

随机化版本：

#include<iostream>
#include<ctime>
#include<cstdlib>
using namespace std;void Print(int *A,int p,int r){for(int i=p;i<=r;i++)cout<<A[i]<<" ";cout<<endl;
}int Partition(int *A,int p,int r){int x=A[r];int i=p-1;for(int j=p;j<=r-1;j++){if(A[j]<=x){i++;swap(A[i],A[j]);}}swap(A[i+1],A[r]);return i+1;
}int Randomized_Partition(int *A,int p,int r){srand(time(NULL));    //生成随机数int i=rand()%(r-p)+p;swap(A[r],A[i]);return Partition(A,p,r);
}
void Randomized_QuickSort(int *A,int p,int r){if(p<r){int q=Randomized_Partition(A,p,r);Randomized_QuickSort(A,p,q-1);Randomized_QuickSort(A,q+1,r);}
}int main(){int A[100];int p,r;cout<<"请输入p,q的值:";cin>>p>>r;cout<<"请输入数字：";for(int i=p;i<=r;i++)cin>>A[i];cout<<"快速排序前：";Print(A,p,r);	Randomized_QuickSort(A,p,r);cout<<"快速排序后：";Print(A,p,r);return 0;
}

这篇关于算法导论第7章—快速排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---