这类似于交换排序,有三个标准。例如,如果用户输入1、2、3,则优先按身高、体重和年龄排序。我也有比较器。 问题在于我不确定时间复杂度。它会是O(n^2)吗?如果是,有人能解释一下为什么吗?当然,我在谈论最差情况。
struct Person{
string name;
float height; // 1
int weight; // 2
short int age; // 3
};
bool comparePeople(Person a, Person b, short int standardOne, short int standardTwo, short int standardThree )
{
if(standardOne == 1 ){
if( standardTwo == 2){
if (a.height != b.height)
return a.height < b.height;
if (a.weight != b.weight)
return a.weight < b.weight;
return (a.age < b.age);
}
else{ // 1,3,2
if (a.height != b.height)
return a.height < b.height;
if (a.age != b.age)
return a.age < b.age;
return (a.weight < b.weight);
}
}else if(standardOne == 2 ){
if( standardTwo == 1){
if (a.weight != b.weight)
return a.weight < b.weight;
if (a.height != b.height)
return a.height < b.height;
return (a.age < b.age);
}
else{
if (a.weight != b.weight)
return a.weight < b.weight;
if (a.age != b.age)
return a.age < b.age;
return (a.height < b.height);
}
}else if(standardOne == 3 ){
if( standardTwo == 1){
if (a.age != b.age)
return a.age < b.age;
if (a.height != b.height)
return a.height < b.height;
return (a.weight < b.weight);
}
else{ //3,2,1
if (a.age != b.age)
return a.age < b.age;
if (a.weight != b.weight)
return a.weight < b.weight;
return (a.height < b.height);
}
}
}
void sort(Person *GroupOne, short int standardOne, short int standardTwo, short int standardThree, int n){
for(int i = 1; i < n; i++) {
Person key = GroupOne[i];
int j = i - 1;
while (j >= 0 && comparePeople(GroupOne[j],GroupOne[j+1], standardOne, standardTwo, standardThree)) {
Person temp = GroupOne[j+1];
GroupOne[j+1] = GroupOne[j];
GroupOne[j] = temp;
j--;
}
GroupOne[j+1] = key;
}
}
std::sort
允许你指定一个比较器,并且使用标准库的排序很可能比手写的排序更有效率。 - Paul Hankin