精华内容
下载资源
问答
  • 线性时间选择

    2020-09-28 22:32:01
    方法:线性时间选择随机划分法可以模仿随机化快速排序算法设计。基本思想是对输入数组进行递归划分,与快速排序不同的是,它只对划分出的子数组之一进行递归处理。 可以按以下步骤找到满足要求的划分基准: 将n个...

    问题:给定线性序集中n个元素和一个整数k,1≤k≤n,要求找出这n个元素中第k小的元素。(这里给定的线性集是无序的)。(如果将这个线性集先排好序,则排在第k个位置的元素即为要找的元素)

    方法:线性时间选择随机划分法可以模仿随机化快速排序算法设计。基本思想是对输入数组进行递归划分,与快速排序不同的是,它只对划分出的子数组之一进行递归处理。

    可以按以下步骤找到满足要求的划分基准:

    1. 将n个输入元素划分成n/5(向上取整)个组,每组5个元素,最多只可能有一个组不是5个元素。用任意一种排序算法,将每组中的元素排好序,并取出每组的中位数,共n/5(向上取整)个。

    2. 递归调用select来找出这n/5(向上取整)个元素的中位数。如果n/5(向上取整)是偶数,就找它的2个中位数中较大的一个作为划分基准。

    思考草图:
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    (每一组进行排序,最后不足5个的忽略)
    ————————————————————————————
    在这里插入图片描述
    (找出每一组的中位数)
    ————————————————————————————
    在这里插入图片描述
    (把中位数提出来)
    ————————————————————————————————————
    在这里插入图片描述
    (找到中位数的中位数)

    ————————————————————————————————————
    在这里插入图片描述
    (交换位置作为“轴”,借鉴快速排序)

    在这里插入图片描述
    ————————————————————————————在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    (找到k)

    #include<iostream>
    #include<ctime>
    #include<cstdlib>
    using namespace std;
    
    int partition(int a[], int p, int r){
    	int i = p;
    	int j = r + 1;
    	int 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;
    }
    
    int partition(int a[], int p, int r, int x){   //重载partition方法 
    	
    	int i = p-1;
    	int j = r + 1;
    
    	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 quickSort(int a[], int p, int r){
    	if(p < r){
    		int q = partition(a, p, r);
    		quickSort(a, p, q - 1);   //左边排序
    		quickSort(a, q + 1, r);    //
    	}
    }
    
    int select(int a[], int p, int r, int k){
    	
    	if(r - p < 75) {
    		
    		quickSort(a, p , r);   //其他排序也可以 
    		return a[p+k - 1];
    	}
    	
    	for(int i = 0; i <= (r-p-4) / 5; i++){  //r-p-4表示最后一组的中位数所在组数 (有几组就有几个中位数,所以(r-p-4)/5也可以表示中位数个数) 
    		
    		quickSort(a, p+i*5, p+i*5+4);   //将元素每5个分成一组,分别排序
    		swap(a[p+i], a[p+i*5+2]); 	   //并将该组中位数与a[p+i]交换位置使所有中位数都排列在数组最左侧,以便进一步查找中位数的中位数		
    	}
    	//找中位数的中位数
    	int x = select(a, p, p+(r-p-4) / 5, (r-p-4) / 10); //(r-p-4) / 10:中位数的中位数的下标 
    	int pivot = partition(a, p, r, x);
    	int j = pivot-p + 1;
    	
    	if(k <= j)
    		return select(a, p, pivot, k);
    	else
    		return select(a, pivot + 1, r, k - j);
    }
    
    
    int main(){
    	
    	//初始化数组 
    	int a[100];
    	srand((int)time(0));  // 产生随机种子  把0换成NULL也行
    	for(int i = 0; i < 100; i++){
    		
    		a[i] = rand() % 100;
    	}
    	int k;
    	cout << "please input k: " << endl; cin >> k;
    	cout << select(a, 0, 99, k) << endl;
    	for(int i = 0; i < 100; i++){
    		cout << a[i] << " ";
    	}	
    	cout << endl << "-------------检验组----------"<< endl;
    	quickSort(a, 0, 99);
    	for(int i = 0; i < 100; i++){
    		cout << "a[" << i << "]="<< a[i]  << " ";
    	}	
    	
    }
    

    在这里插入图片描述

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,611
精华内容 1,044
关键字:

线性时间选择