因为快速选择算法是基于快速排序算法改进而来，并且两个算法的作者都是Tony Hoare。所以在讲解快速选择算法前先介绍下快速排序算法。

快速排序

快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用。快速排序采用了分治的策略，该方法基本思想如下：

1. 先从要排序数组中取出一个数为基准数
2. 将数组中小于基准数的数放在基准数左边，大于基准数的数放在数组右边
3. 对基准数左右两边数组重复步骤1、2，直到每个区间只有一个数

快速排序算法示例

  CSDN博主elma_tww对快排的过程进行了详细的讲解，在此搬运其例子进行快排过程的示意。
  例如有一需要排序的数组为：23,45,17,11,13,89,72,26,3,17,11,13（从小到大排序）
  选取数组第一个数23为基准数，存入temp变量中，从数组的左右两边界向中间进行遍历，定义两个指针 i 和 j，i 最开始指向数组的第一个元素，j 最开始指向数组的最后一个元素。
  指针 i 从左向右移动，指针 j 从右向左移动。先移动 j 指针（从右忘左移），当 j 指向的数大于基准数时，略过，j 继续往左移动，直到遇到小于等于基准数的数arr[j]，将arr[j]填入arr[i]中；再移动 i 指针，当 i 指向的数小于等于基准数时，略过，i 继续往右移动，直到遇到不比基准数小的数arr[i]，将arr[i]填入arr[j]中；再移动 i 指针，再移动 j 指针...(轮换移动)，直到 i 和 j 指针相遇，此时将temp（基准数）填入arr[i]中即完成算法的第2个步骤。
  接下来分别将基准数左边和右边的数组按照以上方法进行聚合，直到每个子集只有一个元素，即排序完成。
图例

i将数组第一个数23赋给temp变量，指针 i 指向数组第一个元素，指针 j 指向数组最后一个元素
从 j 开始遍历（从右往左），遇到13时，因为13<=temp，因此将arr[j]填入arr[i]中，即此时指针 i 指向的数为13
再从 i 遍历（从左往右），遇到45时，因为45>temp，因此将arr[i]填入arr[j]中，此时指针 j 指向的数为45
继续从 j 遍历，遇到11时，因为11<=temp，因此将arr[j]填入arr[i]中，即此时指针 i 指向的数为11
从 i 遍历，遇到89时，因为89>temp，因此将arr[i]填入arr[j]中，此时指针 j 指向的数为89
从 j 遍历，遇到17时，因为17<=temp，因此将arr[j]填入arr[i]中，即此时指针 i 指向的数为17
从 i 遍历，遇到72时，因为72>temp，因此将arr[i]填入arr[j]中，此时指针 j 指向的数为72
从 j 遍历，遇到3时，因为3<=temp，因此将arr[j]填入arr[i]中，即此时指针 i 指向的数为3
从 i 遍历，遇到26时，因为26>temp，因此将arr[i]填入arr[j]中，此时指针 j 指向的数为26
从 j 遍历，和 i 重合
将 temp（基准数23）填入arr[i]中
  此时已经完成步骤2，接下来就是对基准数（即23）两边的区间用上述方法进行排序，直到每个区间只有一个元素。

快速排序代码实现

void quickSort(vector<int>&  arr, int begin, int end, int baseNumIndex)
{
          if(begin < end)
          {
              int baseNum = arr[baseNumIndex];
              int i = begin;
              int j = end;
              while(i < j)
              {
                      while(i < j && arr[j] > baseNum)
                      {
                            j--;
                      }
                      arr[i] = arr[j];
                      while(i < j && arr[i] < baseNum)
                      {
                            i++;
                      }
                      arr[j] = arr[i];
               }
               arr[i] = baseNum;
               quickSort(arr, begin, i-1, (i-1+begin)/2);
               quickSort(arr, i+1, end, (end+i+1)/2);
          }
}

快速排序特点

1. 快速排序的时间主要耗费在划分操作上，对长度为k的区间进行划分，共需k-1次关键字的比较
2. 最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。时间复杂度为O(n^2)
3. 在最好情况下，每次划分所取的基准都是当前无序区的"中值"记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数：O(nlogn)
4. 尽管快速排序的最坏时间为O(n*n)，但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名。它的平均时间复杂度为O(nlogn)

快速选择算法

快速选择算法通常用于解决TopK问题，什么是TopK问题呢，就是从数组中选出第K小或第K大的元素。假设我们要寻找TopK大，我们甚至不需要一个排序的数组，只要arr[n-k]左边是小于arr[n-k]的值，arr[n-k]右边是大于arr[n-k]的值，那么arr[n-k]就是我们要寻找的TopK。和快速排序算法一样，算法开始时选定一个基数，并将其分成左右两部分。和快排不同的是，快速选择并不对左右两部分子数组都进行递归，而只对寻找的的目标所在的子数组进行递归。也正因如此，快速选择算法将平均时间复杂度从O(nlogn)降到O(n），而最坏情况下时间复杂度为O(n^2)。

快速选择算法步骤（以TopK大为例）

1. 随机产生一个基数
2. 利用相应的划分算法将基数放到相应的位置。使得小于基数的在其左边，大于基数的在其右边
3. 比较pos和N-K以决定在哪边继续进行递归处理

快速选择算法示例

快速选择算法要点在于划分算法和选择需要递归的子数组。下面对划分算法进行图解示例

划分算法图解

在数组[3,2,1,5,6,4]中寻找第2大的元素（以第一次划分为例）

随机选择基数 将基数与区间末尾的数调换 定义save和i指针，并查看i指针所对应的数是否小于等于基数。若小于基数则调换两数位置并且两个指针均向前加一 2小于3，执行交换操作并且两个指针都加一 1小于3，同样执行上述操作 5大于3，save不变，i++ 6大于3，同上 i指向基数，将基数和save指针位置的数进行交换 完成划分

上述即使是划分算法的过程。当划分完毕后若基数所在位置大于k，则对基数左边区域进行划分操作，反之则对右边区域进行划分操作，直到基数所在位置等于k。

下面是Leetcode官方对快速选择算法完整过程的示例 leetcode官方快速选择算法图示

快速选择算法代码

//用于数组两个位置之间数据交换
void swap(vector<int>& arr, int a, int b)
{
      int temp = arr[b];
      arr[b] = arr[a];
      arr[a] = temp;
}

//划分算法
//返回基数划分后所在的下标
int partition(int left, int right, int pivot_index, vector<int>& arr)
{
    int pivot = arr[pivot_index];
    swap(pivot_index, right) //将基数放置最后
    int save = left;
    
    for(int i = left; i <= right; i++)
    {
        if(arr[i] < pivot)
        {
             swap(save, i);
             save++;
        }
    }
    
    //将基数和save所指的数据交换
    swap(save, right);
    return save;
}

//快速选择
int quickSelect(int left, right, int k, vector<int>& arr)
{
     if(left == right)   //只有一个元素时
     {
          return arr[left]; //直接返回
      }
      int pivot_index = (right + left)/2;
      
      //进行划分
      pivot_index = partition(left, right, pivot_index, arr);
      
      if(k == pivot_index)
      {
          return arr[pivot_index];
      }
      if(k < pivot_index)
      {
          return quickSelect(left, pivot_index-1, k, arr);
      }
      
      return quickSelect(pivot_index+1, right, k, arr);
}

本文章相关图文转载了CSDN博主elma_tww快排的文章中的内容
原文链接：https://blog.csdn.net/elma_tww/article/details/86164674