在计算一组基本信息元素的第k个值或前k个值时，可能首先考虑的是对元素进行排序，然后选择第k个值或前k个值。 但是，我们只是想取第k大的数。 是否有必须对整个元素组进行排序的情况？ 当然，这是我们介绍的快速选择算法，其时间复杂度可以达到o(n )。 它在一定程度上基于快速排序的思想。 在这里，假设需要寻找很多要素的中位数。
快速排序快速排序计算基本上是比较排序法中效果最好的，其时间复杂度为o(nlogn )。
快速排序步骤：
)1)首先设定边界值，根据该边界值将排列分为左右两部分。
)2)将边界值以上的数据收集到数组右边，将小于边界值的数据收集到数组左边。
(3)重复步骤(1) ) )2)，直到不能分割数据。
第一次排序：
以第一个数为边界值，从左向右找边界值大的数，从右向左找边界值小的数，如果边界值大的在小的左边，交换两个位置。 记录小于边界值的数量，最后将边界值放入对应的位置，完成第一次排序。 接下来，递归操作边界值的左边和右边的数量，直到排序完成。
递归排序：
代码如下。
templatetypenametstaticvoidqsort (tarr [ ]，int low，int high )//c； if(high=low ) return； int i=low； int j=high 1； int key=arr[low]； while(true ) (/*大于key的值)/while ) arr [ I ] key (if ) I==high ) ) { break； 小于}/*key的值*/while(arr(-j ) key ) ) if ) j==low ) { break； }if(I=j ) break； /*I，j对应的值*/int temp=arr[i]； arr[i]=arr[j]； arr[j]=temp； (/)交换中枢值和j对应值(*/int temp=arr[low]； arr[low]=arr[j]； arr[j]=temp； qsort(arr，low，j - 1 )； qort(ARR，j 1，high )； }选择算法在上述快速排序中，有一种选择算法，因为确定6的位置后需要查找中值，所以完全不需要对6右侧的数据进行排序。 与快速排序一样，递归分割输入数组。 与快速排序不同，快速排序选择递归处理分区的两侧，而只处理分区的一侧。
橙色是我们需要确定的中间位置的数量(中位数)，黄色是当前边界值的数量，也是比较交换后可以确定位置的数量。 每次确定位置的数量确定的位置处于中间位置时，其边界值的数量为中央值。
代码如下。
templatetypenamettselect (tarr [ ]，int low，int high，int m )//c； if(high=low ) { return -1； (} int i=low； int j=high 1； int key=arr[low]； while(true ) (/*大于key的值)/while ) arr [ I ] key (if ) I==high ) ) { break； 小于}/*key的值*/while(arr(-j ) key ) ) if ) j==low ) { break； }if(I=j ) break； /*I，j对应的值*/int temp=arr[i]； arr[i]=arr[j]； arr[j]=temp； (/)交换中枢值和j对应值(*/int temp=arr[low]； arr[low]=arr[j]； arr[j]=temp； if(jm ) ) MQsort(ARR，low，j - 1，m )； (if ) jm ) ) MQsort ) ARR，j 1，high，m )； (if ) j=m ) { return arr[j]； }选择了第k大的元素后，我们当然也有比第一个k大的数量。 因为k右边的数都大于k，k左边的数都小于k。