我的排序算法的时间复杂度是什么？

Question

这类似于交换排序，有三个标准。例如，如果用户输入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;
}   
}

- Filgum0326

---

你说这个算法“类似于插入排序”，但它似乎与维基百科上插入排序的伪代码完全相同：https://en.wikipedia.org/wiki/Insertion_sort#Algorithm。你认为这是因为你使用了比较器而不仅仅是`<=`吗？排序的时间复杂度计算比较次数，无论它们是什么或者多么复杂。 - Paul Hankin

这不是你的问题，但 C++ 标准库中的 std::sort 允许你指定一个比较器，并且使用标准库的排序很可能比手写的排序更有效率。 - Paul Hankin

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。在大O表示法中，这是O(n^2)。

- user1984