215题 求时间复杂度 （binary search + quick sort）

1.     public int findKthLargest(int[] A, int k) {
   
2. 
   
3.         k = A.length - k; // convert to index of k largest
   
4.         
   
5.         int L = 0;
   
6.         int R = A.length - 1; // 这把 R 当作 Pivot
   
7.         
   
8.         while (L <= R) {
   
9.             
   
10.             int i = L - 1;  
    
11.             
    
12.             for (int j = L; j <= R - 1; j++){
    
13.                
    
14.                 if (A[j] < A[R]) {
    
15.                      
    
16.                     i++;
    
17.                     swap(A, i, j);
    
18.                 }
    
19.             }
    
20.             
    
21.             ++i;
    
22.             swap(A, i, R);
    
23. 
    
24.             if (k < i) R = i - 1;
    
25.             else if (k > i) L = i + 1;
    
26.             else return A[i];
    
27.         }
    
28.         return -1; // k is invalid
    
29.     }
    
30.    
    
31.     public void swap(int[] nums, int i, int j){
    
32.         
    
33.         int tmp = nums[i];
    
34.         nums[i] = nums[j];
    
35.         nums[j] = tmp;
    
36.     }

复制代码

求大家分析下时间复杂度，感谢各位。
[/i][/i][/i]

应该是O(N)

pivot加个random可以当作On