首页 / 算法 / 快速排序(算法分析与设计)c++
快速排序(算法分析与设计)c++
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了快速排序(算法分析与设计)c++,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1533字,纯文字阅读大概需要3分钟。
内容图文
#include <iostream>
using namespace std;
void Swap(int a,int b) //a,b交换位置
{
int c=a;
a=b;
b=c;
}
int Partition(int a[],int p,int r)//Partition的作用是将基准元素置于本应在序列中的位置,
{ // 并保存该基准在数组中的下标(位置),还让其前面的元素
// 均小于该基准,后面的元素均大于该基准
int i=p,j=r+1; //i为基准位置,r为要排序的数组中最后一个元素下标
int x=a[p]; //x为选取的基准 ,p为基准未排序前在数组中的位置
while(true) // x
{ //数组a[p:r]: p,p+1,...,r-1, r
//对应i,j: i,i+1,...,j-2,j-1,j
while (a[++i]<x&&i<j-1);//跳出第一个while说明i前面的都<x,a[i]>=x或i=j-1
while(a[--j]>x); //跳出第二个while说明j后面的都>x,a[j]<=x
if(i>=j)break; //终止外层while循环的条件,若满足if条件说明跳出了前面两个while,
//且i>=j,说明j前面的都<x ,j后面的都>x,
//此时a[j]的位置j即为x本应在序列中的位置
Swap(a[i],a[j]); //若未终止外层循环,则说明i<j,将a[i] (>=x) 与 a[j] (<=x)互换位置
}
a[p]=a[j]; //将基准x置于本应在序列中的位置 (与该位置的元素交换位置)
a[j]=x;
return j; //返回基准位置
}
void Quicksort(int a[],int p,int r)
{
if(p<r)
{
int q=Partition(a,p,r); //将放a[p]到了自己本应在序列中的位置(与a[j]交换位置) ,
//并将该位置j赋值给q
Quicksort(a,p,q-1); //基准与位置为q的元素交换了位置,此时基准回到了自己的位置q
Quicksort(a,q+1,r); //剩下的位置p~q-1,q+1~r,与对应的元素并不匹配,继续换位置
}
}
int main(){
int n;
cin>>n; //数组元素个数
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
Quicksort(a,0,n-1); //对含有n个元素的数组a[0:n-1]快排
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
return 0;
}
内容总结
以上是互联网集市为您收集整理的快速排序(算法分析与设计)c++全部内容,希望文章能够帮你解决快速排序(算法分析与设计)c++所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。