java - 排序算法运行时间

Question

我编写了一个函数来按从旧到新的顺序对时间戳 (hh:mm:ss) 进行排序。我很想知道我的代码在最坏情况下的大致运行时间，但我不知道如何确定。

我粗略的猜测是 O(n-1)^2 因为嵌套的 for 循环。我是对的吗？

如果不是，那么有人可以确定我的代码在 Big O 表示法中的大致运行时间是多少？

public void sortTimeStamp(SortTime timestamps[])
{
    for(int i=0;i<timestamps.length-1;i++)
    {
        for(int j=0;j<timestamps.length-1;j++)
        {
            if(timestamps[j].hour > timestamps[j+1].hour)
            {
                swap_timestamps(timestamps, j);
            }
            else
            if(timestamps[j].hour == timestamps[j+1].hour)
            {
                if(timestamps[j].minutes > timestamps[j+1].minutes)
                {
                     swap_timestamps(timestamps, j);
                }
                else
                if(timestamps[j].minutes == timestamps[j+1].minutes && timestamps[j].seconds > timestamps[j+1].seconds)
                {
                    swap_timestamps(timestamps, j);
                }

            }
        }
    }
}

交换函数

public void swap_timestamps(SortTime timestamps[], int index)
    {
        SortTime temp = timestamps[index];
        timestamps[index] = timestamps[index+1];
        timestamps[index+1] = temp;
    }

Answer 1

我觉得这个排序算法是O(n^2)。
你的答案是 O((n-1)^2)，它等于 O(n^2-2n+1)。
但是大 O 符号 O(f(n)) 的意思是“时间大约与 f(n) 成正比”(不完全正确，但很容易理解)
因此，您不必考虑 -2n 或 1 项。
您可以只考虑 n^2 项，不需要任何系数。

但是你可以做合并排序，时间复杂度是 O(n log n)
计数排序是可以的，因为 hh:mm:ss 只能表示 86400 种方式。它完成 O(n+k)，其中 k=86400。