UOJ Logo

NOI.AC

标签
暂无

关于快排的问题解决与解答:

2024-07-07 18:39:18 By nihaoll

对于正在学快排的新人,学时会遇见一个可怕的问题: 当我的中间量使用a[mid]时会发生错误! 对于这种情况,很多人都不知道为什么(这里只指新手) 那是为什么呢? 原来啊,当你使用a[mid]遍历时如果判断到a[mid]可能会和另一个大于(或小于)a[mid]的值交换,这样a[mid]的值就会变为另一个,那么在下一次遍历时a[mid]就会变成那个值 所以在使用快排时应该给a[mid]赋值到另一变量(一般来说用key) 错误代码如下:

#include <bits/stdc++.h>
using namespace std;
int a[1000000];
void xie(int n)
{
    int gap=n;
    int end=0;
    int tmp=0;
    while(gap>1)
    {
        gap/=2;
        for(int i=1;i<=n-gap-1;i++)
        {
            end=i;
            tmp=a[end+gap];
            while(end>=0)
            {
                if(tmp<a[end])
                {
                    a[end+gap]=a[end];
                    end-=gap;
                }
                else
                {
                    break;
                }
            }
            a[end+gap]=tmp;
        }
    }
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    xie(n);
    for(int i=1;i<=n;i++)
    {
        cout<<a[i]<<" ";
    }
}

正确代码如下

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N];
void quick(int left,int right)
{
    int i=left,j=right;
    int mid=a[(left+right)/2];
    while(i<=j)
    {
    while(a[i]<mid) i++;
    while(a[j]>mid)j--;
    if(i<=j)
    {
        swap(a[j],a[i]);
        i++;
        j--;
         }     
    }
    if(left<=j) quick(left,j);
    if(i<=right) quick(i,right);
}

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    quick(1,n);
    for(int i=1;i<=n;i++)
    {
        cout<<a[i]<<" ";
    }
 }
共 1 篇博客