c++ - 我的排序算法的时间复杂度是多少？

Question

它类似于带交换的插入排序，并且适用于三个标准。例如，如果用户输入 1、2、3，则优先顺序是按高度排序，然后是体重，最后是年龄。我也有比较器。问题是我不确定时间复杂度。会是 O(n^2) 吗？如果是，谁能解释为什么？ Ofc 我说的是最坏的情况。

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;
}   
}

Answer 1

是的，正如您在问题中所述，这是一种二次排序算法。推理是这样的:

代码的主要部分运行一个嵌套循环如下:

for(int i = 1; i < n; i++) {
   int j = i-1
   while (j >= 0...

您在内部循环中进行持续工作的地方。

在最坏的情况下，对于外层循环的每次迭代，内层循环迭代 i 次。这将创建以下著名序列:1 + 2 +...+ n-1 + n，等于 n * (n+1)/2。在 Big O 术语中，这是 O(n^2)。