快速法实现对下列关键码的排序:{72,11,13,17,19,71,23,94,16,105,68,2,3,4,5,7,23,29,73,31,37,41,52}
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/07 15:41:06
快速法实现对下列关键码的排序:{72,11,13,17,19,71,23,94,16,105,68,2,3,4,5,7,23,29,73,31,37,41,52}
快速法实现对下列关键码的排序:{72,11,13,17,19,71,23,94,16,105,68,2,3,4,5,7,23,29,73,31,37,41,52}
快速法实现对下列关键码的排序:{72,11,13,17,19,71,23,94,16,105,68,2,3,4,5,7,23,29,73,31,37,41,52}
//快排c++代码
/*基本思想是：通过一趟排序将要排序的数据分割成独立的两部分,
其中一部分的所有数据都比另外一部分的所有数据都要小,
然后再按此方法对这两部分数据分别进行快速排序,
整个排序过程可以递归进行,以此达到整个数据变成有序序列.*/
#include<iostream>
using namespace std;
//从小到大
int partition(int a[],int p,int r)
{
int x=a[r];//通常,拿最后一个值,作为预期的中间值
int middle=p;//记录“较小的一段数据”的最大下标.通常这个值在p和r的中间,故起名middle
for(int j=p;j<r;j++)
{
if(a[j]<x)
{
if(j!=middle)
{
int temp=a[middle];
a[middle]=a[j];
a[j]=temp;
}
middle++;
}
}
int temp=a[r];
a[r]=a[middle];
a[middle]=temp;
return middle;
}
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 array[]= {72,11,13,17,19,71,23,94,16,105,68,2,3,4,5,7,23,29,73,31,37,41,52};
QuickSort(array,0,22);
for(int i=0;i<=22;i++)
cout<<array[i]<<" ";
cout<<endl;
return 0;
}