快速选择排序 Quick select 解决Top K 问题

电玩女神 2022-04-12 13:26 146阅读 0赞

### 1. 思想 ###

Quick select算法通常用来在未排序的数组中寻找第k小/第k大的元素。  
   Quick select和Quick sort类似，核心是partition。

1. 什么是partition？（如下图，选44为pivot，把数组分为2部分，左边比44小，右边比44大）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlbmd5dXBlbmc_size_16_color_FFFFFF_t_70][]

从数组中选一个数据作为pivot，根据每个数组的元素与该pivot的大小将整个数组分为两部分：  
   左半部分，都比pivot大，右半部分，都比pivot小 。

2. 用分治思路实现排序

pivotIndex 是pivot在数组的下标

pivotIndex大于k，说明array\[pivotIndex\]左边的元素都大于k，只递归array\[0, pivotIndex-1\]第k大的元素即可；

pivotIndex小于k，说明第k大的元素在array\[pivotIndex\]的右边，只递归array\[pivotIndex +1, n\]第k-pivotIndex大的元素即可；

逻辑如下：

function quickSelect(list, left, right, k)
    
       if left = right
          return list[left]
    
       Select a pivotIndex between left and right
    
       pivotIndex := partition(list, left, right, 
                                      pivotIndex)
       if k = pivotIndex
          return list[k]
       else if k < pivotIndex
          right := pivotIndex - 1
       else
          left := pivotIndex + 1

### 2.code in java ###

import java.util.Arrays;
    
    public class QuickSelect {
    
        public static void main(String[] args) {
            int arr[] = {7, 10, 4, 3, 20, 15 };
    
            int pivotIndex = quickSelect(arr,4, 0, arr.length - 1 );
            System.out.println("pivotIndex="+pivotIndex);
        }
    
        
        private static int getPivotByPartition(int[] elements, int start, int end) {
            int pivot = start;
            int lessThan = start;
    
            for (int i = start; i <= end; i++) {
                int currentElement = elements[i];
                if (currentElement < elements[pivot]) {
                    lessThan++;
                    int tmp = elements[lessThan];
                    elements[lessThan] = elements[i];
                    elements[i] = tmp;
                }
            }
            int tmp = elements[lessThan];
            elements[lessThan] = elements[pivot];
            elements[pivot] = tmp;
            //System.out.println(" --- array = " +Arrays.toString(elements));
            return lessThan;
        }
        
        private static int quickSelect(int[] elements, int k, int start, int end) {
    
            int pivot = getPivotByPartition(elements, start, end);
    
            if (k == (pivot - start + 1)) {
                System.out.println("pivot value="+elements[pivot]);
                return pivot;
            } else if (k < (pivot - start + 1)) {
                return quickSelect(elements, k, start, pivot - 1);
            } else {
                return quickSelect(elements, k - (pivot - start + 1), pivot + 1, end);
            }
        }
    }

### 3. 分析 ###

与Quick sort不同的是，Quick select只考虑所寻找的目标所在的那一部分子数组，而非像Quick sort一样分别再对两边进行分  割。正是因为如此，Quick select将平均时间复杂度从O(nlogn)降到了O(n)

[最坏时间复杂度][Link 1]： О(n²)

[平均时间复杂度][Link 2]： О(n)

[最坏空间复杂度][Link 3]： О(n) total, O(1) auxiliary

### 4. 参考 ###

[https://www.geeksforgeeks.org/quickselect-algorithm/][https_www.geeksforgeeks.org_quickselect-algorithm]

[https://blog.csdn.net/wufaliang003/article/details/82940218][https_blog.csdn.net_wufaliang003_article_details_82940218]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlbmd5dXBlbmc_size_16_color_FFFFFF_t_70]: /images/20220412/07e2f50228fe45a1b2d96a4bb4ab9b71.png
[Link 1]: https://www.google.co.in/search?q=%E9%81%B8%E6%93%87%E6%8E%92%E5%BA%8F+%E6%9C%80%E5%9D%8F%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6&sa=X&ved=2ahUKEwj2iYfJtIPfAhVEvI8KHUXbAmsQ6BMoADAOegQIARAG
[Link 2]: https://www.google.co.in/search?q=%E9%81%B8%E6%93%87%E6%8E%92%E5%BA%8F+%E6%9C%80%E4%BC%98%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6&sa=X&ved=2ahUKEwj2iYfJtIPfAhVEvI8KHUXbAmsQ6BMoADAPegQIARAJ
[Link 3]: https://www.google.co.in/search?q=%E9%81%B8%E6%93%87%E6%8E%92%E5%BA%8F+%E6%9C%80%E5%9D%8F%E7%A9%BA%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6&sa=X&ved=2ahUKEwj2iYfJtIPfAhVEvI8KHUXbAmsQ6BMoADAQegQIARAM
[https_www.geeksforgeeks.org_quickselect-algorithm]: https://www.geeksforgeeks.org/quickselect-algorithm/
[https_blog.csdn.net_wufaliang003_article_details_82940218]: https://blog.csdn.net/wufaliang003/article/details/82940218