找出数组中最大的三个元素

Question

Sample input: [141, 1, 17, -7, -17, -27, 18, 541, 8, 7, 7]

Sample output: [18, 141, 541]

我的代码

class Program {
     public static int[] findThreeLargestNumbers(int[] array) {
       int j = array.length;
       while(j>= array.length-3){
           for(int i = 0; i<j-1; i++){
               if(array[i]>=array[i+1]){
                   int temp = array[i];
                   array[i] = array[i+1];
                   array[i+1] = temp;
               }
           }
           j--;
       }
       int [] result = new int [3];
       result[0] = array[array.length-3];
       result[1] = array[array.length-2];
       result[2] = array[array.length-1];
       return result;
    }
}

我认为我可以进行“3”次冒泡排序，因为我只关心 3 个最大的元素然后退出。我知道传统的冒泡排序算法是 O(N^2)。但是，我修改后的算法是否具有更好的 O(N) 时间复杂度，因为我的 while 循环仅运行 3 次，而我的 for 循环运行 N 个元素使得 O(3N) 因此 O(N) ??

我只需要帮助理解这个问题的时间复杂度，而不是非常简单的解决方案。

Answer 1

是的，你是对的，你的算法进行了大约 3N 次比较并且具有 O(N) 的复杂性。

它比完全冒泡排序更好，因为算法只执行部分排序，其余部分保持未排序。

但请注意，对于固定个最大元素（此处为 3），复杂度是线性的。如果你需要 select 说 n/3 最大的 - 这种方法变成二次方的，你宁愿选择另一种部分排序（例如，基于 Quicksort 分区或二进制堆的算法）

找出数组中最大的三个元素

Find the three largest elements in an array

sorting

algorithm

big-o

bubble-sort

time-complexity