作者:郭健曲 | 来源:互联网 | 2023-08-13 13:59
该算法由西南交通大学段凡丁老师提出,提出的时间比较早,1992年还是1993年。我应一个朋友的要求把这个算法实现了,并跟快速排序算法作了比较,发现确实是要比快速排序快。我们都知道快速排
该算法由西南交通大学段凡丁老师提出,提出的时间比较早,1992年还是1993年。我应一个朋友的要求把这个算法实现了,并跟快速排序算法作了比较,发现确实是要比快速排序快。
我们都知道快速排序算法的时间复杂度是O(N*log2 N),据段老师论文中的描述,超快速排序算法可达到O(N)的效率。
我们先来看看算法的核心思想:
利用hash地址散列原理,设计散列函数H:R->S,使R[1:n]中的各个元素按照其自身的序列及分布规律快速地映射在S[1:m]空间。采用冲突元素预留地址区间法,解决重复冲突和散列失效的问题。
我按照论文的算法描述,用C++将超快速算法封装成了一个类。具体代码如下所示。
#ifndef __SupperSort_H__ #define __SypperSort_H__ #include "MyTimer.h" #include template class SupperSort { public: long g_costTime; protected: T *m_array, *m_addr,*m_point; int size; public: // 构造函数:分配相关内存空间,初始化变量 SupperSort(T *num,int n) { this->size = n; this->m_array = new T[size]; memcpy(this->m_array,(void *)num,n*sizeof(T)); this->m_addr = new T[size]; memset(this->m_addr,0,size*sizeof(T)); this->m_point = new T[size]; memset(this->m_point,0,size*sizeof(T)); g_costTime = 0; } // 核心算法:超快速排序 int Sort() { int i; MyTimer timer; timer.Start(); // 取得数组中的最大值和最小值 GetMaxMin(); if( m_max == m_min ) { cout<<"End SupperSort" < return 1; } // 对冲突元素进行分组计算 for(i=1;i { int j=(m_array[i]-m_min)*(size-2)/(m_max-m_min)+1; m_addr[j] = m_addr[j]+1; } // 找出每个元素的散列地址区间,即散列末地址 for(i=2;i m_addr[i] += m_addr[i-1]; // k从n到1,依次计算源数组的散列地址区间,若该地址的m_point指针为空,说明无冲突,则将k放入m_point指针; // 若m_point指针不空,则将k前推用插入的方法直接插入到m_point指针 for(i=size-1;i>0;i--) { int k=i; int g=m_addr[(m_array[k]-m_min)*(size-2)/(m_max-m_min)+1]; while(m_point[g]!=0) { if( m_array[k]>m_array[m_point[g]] ) { int t = k; k = m_point[g]; m_point[g] = t; } g = g-1; } m_point[g] = k; } timer.End(); g_costTime = timer.costTime; cout <<"End SuperSort! Costs Time:" < return 0; } // 输出最后的排序结果 void OutResult() { for(int i=1;i { cout < } cout < } // 析构函数:释放相关内存 virtual ~SupperSort() { if( m_array ) { delete []m_array; m_array = NULL; } if( m_addr ) { delete []m_addr; m_addr = NULL; } if( m_point ) { delete []m_point; m_point = NULL; } } private: T m_max,m_min; // 获取数组的最大值和最小值 void GetMaxMin() { m_max = 0; m_min = 100000000; for(int i=1;i { if( this->m_array[i] > m_max ) m_max = m_array[i]; if( this->m_array[i] m_min = m_array[i]; } } }; #endif |
上面的代码注意两点:
(1)红色的部分有可能出现问题。当数组的规模size很大,并且数也很大时,有可能超出整型描述的范围,因此在测试的时候要控制好;
(2)代码中的MyTimer类是自己写的一个计时类,可精确到微妙级别。该类的代码如下:
#ifndef __MyTimer_H_ #define __MyTimer_H_ #include class MyTimer { private: int _freq; LARGE_INTEGER _begin; LARGE_INTEGER _end; public: long costTime; // 花费的时间(精确到微秒) public: MyTimer() { LARGE_INTEGER tmp; QueryPerformanceFrequency(&tmp); _freq = tmp.QuadPart; costTime = 0; } void Start() // 开始计时 { costTime = 0; QueryPerformanceCounter(&_begin); } void End() // 结束计时 { QueryPerformanceCounter(&_end); costTime = (long)((_end.QuadPart - _begin.QuadPart) * 1000000 / _freq); } void Reset() // 计时清0 { costTime = 0; } }; #endif |
与超快速排序相比较的快速排序算法我也封装成了一个类,具体如下:
#ifndef __QuickSort_H__ #define __QuickSort_H__ #include "MyTimer.h" #include template class QuickSort { protected: T *m_array; int size; int m_low,m_high; public: long g_costTime; public: // 构造函数 QuickSort(T *num,int n,int low,int high) { size = n; m_low = low; m_high = high; m_array = new T[size]; memcpy(m_array,(void *)num,n*sizeof(T)); g_costTime = 0; } // 进行快速排序 void Sort() { MyTimer timer; timer.Start(); BeginSort(m_low,m_high); timer.End(); g_costTime = timer.costTime; cout <<"End QuickSort! Costs Time:" < } // 输出最后的排序结果 void OutResult() { for(int i=1;i { cout < } cout < } // 析构函数:释放内存 virtual ~QuickSort() { if( m_array ) { delete []m_array; m_array = NULL; } } private: // 快速排序的核心实现:递归 void BeginSort(int low,int high) { int po; if(low { po=Partion(low,high); BeginSort(low,po-1); BeginSort(po+1,high); } } // 具体实现 int Partion(int low,int high) { T key; key=m_array[low]; while(low { while(low=key) high--; m_array[low]=m_array[high]; while(low low++; m_array[high]=m_array[low]; } m_array[low]=key; return low; } }; #endif |
具体的测试程序如下:
#include "MyTimer.h" #include "QuickSort.h" #include "SupperSort.h" #include #include #include #include #define M_Size 100001 int main() { int num[M_Size]; srand((int)time(0)); // 让每次产生的随机数都不一样 for(int i=1;i { num[i] = rand()%10000; } QuickSort qs(num,M_Size,1,M_Size-1); qs.Sort(); //qs.OutResult(); cout<<"-----------------------------------" < SupperSort ss(num,M_Size); ss.Sort(); //ss.OutResult(); return 0; } |
注意:数组的规模为M_Size,数组元素最大值为9999。在超快速排序中,冲突元素的个数跟数据规模和数据的最大值有关系。当规模大,而最大值小时,冲突元素多,超快速排序花费时间多。
------------------------------------------- 其实我就是分割线 ----------------------------------------------------
我的机子的配置是:
CPU:Intel(R) Core(TM)2 Duo 2.0GHZ
内存:2G
系统:Windows XP
下面是具体的测试结果: