算法设计与分析线性时间选择讲解文档

《算法设计与分析》实验指导书本书是为配合《算法分析与设计实验教学大纲》而编写的上机指导，其目的是使学生消化理论知识，加深对讲授内容的理解，尤其是一些算法的实现及其应用，培养学生独立编程和调试程序的能力，使学生对算法的分析与设计有更深刻的认识。

上机实验一般应包括以下几个步骤：（1）、准备好上机所需的程序。

手编程序应书写整齐，并经人工检查无误后才能上机。

（2）、上机输入和调试自己所编的程序。

一人一组，独立上机调试，上机时出现的问题，最好独立解决。

（3）、上机结束后，整理出实验报告。

实验报告应包括：题目、程序清单、运行结果、对运行情况所作的分析。

本书共分阶段4个实验，每个实验有基本题和提高题。

基本题必须完成，提高题根据自己实际情况进行取舍。

题目不限定如下题目，可根据自己兴趣爱好做一些与实验内容相关的其他题目，如动态规划法中的图象压缩，回溯法中的人机对弈等。

其具体要求和步骤如下：实验一分治与递归（4学时）一、实验目的与要求1、熟悉C/C++语言的集成开发环境；2、通过本实验加深对递归过程的理解二、实验内容：掌握递归算法的概念和基本思想，分析并掌握“整数划分”问题的递归算法。

三、实验题任意输入一个整数，输出结果能够用递归方法实现整数的划分。

四、实验步骤1．理解算法思想和问题要求；2．编程实现题目要求；3．上机输入和调试自己所编的程序；4．验证分析实验结果；5．整理出实验报告。

一、实验目的与要求1、掌握棋盘覆盖问题的算法；2、初步掌握分治算法二、实验题：盘覆盖问题：在一个2k×2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。

在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。

