第九届蓝桥杯第五题：快速排序

心已赠人 2022-11-18 04:57 206阅读 0赞

# 快速排序介绍 #

[快速排序解释  
][Link 1]

# 题目 #

#include <stdio.h>
    
    int quick_select(int a[], int l, int r, int k) { 
    	int p = rand() % (r - l + 1) + l;
    	int x = a[p];
    	{ int t = a[p]; a[p] = a[r]; a[r] = t;}
    	int i = l, j = r;
    	while(i < j) { 
    		while(i < j && a[i] < x) i++;
    		if(i < j) { 
    			a[j] = a[i];
    			j--;
    		}
    		while(i < j && a[j] > x) j--;
    		if(i < j) { 
    			a[i] = a[j];
    			i++;
    		}
    	}
    	a[i] = x;
    	p = i;
    	if(i - l + 1 == k) return a[i];
    	if(i - l + 1 < k) return quick_select( _____________________________ ); //填空
    	else return quick_select(a, l, i - 1, k);
    }
    	
    int main()
    { 
    	int a[] = { 1, 4, 2, 8, 5, 7, 23, 58, 16, 27, 55, 13, 26, 24, 12};
    	printf("%d\n", quick_select(a, 0, 14, 5));
    	return 0;
    }

# 说明 #

根据快速排序和题目的说明  
if（i-l+1==k)就是基准线为第k个最小值的情况  
if (i - l + 1 < k)就是基准线小于第k个最小值，也就是说整个数组第k最小值在基准线右边没有分类的大数里面  
else 就是说基准线大于第k个最小值，也就是说整个数组第k最小值在基准线左边没有分类的小数里面

然后由此可得前几个参数为 a,i+1,r,  
根据快速排序的原理基准线左边的数一定小于右边的数，所以整个组数中第k个最小值在当前基准线的右部分，而前面k-1个(下标i+1个)最小值在右边，所以对于右边这个子数组而言，整个数组的第k个最小值，应当是其第k-（i-l+1)个最小值。

答案：a, i+1, r, k-(i-l+1)

[Link 1]: https://blog.csdn.net/qq_40941722/article/details/94396010?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522161818768416780264086152%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=161818768416780264086152&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-94396010.first_rank_v2_pc_rank_v29&utm_term=%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F