为什么不能用快速排序?

P1104 生日

lxl2012 @ 2024-01-28 21:44:50

快速排序:

#include<bits/stdc++.h>
using namespace std;
int n;
struct student{
    int years,months,days,id;
    char name[20];
};
student a[110];
bool operator >(student s1,student s2){
    if(s1.years != s2.years) return s1.years > s2.years;
    if(s1.months != s2.months) return s1.months > s2.months;
    if(s1.days != s2.days) return s1.days > s2.days;
    return s1.id < s2.id;
}
bool operator <(student s1,student s2){
    if(s1.years != s2.years) return s1.years < s2.years;
    if(s1.months != s2.months) return s1.months < s2.months;
    if(s1.days != s2.days) return s1.days < s2.days;
    return s1.id > s2.id;
}
int randint(int l,int r){
    return rand() % (r - l + 1) + 1;
}
void quick(int l,int r){
    if(l >= r) return;
    int i = l,j = r;
    int s = randint(l,r);
    swap(a[l],a[s]);
    student tmp = a[l];
    while(i < j){
        while(i < j && a[j] > tmp) -- j;
        a[i] = a[j];
        while(i < j && a[i] < tmp) ++ i;
        a[j] = a[i];
    }
    a[i] = tmp;
    quick(l,i - 1);
    quick(i + 1,r);
}
int main(){
    cin>>n;
    for(int i = 1;i <= n;i ++){
        cin>>a[i].name>>a[i].years>>a[i].months>>a[i].days;
        a[i].id = i;
    }
    quick(1,n);
    for(int i = 1;i <= n;i ++){
        cout<<a[i].name<<endl;
    }
    return 0;
}

快速排序记录

#include<bits/stdc++.h>
using namespace std;
int n;
struct student{
    int years,months,days,id;
    char name[20];
};
student a[110];
bool operator >(student s1,student s2){
    if(s1.years != s2.years) return s1.years > s2.years;
    if(s1.months != s2.months) return s1.months > s2.months;
    if(s1.days != s2.days) return s1.days > s2.days;
    return s1.id < s2.id;
}
bool operator <(student s1,student s2){
    if(s1.years != s2.years) return s1.years < s2.years;
    if(s1.months != s2.months) return s1.months < s2.months;
    if(s1.days != s2.days) return s1.days < s2.days;
    return s1.id > s2.id;
}
void maopao(student *c,int n){
    for(int i = 1;i <= n - 1;i ++){
        bool b = true;
        for(int j = 1;j <= n - i + 1;j ++){
            if(*(c + j) < *(c + j - 1)){
                swap(*(c + j),*(c + j - 1));
                b = false;
            }
        }
        if(b){
            break;
        }
    }
}
int main(){
    cin>>n;
    for(int i = 1;i <= n;i ++){
        cin>>a[i].name>>a[i].years>>a[i].months>>a[i].days;
        a[i].id = i;
    }
    maopao(&a[0],n);
    for(int i = 1;i <= n;i ++){
        cout<<a[i].name<<endl;
    }
    return 0;
}

冒泡排序记录


by tder @ 2024-01-28 21:51:53

盲猜因为不稳定。


by __ryp__ @ 2024-01-28 21:52:37

@lxl2012 快速排序不稳定,可能交换两个相同元素的位置


by __ryp__ @ 2024-01-28 21:53:08

@lxl2012

(如果有两个同学生日相同,输入靠后的同学先输出)


by _O_v_O_ @ 2024-01-28 22:16:17

因为 rand 是伪随机

震惊,卡常毒瘤lxl居然不知道rand是伪随机


by lxl2012 @ 2024-01-30 20:10:05

@intirain @tder 我用了编号比较啊


by lxl2012 @ 2024-07-30 09:17:45

@_O_vO 还真是rand的问题 记录

#include<bits/stdc++.h>
using namespace std;
int n;
struct student{
    int years,months,days,id;
    char name[20];
};
student a[110];
bool operator >(student s1,student s2){
    if(s1.years != s2.years) return s1.years > s2.years;
    if(s1.months != s2.months) return s1.months > s2.months;
    if(s1.days != s2.days) return s1.days > s2.days;
    return s1.id < s2.id;
}
bool operator <(student s1,student s2){
    if(s1.years != s2.years) return s1.years < s2.years;
    if(s1.months != s2.months) return s1.months < s2.months;
    if(s1.days != s2.days) return s1.days < s2.days;
    return s1.id > s2.id;
}
void quick(int l,int r){
    if(l >= r) return;
    int i = l,j = r;
    student tmp = a[l];
    while(i < j){
        while(i < j && a[j] > tmp) -- j;
        a[i] = a[j];
        while(i < j && a[i] < tmp) ++ i;
        a[j] = a[i];
    }
    a[i] = tmp;
    quick(l,i - 1);
    quick(i + 1,r);
}
int main(){
    cin>>n;
    for(int i = 1;i <= n;i ++){
        cin>>a[i].name>>a[i].years>>a[i].months>>a[i].days;
        a[i].id = i;
    }
    quick(1,n);
    for(int i = 1;i <= n;i ++){
        cout<<a[i].name<<endl;
    }
    return 0;
}

by lxl2012 @ 2024-12-14 17:20:21

@_O_vO毒瘤是什么意思


|