快速排序解决次序选择问题

次序选择问题

对于给定的n个元素的数组a[1..n]，要求从中找出第k小的元素。

【输入样例】

a={20, 43, 32, 67 ,48, 89, 36, 47, 15}

k=3

【输出样例】

算法设计描述

采用快速排序的基本思路是通过递归地将数组划分成小于基准元素和大于基准元素的两个子数组，最终找到第k小的元素。

快速排序的本质就是通过特定的算法将一段无序的数列分割成独立的两部分，再对这两部分采用同样的算法递归处理，最终使得序列有序。具体实现时，我们可以取序列中任意一个元素作为媒介，并把比其小的数字放在这个元素左边，把比其大的数字放在右边。

由于可以选取任意的元素作为媒介，所以快速排序就有了很多种不同的类型。其中比较常见的就是把中间元素或第一个元素作为媒介。在本次实验中，我采用的是将第一个元素作为媒介的方式。

思路优化

分治算法：可以取序列中任意一个元素作为媒介，并把比其小的数字放在这个元素左边，把比其大的数字放在右边。

如果右边的数字个数等于k，那么选取的这个元素就是答案；

如果右边的数字个数大于k，则答案在右边，对右边递归；

如果右边的数字个数小于k，则答案在左边，对左边递归。

void quick_sort(int l,int r)//升序排列 
//取序列中第一个元素作为媒介，并把比其小的数字放在这个元素的相对左边，把比其大的数字放在相对右边。
{
	int i=l,j=r,key=a[i];//存储媒介 
	while(i<j)//只要两个指针还没有相遇就继续执行检索交换的操作 
	{
		while(i<j&&a[j]>=key)j--;//倒序遍历，只要媒介后的数比媒介值大（说明符合要求，就往前移动，不执行任何操作） 
			a[i]=a[j];//遇到比媒介小的数就交换这两个数，此时j的值为被交换元素的数组下标
		while(i<j&&a[i]<=key)i++;//正序遍历，只要媒介后的数比媒介值小（说明符合要求，就往后移动，不执行任何操作） 
			a[j]=a[i];//遇到比媒介值大的数就交换这两个数，此时i的值为被交换元素的数组下标
	}
	a[i]=key;//在上述遍历过程中，a[i]的值是其他元素的复制，而媒介值丢失，所以此处应该重新把媒介的值复制给a[i]
	if(l<r)//只要左边界小于右边界（即该区间内至少有两个元素）就继续递归执行快排
	{
		quick_sort(l,i-1);//左半边快排 
		quick_sort(j+1,r);//右半边快排 
	}
}

由于每一遍的检索遍历完成的只是针对媒介的左右有序，所以需要递归执行媒介两边的排序过程，每次递归过程再分别确定媒介进而进行快速排序。

手绘快速排序的具体思路分析

完整求解代码如下：

#include<bits/stdc++.h>
using namespace std;
int a[1000005],n,t;
int  quick_sort(int l,int r,int k)
{
    int i=l,j=r,key=a[i];
    while(i<j)
    {
    while(i<j&&a[j]>=key)j--;
    a[i]=a[j];
    while(i<j&&a[i]<=key)i++;
    a[j]=a[i];
    }
    a[i]=key;
    if(l<r)
    {
        if(i-l+1==k)
        {
            return key;
        }
        else if(i-l+1>k)
            return quick_sort(l,i-1,k);
        else return quick_sort(i+1,r,k-(i-l+1));
    }
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int k;
	cin>>k;
    cout<<quick_sort(1,n,k); 
 return 0;
}