三、实验提示void chessBoard(int tr, int tc, int dr, int dc, int size) {if (size == 1) return;int t = tile++, // L型骨牌号s = size/2; // 分割棋盘// 覆盖左上角子棋盘if (dr < tr + s && dc < tc + s)// 特殊方格在此棋盘中chessBoard(tr, tc, dr, dc, s);else {// 此棋盘中无特殊方格// 用t 号L型骨牌覆盖右下角board[tr + s - 1][tc + s - 1] = t;// 覆盖其余方格chessBoard(tr, tc, tr+s-1, tc+s-1, s);}// 覆盖右上角子棋盘if (dr < tr + s && dc >= tc + s)// 特殊方格在此棋盘中chessBoard(tr, tc+s, dr, dc, s);else {// 此棋盘中无特殊方格// 用t 号L型骨牌覆盖左下角board[tr + s - 1][tc + s] = t;// 覆盖其余方格chessBoard(tr, tc+s, tr+s-1, tc+s, s);}// 覆盖左下角子棋盘if (dr >= tr + s && dc < tc + s)// 特殊方格在此棋盘中chessBoard(tr+s, tc, dr, dc, s);else {// 用t 号L型骨牌覆盖右上角board[tr + s][tc + s - 1] = t;// 覆盖其余方格chessBoard(tr+s, tc, tr+s, tc+s-1, s);}// 覆盖右下角子棋盘if (dr >= tr + s && dc >= tc + s)// 特殊方格在此棋盘中chessBoard(tr+s, tc+s, dr, dc, s);else {// 用t 号L型骨牌覆盖左上角board[tr + s][tc + s] = t;// 覆盖其余方格chessBoard(tr+s, tc+s, tr+s, tc+s, s);}}一、实验目的与要求1、熟悉二分搜索算法；2、初步掌握分治算法；二、实验题1、设a[0:n-1]是一个已排好序的数组。

快速选择算法线性时间选择第k小的元素快速选择算法：线性时间选择第k小的元素快速选择算法是一种高效的算法，用于在未排序的数组中选择第k 小的元素。

该算法的时间复杂度为O(n)，在大规模数据处理和排序任务中具有广泛的应用。

1. 算法原理快速选择算法基于快速排序算法的分治思想，通过每次选择一个枢纽元素，并将数组中的元素分为左右两部分，来实现快速查找排序后的第k小元素。

具体步骤如下：- 选择枢纽元素：从未排序数组中选择一个元素作为枢纽元素，可以随机选择或选择固定位置的元素，比如选取数组的第一个元素。

- 划分数组：将数组分为两部分，左边的元素小于枢纽元素，右边的元素大于等于枢纽元素。

- 判断位置：比较枢纽元素的位置与k的大小关系，如果位置小于k，则递归在右半部分查找第k小元素；如果位置大于k，则递归在左半部分查找第k小元素；否则，返回该位置的元素即为第k小元素。

2. 算法步骤下面给出一种实现快速选择算法的伪代码：```function quickSelect(A, k, left, right):if left == right:return A[left]pivotIndex = partition(A, left, right)if k == pivotIndex:return A[k]else if k < pivotIndex:return quickSelect(A, k, left, pivotIndex - 1) else:return quickSelect(A, k, pivotIndex + 1, right) function partition(A, left, right):pivot = A[left]i = left + 1j = rightwhile i <= j:if A[i] < pivot and A[j] > pivot:swap A[i] and A[j]i = i + 1j = j - 1if A[i] >= pivot:i = i + 1if A[j] <= pivot:j = j - 1swap A[left] and A[j]return j```3. 算法性能分析快速选择算法通过每次划分数组来减小搜索范围，因此平均时间复杂度为O(n)，其中n为数组的长度。

算法：线性时间选择（CC++）Description给定线性序集中n个元素和⼀个整数k，n<=2000000，1<=k<=n，要求找出这n个元素中第k⼩的数。

Input第⼀⾏有两个正整数n,k. 接下来是n个整数（0<=ai<=1e9）。

Output输出第k⼩的数Sample Input6 31 3 52 4 6Sample Output3利⽤快速排序可以找出第k⼩的，加上随机函数改进⼀下：#include <cstdio>#include <cstdlib>#include <ctime>#include <iostream>int num[2000001];void quictSort(int, int, int);int partition(int, int);int main(){int n, m, i;srand(unsigned(time(NULL))); // 随机函数种⼦while (~scanf("%d%d", &n, &m)){for (i = 0; i < n; i++)scanf("%d", &num[i]);quictSort(0, n - 1, m - 1);printf("%d\n", num[m - 1]);}return 0;}// 快速排序void quictSort(int left, int right, int mTop){if (left < right){int p = partition(left, right); // 分为两段if (p == mTop) // 如果随机找到第mTop⼩就直接返回return;if (p < mTop)quictSort(p + 1, right, mTop); // 找到的位置⽐mTop⼩就在[p + 1, right]区间找if (p > mTop)quictSort(left, p - 1, mTop); // 找到的位置⽐mTop⼤就在[left, p - 1]区间找}}// 从⼩到⼤排int partition(int left, int right){int r = rand() % (right - left + 1) + left; // 随机选择⼀个数int key = num[r];std::swap(num[r], num[left]); // 交换到数组⾸位while (left < right){// 从数组后⾯开始, 找⽐随机选择的数⼩的, 然后从前找⽐随机选择的数⼤的while (left < right && num[right] >= key)right--;if (left < right)num[left] = num[right];while (left < right && num[left] <= key)left++;if (left < right)num[right] = num[left];}num[left] = key; // 将随机选择的数存回return left; // 返回随机选择的数分割数组的下标, 左边都是⽐它⼩的, 右边都是⽐它⼤的}中位数法线性时间选择划分：AC代码：#include <cstdio>#include <cstdlib>int num[2000001];int select(int low, int high, int top);int partition(int low, int high, int median); void selectSort(int low, int high);void swap(int &a, int &b);int main(){int n, m, i;while (~scanf("%d%d", &n, &m)){for (i = 0; i < n; i++)scanf("%d", &num[i]);printf("%d\n", select(0, n - 1, m - 1));/*for (i = 0; i < n; i++)printf("%d%c", num[i], i < n - 1 ? ' ' : '\n'); */}return 0;}// 中位数法线性时间选择int select(int low, int high, int top){// ⼩于75个数据随便⽤⼀个排序⽅法if (high - low < 74){selectSort(low, high); // 选择排序return num[low + top]; // 排完序直接返回第low + top的数}int groupNum = (high - low - 4) / 5; // 每组5个数, 计算多少个组, 从0开始计数for (int i = 0; i <= groupNum; i++){int start = low + 5 * i; // 每组的起始位置int end = start + 4; // 每组的结束位置for (int j = 0; j < 3; j++) // 从⼩到⼤冒3个泡for (int k = start; k < end - j; k++)if (num[k] > num[k + 1])swap(num[k], num[k+1]);swap(num[low + i], num[start + 2]); // 每组的中位数交换到前⾯第low + i的位置}// 上⾯排完后, 数组low + 0 到 low + groupNum都是每⼀组的中位数int median = select(low, low + groupNum, (groupNum + 1) / 2); // 找中位数的中位数int p = partition(low, high, median); // 将数组分为两段, 左边的⼩于中位数的中位数, 右边的⼤于中位数的中位数 int n = p - low; // 计算p到low之间有多少个数, 后⾯得减掉if (n == top)return num[p]; // 如果运⽓好, 刚好要找的就是中位数if (n > top)return select(low, p - 1, top); // n⽐top⼤就在左边找if (n < top)return select(p + 1, high, top - n - 1); // n⽐top⼩就在右边找, 并且top要减去已经⼤的个数}// 以中位数进⾏分割, 分成两半int partition(int low, int high, int median){int p;for (int i = low; i <= high; i++)if (num[i] == median){p = i;break;}// 将中位数交换到最前⾯swap(num[p], num[low]);// 记下最前⾯的数int key = num[low];// 把⼩于key的放前⾯, ⼤于key的放后⾯while (low < high){while (num[high] >= key && low < high)high--;if (low < high)num[low] = num[high];while (num[low] <= key && low < high)low++;if (low < high)num[high] = num[low];}// 分别从两头开始, 找到中间时, 把key存回num[low] = key;return low;}// 选择排序void selectSort(int low, int high){for (int i = low; i <= high; i++){int MIN = i;for (int j = i + 1; j <= high; j++)if (num[MIN] > num[j])MIN = j;swap(num[i], num[MIN]);}}// 交换两个元素void swap(int &a, int &b){int temp = a;a = b;b = temp;}。

线性时间选择I.问题描述给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素，即如果将这n个元素依其线性序排列时，排在第k个位置的元素即为要找的元素。

当k=1时，就是要找的最小元素；当k=n时，就是要找最大元素；当k=（n+1）/2时，称为找中位数。

II.问题分析在线性序集n个元素中找出第k小的元素，可以采用分治策略的思想。

模仿前面的随机选择策略的快速排序算法，对输入的数组进行递归划分。

与快速排序算法不同的是，它只对划分的子数组之一进行递归处理。

在算法RandomizedSelect中执行Randomized_Partition后，数组a[p:r]被划分成两个子数组a[p:i]和a[i+1:r],使a[p:i]中每个元素都不大于a[i+1:r]中每个元素。

接着算法计算子数组a[p:i]中元素个数j。

如果k≤j,则a[p:r]中第k小元素落在子数组a[p:i]中。

如果k>j,则要找的第k小元素落在子数组a[i+1:r]中。

由于此时已知道子数组a[p:i]中元素均小于要找的第k小元素，因此，要找的a[p:r]中第k小元素是a[i+1:r]中的第k-j小元素。

算法复杂性分析：容易看出，在最坏情况下，算法RandomizedSelect需要O（n^2）计算时间，例如，在找最小元素时，总是在最大元素处划分。

但是，该算法的平均时间复杂度为O（n）。

III.算法描述RandomizedSelect（A,p,r,i）//找出第k小元素函数if p==r //数组中只有一个数return A[p]q=Randomized_Partition(A,p,r)// 调用随机划分函数，即同前面的随机选择策略的快速排序k=q-p+1if i==kreturn A[q]else if i<kreturn RandomizedSelect(A,p,q-1,i) //在左半段找第k小元素else return RandomizedSelect(A,q+1,r,i-k) //在右半段找第k小元素Randomized_Partition(A,p,r) //随机划分函数i=Random(p,r)exchange A[r] with A[i]return Partition(A,p,r)Partition（A,p,r）//快速排序函数x=A[r]i=p-1for j=p to r-1if A[j]≤xi=i+1exchange A[i] with A[j]exchange A[i+1] with A[r]return i+1IV.程序用C++描述如下：#include <iostream>using namespace std;int RandomizedSelect(int array[], int begin, int end, int rank);int Randomized_Partition(int a[],int p,int r);void Randomized_QuickSort(int a[],int p,int r);int Partition(int a[],int p,int r);void Swap(int &a,int &b);int RandomizedSelect(int array[], int begin, int end, int rank) //找出第k小元素函数{if (begin == end){return array[begin];}//随机选取一个基准元素,将数组按照基准元素值的大小分区,//基准元素的左侧都是比基准元素小的元素//基准元素的右侧都是比基准元素大的元素//返回分区后的基准元素的数组索引int q = Randomized_Partition(array, begin, end);//计算基准元素的数组排位int k = q - begin + 1;if (rank == k){//分区的基准元素刚好是排在rank位置上, 则直接返回基准元素return array[q];}else if (rank < k){//分区的基准元素比rank大,转为在基准元素左面的区间中寻找return RandomizedSelect(array, begin, q - 1, rank);}else{//分区的基准元素比rank小,转为在基准元素右面的区间中寻找return RandomizedSelect(array, q + 1, end, rank - k);}}//实现随机功能的函数int Random(int p,int r){return rand()%(r-p+1)+p;}//随机划分函数int Randomized_Partition(int a[],int p,int r){//随机的从p至r中抽取一个数int i=Random(p,r);//将a[i]和a[p]交换Swap(a[i],a[p]);//调用划分函数return Partition(a,p,r);}//用于划分左右数组的函数//p为数组下界，r为上界int Partition(int a[],int p,int r){int i=p,j=r+1;int x=a[p];//将小于x的元素交换到左边区域//将大于x的元素交换到右边区域while(true){while((a[++i]<x)&&(i<r));while(a[--j]>x);if(i>=j) break;Swap(a[i],a[j]);}a[p]=a[j];a[j]=x;return j;}//用于实现数组成员交换的函数void Swap(int &a,int &b){int c;c=a;a=b;b=c;}void main(){int n,r,k;cout<<"线性时间选择"<<endl<<"请输入数组规模：";cin>>n;int *a=new int[n];cout<<"输入要排序的数："<<endl;for(int i=0;i<n;i++)cin>>a[i]; //输入待排序数组cout<<"请输入要找的第k小元素："<<endl;cin>>k;r=RandomizedSelect(a,0,n-1,k); //求第k小元素cout<<"第k小元素为："<<r<<endl;cout<<endl<<"END"<<endl;}。

《算法设计与分析》实验指导书《算法设计与分析》实验指导书本文档主要用于《算法设计与分析》课程的实验指导。

《算法设计与分析》旨在教会学生处理各种问题的方法，通过实验，使学生能够把所学的方法用于具体的问题，并对所用算法进行比较分析，从而提高学生分析问题、解决问题的能力。

通过该课程的实验，使学生对课堂中所讲述的内容有一个直观的认识，更好地掌握所学的知识，培养学生的实际动手能力，加强学生创新思维能力的培养。

本课程设计了7个设计型实验。

实验内容包括用分治法、动态规划、贪心法、回溯法以及分支限界法求解问题。

一、实验内容安排二、实验基本要求实验前要求学生一定要先了解实验目的、内容、要求以及注意事项，要求学生熟悉实验对象，设计并编写相应的算法。

学生应独立完成所布置实验内容，编写代码，运行程序，记录结果并撰写实验报告。

三、实验报告要求实验结束后，应及时整理出实验报告，实验报告提交书面文档。

四、考核方式理论考试（60％）＋实验（30％）+作业（10%）五、实验内容与指导实验一快速排序问题1．实验目的(1) 用分治法求解该问题。

2．实验环境PC机，要求安装Eclipse软件或VC++软件供学生实验。

3．实验内容有n个无序的数值数据，现要求将其排列成一个有序的序列。

4. 实验步骤(1) 输入实现该问题的源代码；(2) 输入测试数据，验证代码的正确性。

5.实验要求(1)做好实验预习，熟悉本实验中所使用的开发环境。

(2)写出实验报告①实验目的②实验内容③出错信息及处理方法④实验结果实验二最少硬币问题1．实验目的(1) 用动态规划求解该问题。

2．实验环境PC机，要求安装Eclipse软件或VC++软件供学生实验。

3．实验内容有n种不同面值的硬币，各硬币面值存于数组T[1:n]；现用这些面值的钱来找钱；各面值的个数存在数组Num[1:n]中。

对于给定的1≤n≤10，硬币面值数组、各面值的个数及钱数m，0<=m<=2001，设计一个算法，计算找钱m的最少硬币数。

算法分析线性时间选择复杂度分析第二组：袁瑾(计科1304：201308010410)，欧阳玉峰（计科1304:201308080216），程帆瑾（物联1302:201378010206）。

一、问题描述：给一个线性序列，要求在一个平均时间线性的情况下进行第k小元素的选择。

二、方法一：模仿快速排序的方法对输入序列进行递归划分，但只对划分出的子数组之一进行递归处理。

代码如下：RandomizedSelect(a, p, r, k):if p==r :return a[p]i = RandomizedPartition(a,p,r)j = i-p+1if k<=j :return RandomizedSelect(a,p,i,k)return RandomizedSelect(a,i+1,r,k-j)三、方法一时间复杂度：先从上边的函数说起。

其实质是模拟一个快速排序的过程。

快速排序是随机选择一个轴值，然后比轴值小的排在左边，比轴值大的排在右边。

上边的函数四个参数a,p,r,k。

a是数组的参数，p是数组开始元素的下标，r的数组结束的下标。

k是找第k小的元素。

每次划分所需要的时间是O(n),此时每个元素需要和轴值进行比较一次。

所以最好的情况是选完轴值一次快排后，左边刚好有k-1个元素，则此时轴值则是第k小元素。

而一般情况是，轴值左边有m个元素，m<k时，在右边找第k-m小的元素，m>k时，在左边找第k小的元素。

平均复杂度是O(n)。

最坏的情况是轴值每次选的都是刚好最大的元素或者最小的元素，此时时间复杂度是O(n*k)。

四.方法二：能在线性时间内找到一个划分基准，使得按照这个基准所划分出的两个子数组长度都至少为元数组长度的 m 倍：Select(a, p, r, k):if r-p<MG :sort(a[p:r])return a[p+k-1]for i in 0...(r-p-4)/5 :将a[p+5*i]...a[p+5*i+4]的第3小元素与a[p+i]交换x=Select(a,p,p+(r-p-4)/5,(r-p-4)/10)i=Partition(a,p,r,x)j=i-p+1if k<=j :return Select(a,p,i,k)return Select(a,i+1,r,k-j)五、算法及其复杂度分析：⌊3(n-5)/10⌋⌈n/5⌉<1> 将所有的数n个以每5个划分为一组共⌈n/5⌉组，将不足5个的那组忽略，然后用任意一种排序算法，因为只对5个数进行排序，所以任取一种排序法就可以了。

算法分析与设计实验报告第次实验(1)问题描述：给定任意几组数据，利用舍伍德型选择算法，找出数组中的中值并输出（若数组为奇数个则输出中值，若数组为偶数个则输出第 n/2 小元素）。

(2)设A是一个确定性算法，当它的输入实例为x时所需的计算时间记为tA(x)。

设Xn是算法A的输入规模为n的实例的全体，则当问题的输入规模为n时，算法A所需的平均时间为。

这显然不能排除存在x∈Xn使得的可能性。

希望获得一个随机化算法B，使得对问题的输入规模为n的每一个实例均有。

这就是舍伍德算法设计的基本思想。

当s(n)与tA(n)相比可忽略时，舍伍德算法可获得很好的平均性能。

(3)对于选择问题而言,用拟中位数作为划分基准可以保证在最坏的情况下用线性时间完成选择。

如果只简单地用待划分数组的第一个元素作为划分基准，则算法的平均性能较好，而在最坏的情况下需要O(n^2)计算时间。

舍伍德选择算法则随机地选择一个数组元素作为划分基准，这样既保证算法的线性时间平均性能，又避免了计算拟中位数的麻烦。

(4)用Select随机产生l和r之间的一个整数作为划分基准，对a[l:r]中n个元素进行划分时，第k小元素可能在低区子数组，或者刚好是划分基准，或者在较大的子数组中。

低区子数组含有一个元素的概率为2/n，含有i 个元素的概率为1/n,最坏情况是第k小元素总是被划分在较大的子数组中，此时在较大子数组中重新选择随机的划分基准，找出第k小元素。

(5)舍伍德算法属于概率算法，消除了运行时间和输入实例之间的联系。

测试结果如下图：附录：完整代码(建一个项目工程) //Sherwood.cpp#include "RandomNumber.h"#include <iostream>#include <iomanip>#include <time.h>#include <stdio.h>#include <time.h>using namespace std;const int INF = 9999;// 交换a, b的值template <typename Type>void Swap(Type &a, Type &b){Type temp;temp = a;a = b;b = temp;}template <typename Type>Type select(Type a[], int lt, int rt, int k){// 计算a[lt:rt]中第k小元素static RandomNumber rnd;while(true){if(lt > rt)return a[lt];int i = lt, j = lt+rnd.Random(rt-lt+1); // 随机选择的划分基准 Swap(a[i], a[j]);j = rt+1;Type pivot = a[lt];//以划分基准为轴作元素交换while(true){while(a[++i] < pivot);while(a[--j] > pivot);if(i >= j)break;Swap(a[i], a[j]);}if(j - lt + 1 == k)return pivot;a[lt] = a[j];a[j] = pivot;// 对子数组重复划分过程if(j - lt + 1 < k){k = k - j + lt - 1;lt = j + 1;}elsert = j - 1;}}template <typename Type>Type Select(Type a[], int n, int k){// 计算a[0: n-1]中第k小元素// 假设a[n]是一个键值无穷大的元素if(k < 1 || k > n)cerr << "Wrong!" << endl;return select(a, 0, n-1, k);}int main(){int i,j=0;double k=0.0;clock_t start,end,over;start=clock(); end=clock();over=end-start; start=clock();int arr[7] = {3, 2, 5, 7, 10, 4};for(i=0;i<6;i++){cout<<arr[i]<<" ";}cout<<endl;cout << "第4小的元素为："<<Select(arr, 6, 4) << endl;for(i=0;i<1000000000;i++)j=j+i;end=clock();printf("The time is %6.3f",(double)(end-start-over)/CLK_TCK);return 0;}//RandomNumber.h//RandomNumber.cpp。

经典算法总结之线性时间做选择问题：输⼊：⼀个包含n个(不同的)数的集合A和⼀个数i， 1 <= I <= n。

输出：元素x∈A，它恰⼤于A中其他的I – 1个元素（即求第k⼩数）。

本博⽂中这篇⽂章也⽤了本⽂中的算法，⼤家可以参考。

三种算法：1、直接排序，输出数组第i个元素即可, 时间复杂度为O(nlgn)2、这种算法，利⽤“快排的或者类似⼆分”的思想，每次以枢纽为界，分两边，每次只需处理⼀边即可（抛弃另⼀边），平均情况下的运⾏时间界为O(n)，这种算法以期望时间做选择。

《算法都论》⾥是，在分治时⽤随机数来选取枢纽（算法导论中伪代码见图），好吧，这是理论上的算法，它没有考虑实际产⽣随机数的开销，事实上，效率⼀点也不⾼，已经测试过，产⽣随机数花费的开销真的很⼤，后边我⽤更快的三数中值⼜实现了⼀遍，思想是⼀样的，只是效率提⾼了。

C++完整代码：#include <iostream>#include <vector>#include <algorithm>using namespace std;int partition(vector<int> &A,int p,int r){int x = A[r];int i=p-1;int temp;for(int j = p;j<r;++j){if(A[j]<=x){++i;swap(A[i],A[j]);}}swap(A[i+1],A[r]);return i+1;}inline int Random(int low, int high) {return (rand() % (high - low + 1)) + low;}int Randomized_Partition(vector<int> &kp, int low, int high) {int i = Random(low, high);swap(kp[high], kp[i]);return partition(kp, low, high);}void randomized_quickSort(vector<int> &A,int p,int r){if(p<r){int q = Randomized_Partition(A,p,r);randomized_quickSort(A,p,q-1);randomized_quickSort(A,q+1,r);}}int randomized_select(vector<int> A,int p,int r,int i){if(p==r)return A[p];if(p>r) return -1;int q = Randomized_Partition(A,p,r);int k = q-p+1;if(i==k)return A[q];else if(i<k)return randomized_select(A,p,q-1,i);else return randomized_select(A,q+1,r,i-k);}void main(){int a[10] = {9,10,8,7,6,5,4,3,2,1};vector<int> A(a,a+10);cout<<randomized_select(A,0,9,5)<<endl;}3、第三种算法以最坏情况线性时间做选择，最坏运⾏时间为O(n)，这种算法基本思想是保证每个数组的划分都是⼀个好的划分，以5为基，五数取分，这个算法，算法导论没有提供伪代码，额，利⽤它的思想，可以快速返回和最终中位数相差不超过2的数，这样的划分接近最优，基本每次都⼆分了（算法导论中步骤见图)/*利⽤中位数来选取枢纽元,这种⽅法最坏情况下运⾏时间是O(n)这⾥求的中位数是下中位数算法导论⾥没有伪代码，写起来很⿇烦注意这⾥的查找到的中位数，并不是真正意义上的中位数⽽是和真正中位数相差不超过2的⼀个数开始以为我写错了，⼜看了算法导论，应该就是这个意思返回的是[x - 1, x + 2]的⼀个数，中位数是x从下边的输出中也可以看出：*/ #include<iostream>#include<cstdio>using namespace std;const int maxn = 14;//kp -> sizeconst int maxm = maxn / 5 + 1;//mid -> sizeint kp[maxn];int mid[maxm]; //插⼊排序void InsertionSort(int kp[], int n) {for (int j, i = 1; i < n; i++) {int tmp = kp[i];for (j = i; j > 0 && kp[j - 1] > tmp; j--) {kp[j] = kp[j - 1];}kp[j] = tmp;}} //查找中位数, 保证每⼀个划分都是好的划分int FindMedian(int kp[], int low, int high) {if (low == high) {return kp[low];}int index = low;//index初始化为low//如果本⾝⼩于5个元素，这⼀步就跳过if (high - low + 1 >= 5) { //储存中位数到mid[]for (index = low; index <= high - 4; index += 5) {InsertionSort(kp + index, 5);int num = index - low;mid[num / 5] = kp[index + 2];}} //处理剩下不⾜5个的元素int remain = high - index + 1;if (remain > 0) {InsertionSort(kp + index, remain);int num = index - low;mid[num / 5] = kp[index + (remain >> 1)];//下中位数}int cnt = (high - low + 1) / 5;if ((high - low + 1) % 5 == 0) {cnt--;//下标是从0开始，所以需要-1}//存放在[0…tmp]if (cnt == 0) {return mid[0];} else {return FindMedian(mid, 0, cnt);}} int Qselect(int kp[], int low, int high, int k) {int pivotloc = FindMedian(kp, low, high); //这⾥有点不⼀样，因为不知道pivotloc下标，所以全部都要⽐较int i = low - 1, j = high + 1;for (; ;) {while (kp[++i] < pivotloc) {}while (kp[--j] > pivotloc) {}if (i < j) swap(kp[i], kp[j]);else break;} int num = i - low + 1;if (k == num) return kp[i];if (k < num) {return Qselect(kp, low, i - 1, k);} else {return Qselect(kp, i + 1, high, k - num);}}int main() {int kp[maxn] = {10, 14, 8, 11, 7, 1, 2, 13, 3, 12, 4, 9, 6, 5};for (int i = 0; i < maxn; i++) {printf("中位数是: %d\n", FindMedian(kp, 0, maxn - 1));printf("第%d⼩的数是: ", i + 1);cout << Qselect(kp, 0, maxn - 1, i + 1) << endl << endl;}return 0;}。

福州大学数学与计算机科学学院《计算机算法设计与分析》上机实验报告（1）图中箭头指向表示大的数值指向小的数值，所以根据图可以看出，在x的右边，每一个包含5个元素的组中至少有3个元素大于x，在x的左边，每一组中至少有3个元素小于x （保证x分割一边必定有元素存在）。

图中显示的中位数的中位数x的位置，每次选取x作为划分的好处是能够保证必定有一部分在x的一边。

所以算法最坏情况的递归公式可以写成：，使用替换法可以得出）（。

Tncn4、算法代码：#include <iostream>#include <ctime>using namespace std;template <class Type>void Swap(Type &x,Type &y);inline int Random(int x, int y);template <class Type>int Partition(Type a[],int p,int r);template<class Type>int RandomizedPartition(Type a[],int p,int r);template <class Type>Type RandomizedSelect(Type a[],int p,int r,int k);int main(){void SelectionSort(int a[]);int s;int a[2000];int b[2000];for(int i=0; i<2000; i++){a[i]=b[i]=rand()%10000;cout<<a[i]<<" ";}cout<<endl;SelectionSort(b);for(int j=0;j<2000;j++){printf("a[%d]:%d ",j+1,b[j]);}cout<<endl;printf("请输入要求的第几最小数：");scanf("%d",&s);cout<<RandomizedSelect(a,0,1999,s)<<endl; }template <class Type>void Swap(Type &x,Type &y){Type temp = x;x = y;y = temp;}inline int Random(int x, int y){srand((unsigned)time(0));int ran_num = rand() % (y - x) + x;return ran_num;}template <class Type>int Partition(Type a[],int p,int r){int i = p,j = r + 1;Type x = a[p];while(true){while(a[++i]<x && i<r);while(a[--j]>x);if(i>=j){break;}Swap(a[i],a[j]);}a[p] = a[j];a[j] = x;return j;}template<class Type>int RandomizedPartition(Type a[],int p,int r){int i = Random(p,r);Swap(a[i],a[p]);return Partition(a,p,r);}template <class Type>Type RandomizedSelect(Type a[],int p,int r,int k) {if(p == r){return a[p];}int i = RandomizedPartition(a,p,r);int j = i - p + 1;if(k <= j){return RandomizedSelect(a,p,i,k);}else{//由于已知道子数组a[p:i]中的元素均小于要找的第k小元素//因此，要找的a[p:r]中第k小元素是a[i+1:r]中第k-j小元素。

程序设计报告我保证没有抄袭别人作业!1.题目内容题名为线性时间选择。

题目要求：给定无序序列集中n个元素和一个整数k,1<=k<=n。

要找到这n个元素中第k小的元素。

2.算法分析（1）分治法思想将n个输入元素划分成n/5个组，每组5个元素，只可能有一个组不是5个元素。

用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共n/5个。

递归调用select来找出这n/5个元素的中位数。

如果n/5是偶数，就找它的2个中位数中较大的一个。

以这个元素作为划分基准。

在此处选用的排序算法为快速排序。

算法框架：Type Select(Type a[], int p, int r, int k){if (r-p<75) {//用快速排序算法对数组a[p:r]排序;return a[p+k-1];};for ( int i = 0; i<=(r-p-4)/5; i++ )将a[p+5*i]至a[p+5*i+4]的第3小元素与a[p+i]交换位置;//找中位数的中位数，r-p-4即上面所说的n-5Type x = Select(a, p, p+(r-p-4)/5, (r-p-4)/10);int i=Partition(a,p,r, x),j=i-p+1;if (k<=j) return Select(a,p,i,k);else return Select(a,i+1,r,k-j);}快速排序的算法int i=p,j=r+1;int x=a[p];while(1){ while(a[int qsort(int *a,int p,int r) { if(p<r){ int q;q=partition(a,p,r);qsort(a,p,q-1);qsort(a,q+1,r);}}int partition(int a[],int p,int r){++i]<x);while(a[--j]>x);if(i>=j)break;else swap(i,j);}a[p]=a[j];a[j]=x;return j;}3.算法的优化一般我们选择无序序列的某个元素作为划分元素，每次调用Partition(A,p,r),所需的元素比较次数是Ο(r-p+1)。

实验五线性时间选择问题年级 16 学号 20161101072 姓名陈飞宇成绩专业信息安全实验地点 C1-413 指导教师陈丽萍实验日期一、实验目的1、理解分治法的基本思想2、掌握分治法解决问题的基本步骤，并能进行分治算法时间空间复杂度分析。

二、实验内容线性时间选择问题：给定线性序集中n个元素和一个整数k（k>=1而且k<=n），要求在线性时间内找出这n个元素中第k小的元素。

1.随机快速排序2.利用中位数线性时间选择三、算法描述1.随机快速排序在算法Randomized_Select中执行Randomized_Partition，将数组分成两个子数组，在Randomized_Partition中调用Partition函数确定一个基准元素，对数组进行划分。

由于划分是随机产生的，由此导致算法Randomized_Select也是一个随机化算法。

2.利用中位数线性时间选择四、程序1.随机快速排序#include<stdio.h>#include<stdlib.h>#include<time.h>int Randomized_Select(int a[],int p,int r,int i);int Randomized_Partition(int a[],int p,int r);int Partition(int a[],int p,int r);void swap(int *a,int *b);int Random(int p,int q);int main(){int a[] = {10,9,8,7,6,5,4,3,2,1};int i = 3;printf("第%d小的数是:\n%d",i,Randomized_Select(a,0,9,i)); return 0;}void swap(int *a,int *b){int temp;temp = *a;*a = *b;*b = temp;}int Random(int p,int q)//产生p和q之间的一个随机整数{int i,number;srand((unsigned)time(NULL));number = rand()%(q-p+1)+p;return number;}int Partition(int a[],int p,int r)//快排的部分{int x = a[r];int i = p- 1;int j;for(j = p;j<=r-1;j++){if(a[j] <= x){i = i + 1;swap(&a[j],&a[i]);}}swap(&a[i+1],&a[r]);return i+1;}int Randomized_Partition(int a[],int p,int r)//随机交换数字{int i = Random(p,r);swap(&a[r],&a[i]);return Partition(a,p,r);}int Randomized_Select(int a[],int p,int r,int i)//选择算法核心{if(p == r) return a[p];int q = Randomized_Partition(a,p,r);int k = q - p + 1;if(i == k)//如果刚好等于i，输出return a[q];else if(i < k)//如果i比k小，证明要找的元素在低区return Randomized_Select(a,p,q-1,i);else //找的元素在高区return Randomized_Select(a,q+1,r,i-k); //因为a[q]已经是前面第k个小的，所以在后面就是i-k小}2. 利用中位数线性时间选择#include <stdio.h>#include <stdlib.h>#include <ctime>#include <iostream>using namespace std;template <class Type>void Swap(Type &x,Type &y);inline int Random(int x, int y);template <class Type>void BubbleSort(Type a[],int p,int r);template <class Type>int Partition(Type a[],int p,int r,Type x);template <class Type>Type Select(Type a[],int p,int r,int k);int main(){//初始化数组int a[10];//必须放在循环体外面srand((unsigned)time(0));for(int i=0; i<10; i++){a[i] = Random(0,50);cout<<"a["<<i<<"]:"<<a[i]<<" ";}cout<<endl;cout<<"第3小元素是"<<Select(a,0,9,3)<<endl;//重新排序，对比结果BubbleSort(a,0,9);for(int i=0; i<10; i++){cout<<"a["<<i<<"]:"<<a[i]<<" ";}cout<<endl;}template <class Type>void Swap(Type &x,Type &y){Type temp = x;x = y;y = temp;}inline int Random(int x, int y){int ran_num = rand() % (y - x) + x;return ran_num;}//冒泡排序template <class Type>void BubbleSort(Type a[],int p,int r){//记录一次遍历中是否有元素的交换bool exchange;for(int i=p; i<=r-1;i++){exchange = false ;for(int j=i+1; j<=r; j++){if(a[j]<a[j-1]){Swap(a[j],a[j-1]);exchange = true;}}//如果这次遍历没有元素的交换,那么排序结束 if(false == exchange){break ;}}}template <class Type>int Partition(Type a[],int p,int r,Type x){int i = p-1,j = r + 1;while(true){while(a[++i]<x && i<r);while(a[--j]>x);if(i>=j){break;}Swap(a[i],a[j]);}return j;}template <class Type>Type Select(Type a[],int p,int r,int k){if(r-p<75){BubbleSort(a,p,r);return a[p+k-1];}//(r-p-4)/5相当于n-5for(int i=0; i<=(r-p-4)/5; i++){//将元素每5个分成一组，分别排序，并将该组中位数与a[p+i]交换位置 //使所有中位数都排列在数组最左侧，以便进一步查找中位数的中位数BubbleSort(a,p+5*i,p+5*i+4);Swap(a[p+5*i+2],a[p+i]);}//找中位数的中位数Type x = Select(a,p,p+(r-p-4)/5,(r-p-4)/10);int i = Partition(a,p,r,x);int j = i-p+1;if(k<=j){return Select(a,p,i,k);}else{return Select(a,i+1,r,k-j);}}五、测试与分析1.随机快速排序 O(n)2.利用中位数线性时间选择 O(n)。