java - 改进的冒泡排序

Question

我需要编写一个算法，该算法将采用一个整数数组并找到数组中的第 k 个最大元素。这里需要注意的是，运行时间必须是 O(K*n) 或更好。

我的老师已经明确表示这可以通过修改冒泡排序程序来完成，但我不确定如何修改冒泡排序而不破坏它，因为我认为有必要循环遍历冒泡排序的每个元素大批。这是我的代码(只是程序的外壳和未经修改的冒泡排序):

public int kthLargest(int[] A, int k){

    int[] sorted = A;
    int temp;
    for (int i = (A.length - 1); i >= 0; i--)
       {
          for (int j = 1; j <= i; j++)
          {
             if (sorted[j-1] < sorted[j])
             {
                  temp = sorted[j-1];
                  sorted[j-1] = sorted[j];
                  sorted[j] = temp;
             }
          }
       }
    return sorted[k-1];
}

弄清楚了:

public int kthLargest(int[] A, int k){

    int[] sorted = A;
    int temp;
    for (int i = 0; i < A.length-1; i++)
       {
          for (int j = 0; j < A.length-i-1; j++)
          {
             if (sorted[j] > sorted[j+1])
             {
                  temp = sorted[j];
                  sorted[j] = sorted[j+1];
                  sorted[j+1] = temp;
             }
             if(i == (k-1)) return A[A.length-i-1];
          }
       }
    return sorted[A.length-k];

}

数组已排序到第 k 大元素，已找到要查找的内容，可以停止排序并返回。

Answer 1

我认为如果列表已经排序，修改后的冒泡排序就会提前退出？

这样的东西还不够吗？

public int kthLargest(int[] A, int k){
    int[] sorted = A;
    int temp;
    bool bSorted = TRUE;
    for (int i = (A.length - 1); i >= 0; i--)
    {
      for (int j = 1; j <= i; j++)
      {
         if (sorted[j-1] < sorted[j])
         {
              temp = sorted[j-1];
              sorted[j-1] = sorted[j];
              sorted[j] = temp;
              bSorted = FALSE;
         }
      }
      if(bSorted)
          break;
   }
   return sorted[k-1];
}