C++习题-快速排序
时间: 1ms 内存:128M
描述:
以某个数为标准,把比这个数大的都移到它的后面,比这个数小的都移到它的前面,这样它后面的任意一个数都比它前面的任意一个数大,再将这前后两组数再分别重复这一过程,最后就会得到有序的数列;补充:如果从大到小排列可以将比这个数大的都移到它的前面,比这个数小的都移到它的后面.快速排序从小到大排序算法描述:1)设置两个变量first、last,令first等于一组数的第一个数的下标,last等于一组数的最后一个数的下标;2)以某个数组元素作为关键数据(这里将这组数的第一个数作为关键数据),赋值给key,即key=A[first];3)从last开始向前搜索,即由后开始向前搜索(last--),找到第一个小于key的值A[last],将A[last]给A[first];4)从first开始向后搜索,即由前开始向后搜索(first++),找到第一个大于key的A[first],将A[first]给A[last];5)重复第3、4步,直到first=last,将key的值给a[first];6)将first两边的两组数分别再进行排序,重复1、2、3、4、5步;直到每组只剩一个数排序结束.现在,我们的题目来了...输入一组整数,将这组整数从小到大排列。部分代码已给定如下,只需要提交缺失的代码。#include <iostream>
using namespace std;
void Quicksort(int a[],int low,int high)
{
if(low>=high)
{
return;
}
int first=low;
int last=high;
int key=a[first];
while(first<last)
{
///////////////////////////////////////////////////////////////////
/*
请在该部分填写缺少的代码
*/
////////////////////////////////////////////////////////////////////
}
a[first]=key;
Quicksort(a,low,first-1);
Quicksort(a,last+1,high);
}int main()
{
int i,a[100],x,n=0;
cin>>n;
for(i=0; i<n; i++)
cin>>a[i];
Quicksort(a,0,n-1);
for(i=0; i<=n-1; i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}
输入:
输入n和n个整数
输出:
从小到大输出
示例输入:
10
2 1 3 5 4 6 8 7 9 10
示例输出:
1 2 3 4 5 6 7 8 9 10
提示:
参考答案(内存最优[1084]):
#include <stdio.h>
int main()
{
int i=0,d;
int a[10],b,c;
scanf("%d",&c);
for(i=0;i<c;i++)scanf("%d",&a[i]);
for(i=0;i<c-1;i++)
for(d=0;d<c-i-1;d++)
if(a[d]>a[d+1])
{
b=a[d+1];
a[d+1]=a[d];
a[d]=b;
}
for(i=0;i<c;i++)printf("%d ",a[i]);
return 0;
}
参考答案(时间最优[0]):
#include <iostream>
using namespace std;
void Quicksort(int a[],int low,int high)
{
if(low>=high)
{
return;
}
int first=low;
int last=high;
int key=a[first];
while(first<last)
{
while(first<last&&a[last]>=key)
--last;
a[first]=a[last];
while(first<last&&a[first]<=key)
++first;
a[last]=a[first];
}
a[first]=key;
Quicksort(a,low,first-1);
Quicksort(a,last+1,high);
}
int main()
{
int i,a[100],x,n=0;
cin>>n;
for(i=0; i<n; i++)
cin>>a[i];
Quicksort(a,0,n-1);
for(i=0; i<=n-1; i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}
题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。