算法实验报告——线性时间选择问题

实验五线性时间选择问题年级16 学号飞宇成绩专业信息安全实验地点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)。