免费做微商代理,网站优化 月付费,国外汽车配件网站模板,重庆企业网站推广策略题目#xff1a;
E 快速排序#xff1a;以下代码可以从数组a[]中找出第k小的元素。 它使用了类似快速排序中的分治算法#xff0c;期望时间复杂度是O(N)的。 请仔细阅读分析源码#xff0c;填写划线部分缺失的内容。
#include stdio.h
int quick_select(int a[],…题目
E 快速排序以下代码可以从数组a[]中找出第k小的元素。 它使用了类似快速排序中的分治算法期望时间复杂度是O(N)的。 请仔细阅读分析源码填写划线部分缺失的内容。
#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( _____________________________ ); //填空elsereturn 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;
}
注意只填写划线部分缺少的代码不要抄写已经存在的代码或符号。
分析
好久没见过快排了复习也没看过这里遇到了就简单说一下加深一下印象 快排是最快的通用内部排序算法。按照分治三步法 1划分问题将数组的各个元素重排后分为左右两个部分使得左边的任意元素都小于或等于右边的任意元素。 2递归求解把左右两边分别排序 3合并问题不用合并因为此时数组已经完全有序。 快排由于划分方式不同版本很多在这里这道题用的是随机数划分 int p rand() % (r - l 1) l;表示闭区间【l~r】的任意一个数。 先看参数的作用 这里的参数l表示左指针r表示右指针功能同快速排序一致 参数1a表示数组不变 参数2l表示左指针下标边界 参数2r表示右指针下标边界 参数4k表示选择第k小的元素
回到快速排序的各个指针的变化 l~i区间内都是比枢纽小的一共i-l1个元素 i1~r都是比枢纽大的 如果i-l1比k大说明要在l~i-1中找还是找第k个元素 如果i-l1比k小说明要在i1 ~r某个值中找这个值是多少呢要看还需要找到新一轮递归中找第多少小的元素这里新参数k就等于 原k减去当前一轮的l~i的个数 即k-(i-l1)
//#include stdio.h
#includebits/stdc.hint quick_select(int a[], int l, int r, int k)
{int p rand() % (r - l 1) l; //l~r之间的一个随机数int x a[p];//随机数a[p]的值{int t a[p]; //交换随机数a[p]和高位右边第一个数a[p] a[r];a[r] t;}int i l, j r; //i左指针 j右指针while(i j){while(i j a[i] x)i;// 最后ij 或者 a[i]xif(i j) //如果a[i]随机数x{a[j] a[i]; //选一个比x大的数 放到高位j--;}while(i j a[j] x)j--;// 最后ji 或者 a[i]xif(i j) //如果a[i]随机数x{a[i] a[j]; //选一个比x小的数 放到低位i;}}a[i] x;// p i;//这里改了p的值 说明会用到p,且p的值等于i的值if(i - l 1 k)return a[i];if(i - l 1 k)return quick_select(a,i1,r,k-(i-l1)); //填空elsereturn quick_select(a, l, i - 1, k);//a数组不变 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;
}
