算法学习(7)分治策略(最差情况下查找为线性时间算法)

来源:转载


   线性时间选择算法在最差的情况下的时间复杂度是O(n^2),这个算法就是为了优化这一点而诞生的。算法的整体思想基本相似,优化的关键点在于分割点的选择。首先上一张草图。



      首先将数组按照顺序,每5个组成一组。上图中数组是按竖着的顺序排列的。对每一个组排序,并将中位数取出存到额外的一个序列里面;     然后在去对这个额外的序列去分割成5个5个的组,再去求取中位数,依次下去求得中位数的中位数。然后将这个中位数作为分割点,进行线性时间选择算法得到结果。代码如下:

#include <iostream>#include <stdlib.h>#include <time.h>using namespace std;/*********************************************************************** Input:a[]: 待排数组序列 l:待排区间左下标,r:待排区间右下标 Output:Description: 冒泡排序Return: Others:************************************************************************/template <class T>void BubbleSort(T a[], int l ,int r){ T tmp = a[l]; //临时变量,交换使用 for(int i=l; i<r; ++i) { for(int j=i+1; j < r; ++j) { if(a[i] > a[j]) { tmp = a[i]; a[i] = a[j]; a[j] = tmp; } } }}/*********************************************************************** Input:a[]:待排数组序列 l:待排区间左下标,r:待排区间右下标 x 枢纽元素Output:Description:将数组化分成 a[... x ...]。x左边的元素都小于x,右边的 元素都大于x。 Return: 排序后枢纽元素的下标 Others:************************************************************************/template <class Type>int Partition(Type a[], int l, int r, Type x){ int i = l; //枢纽元素的索引号 int j = r; //a[]序列右边界索引号 while(i < j) { //从序列最右边开始查找,找到一个小于a[l]的为止; while (a[j] >= x && i < j) --j; if(i < j) { a[i] = a[j]; i++; } //从a[l]后面元素开始查找,找到一个比a[l]大的为止; while (a[i] < x && i < j) ++i; if (i < j) { a[j] = a[i]; j--; } } a[i] = x; //将a[i]的值写回 return i; //返回分割点的索引} /*********************************************************************** Input:a[]: 待排数组序列 l:待排区间左下标,r:待排区间右下标 Output:Description: 将数组序列的第一个元素作为枢纽元素x,将数组化分成 a[... x ...]。x左边的元素都小于x,右边的元素都大于x。 Return: Others:************************************************************************/template <class T>T Select(T a[], int l, int r, int k){ //T tmp = a[l]; //初始化赋值任意元素 if(r - l < 75) { BubbleSort(a, l, r); return a[l + k - 1]; } for(int i=0; i<=(r-l-4)/5; ++i) { //将a[l+5*i] - a[l + 5*i + 4]的第3小元素与a[l+i]交换位置; BubbleSort(a, l+5*i, l+5*i + 5); tmp[i] = a[l + 5*i + 2]; //a[l + i] = a[l + 5*i + 2]; //因为上面是已序的,所以可以很好的交换 //a[l + 5*i + 2] = tmp; //5个元素已经是排序了的 } //找到中位数的中位数,r-l-4 T x = Select(tmp, l, (r-l-4)/5, (r-l-4)/10); int i = Partition(a, l, r, x); int j = i - l + 1; if(k <= j) return Select(a, l, i, k); else return Select(a, i+1, r, k-j);}int tmp[25] = {0};int main(){ int b[100] = {0}; int a[100] = {0}; //产生原序列 srand((unsigned)time(NULL)); cout << "The src array is: " << endl; for(int i=0; i<10; ++i) { for(int j=0; j<10; ++j) { b[i*10 + j] = rand()%100; cout<< b[i*10 + j] << '/t'; } cout << endl; } cout << endl; memcpy(a, b, sizeof(a)); BubbleSort(a, 0, 100); cout << "The src sorted array is: " << endl; for(int i=0; i<10; ++i) { for(int j=0; j<10; ++j) { cout<< a[i*10 + j] << '/t'; } cout << endl; } cout << endl << endl; int tmpt = Select(b,0,100,15); cout<<"The 15 Min Element is : " << tmpt << endl; //冒泡排序 BubbleSort(b, 0, 100); cout << "After finding, array is: " << endl; for(int i=0; i<10; ++i) { for(int j=0; j<10; ++j) { cout<< b[i*10 + j] << '/t'; } cout << endl; } cout << endl; return 0;}
运行结果:







分享给朋友:
您可能感兴趣的文章:
随机阅读: