C++习题-快速排序

2020年1月17日 1175点热度 0人点赞 0条评论

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 

提示:

参考答案:

解锁文章

没有看到答案?微信扫描二维码可免费解锁文章

微信扫描二维码解锁

使用微信扫描二维码打开广告页面后可以立即关闭,再刷新此页面即可正常浏览此文章

所跳转广告均由第三方提供,并不代表本站观点!

已经扫描此二维码?点此立即跳转

code

这个人很懒,什么都没留下

文章评论