精华内容
下载资源
问答
  • 算法技术手册 – 排序 – 桶排序/哈希排序/散列排序
    2021-05-26 02:40:00

    在前面的计数排序中,我们已经领略到了如何用空间换时间的方法,找到一种线性时间复杂度O(N)的排序算法。

    计数排序的缺点也是非常明显的:一旦数据范围[0,k),中的k]相对于数据量N非常稀疏,计数排序的空间会非常大、时间消耗也会增大非常大。当然主要还是空间问题。

    个人认为:桶排序 = 哈希排序 = 散列排序,基本思想是一样的。

    于是桶排序/哈希排序应运而生,假设值域范围还是k,我们不去创建k个buckets,而是创建m个木桶,让N个元素通过哈系函数映射到这k个桶即可。这里还有一个必须注意的大前提:哈希函数必须保证m个桶有序!即若i < j,则桶bi中的元素要小于桶bj中的元素。

    一个这种哈希函数的例子,对0~1之间的浮点数映射到m个桶中

    int hash(double *d, int m)

    {

    int bucket = m*(*d);

    return bucket;

    }

    利用了C语言强制转换丢失精度的特性,非常巧妙吧!如此一来0.5的hash一定小于0.69!

    哈希排序同时带来的问题是:一个桶中会含有多个元素,对这些元素的排序可以使用插入排序(在数据量小时,如n=4,插入排序是最快的。)

    虽然插入排序的时间复杂读是O(N^2),但是散列平均的话,可以证明对每个桶内进行插入排序,其时间消耗是常数!即总体的散列排序/哈希排序的时间复杂度仍然是O(N)!!

    因此,对于散列排序而言,桶k的个数越大,排序速度就会不断加快。当选择足够多的桶个数时,散列排序可以比快速排序更快!

    散列排序不止可以用于数值,还可用于随机字符的排列,以26个字母为例:

    我们将字符串的前3位想乘做为一个Hash函数,那么k的空间毫无疑问是26^3

    #桶数量计算

    int numBuckets()

    {

    return 26*26*26;

    }

    int hash(char* elem)

    {

    return (elem[0] - 'a')*26*26 +

    (elem[1] - 'a')*26 +

    (elem[2] - 'a');

    }

    只有在桶很少的情况下,散列排序的性能会退化接近于O(N^2)

    更多相关内容
  • 哈希index2 == max(67)是可以出现的,所以index2<68 length在大部分语言里是最大的数字下标+1 完整的计数排序 a <- {'0':0, '1':2,'.':56,'4':4,'5':67,'6':3, 'length':67} hash<-{} index <- 0 ...
    哈希index2 == max(67)是可以出现的,所以index2<68

    length在大部分语言里是最大的数字下标+1

    完整的计数排序

    a <- {'0':0, '1':2,'.':56,'4':4,'5':67,'6':3,
    'length':67}
    hash<-{}
    index <- 0
    while(index < a['length'])
        number = a[index]
        if hash[number] == undefined //hash[number] 不存在
            hash[number] = 1
            else // hash[number]存在
            hash[number] = hash[number] + 1
        end
        index <- index + 1
    end
    index2 <- 0
    max <- findmax(a)
    index2 <- 1
    while index < findmax['length']
        if findmax[index2] < max
            max <- findmax[index2]
        end
        index2 <- index2 + 1
    end
    nawarr <- {}
    while(index2 < max + 1)
        count=hash[index2]
        if count !=undefined
            countIndex = 0
            while(countIndex < count)
                newArr.push(index2)
                countIndex <- countIndex + 1
            end
        end
        index2 <- index2 + 1
    end
    print newArr
    

    桶排序

    桶排序是计数排序的升级版
    排序,要么浪费时间,要么浪费空间
    桶排序里可以进行二次排序


    桶排序
    10个一个桶或者100个一个桶

    基数排序

    基数排序适合万位数以下,适应与大基数的排序
    基数排序就是10进制排序
    出桶和入桶顺序顺序
    先按照个位数进行排序
    十位数入桶
    按照十位数进行排序
    百位数入桶
    按照百位数进行排序
    千位数入桶
    按照千位数进行排序
    万位数入桶
    按照万位数进行排序

    可参考网站:VisuAlgo

    展开全文
  • 解题思路:哈希表+桶排序 (1)定义一个哈希表,然后数值元素作为哈希表的关键字first,哈希表的值作为关键字的个数,进行遍历; (2)将哈希表的关键字存在一个数组中,然后根据哈希表的值进行比较排序,按照降序...

     

    给定一个非空的整数数组,返回其中出现频率前k高的元素。
    例如:
    给定数组[1,1,1,2,2,3],其中k=2,则返回[1,2]
    
    注意:
    (1)可以假设给定的k总是合理的,1<=<=数组中不相同的元素个数
    (2)算法的时间复杂度必须优于o(nlogn),n是数组的大小
    
    解题思路:哈希表+桶排序
    (1)定义一个哈希表,然后数值元素作为哈希表的关键字first,哈希表的值作为关键字的个数,进行遍历;
    (2)将哈希表的关键字存在一个数组中,然后根据哈希表的值进行比较排序,按照降序排序;
    (3)对数组遍历前k个位置便得到相关的元素;
    
    

     方法一:

    
    /*哈希表+桶排序*/
    #include <iostream>
    #include <vector>
    #include <unordered_map>
    #include <algorithm>
    
    using namespace std;
    static int x=[](){
        ios::sync_with_stdio(false);
        cin.tie(0);
        return 0;
    }();  //加快输入输出操作
    
    class Solution{
     public:
        
        vector<int> TopFrequency(vector<int>& nums,int k){
            
            unordered_map<int,int> map;
            for(auto& i:nums)  //&引用数组本身,不需要拷贝
               ++map[i];//i代表数组元素,map[i]是元素的个数,进行加1操作
            
            for(auto& j:map)
                bucket.push_back(j.first); //关键字存入桶中
            
            /*
            这样表达也可以
            for(auto j=map.begin();j!=map.end();j++)
                bucket.push_back(j->first);   
            */      
            //sort(begin,end,compare),三个参数,compare是bool型
            sort(bucket.begin(),bucket.end(),[&map](int a,int b){return map[a]>map[b];});//按照降序排序 
            return vector<int>(bucket.begin(),bucket.begin()+k);//输出前k个高频数组
        }
    
    private:
         vector<int> bucket;
    
    };
    
    int main(int argc,char* argv[]){
        int test[]={1,3,4,4,5,6,9,3,3};
        vector<int> nums(test,test+9);
        for(auto &member:Solution().TopFrequency(nums,2))
             cout<<member<<"  ";
        cout<<endl;
        return 0;
    }

    方法二: 

    /*哈希表+桶排序*/
    #include <iostream>
    #include <vector>
    #include <map>
    #include <algorithm>
    
    using namespace std;
    static int x=[](){
        ios::sync_with_stdio(false);
        cin.tie(0);
        return 0;
    }();  //加快输入输出操作
    
    bool compare(const pair<int,int>& a,const pair<int,int>& b){
            return a.second>b.second;
    }
    
    class Solution{
     public:
        vector<int> topfrequent(vector<int>& nums,int k){
            map<int,int> elements;
            for(int i=0;i<nums.size();i++)
                elements[nums[i]]++;//nums代表数组元素,elemets[i]是元素的个数,进行加1操作
            
            for(auto it=elements.begin();it!=elements.end();it++)
                butkets.push_back(pair<int,int>(it->first,it->second));
    
            sort(butkets.begin(),butkets.end(),compare);//按照降序排序,自定义compare,传入pair
    
            vector<int> result;//用于存储结果
            for(int i=0;i<k;i++)
                 result.push_back(butkets[i].first);
    
            return result; 
    
        }
        
    private:
         vector<pair<int,int>> butkets;//关键字存入桶中,第一个值为元素,第二个值为元素数量
    
    };
    
    int main(int argc,char* argv[]){
        int test[]={1,3,4,4,5,6,9,3,3};
        vector<int> nums(test,test+9);
        for(auto &member:Solution().topfrequent(nums,2))
             cout<<member<<"  ";
        cout<<endl;
        return 0;
    }

     

     

    展开全文
  • 14 哈希和哈希桶

    2022-01-17 14:05:52
    代码实现五、开散列(哈希桶)5.1. 开散列扩容5.2. 代码实现六、闭散列开散列的比较 一、哈希哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把...


    一、哈希表

    哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,通过这种方式,可以不经过任何比较,一次直接从表中得到要搜索的元素,即查找的时间复杂度为 O(1)。
    这个映射函数叫做哈希(散列)函数,存放记录的数组叫做哈希(散列)表。

    最典型的例子是计数排序,将要排序的数组每个元素和新开辟的数组的下标进行映射。

    向哈希表中插入和搜索元素的过程如下:
    先用哈希函数将被要插入或查找的键值转化为数组的一个索引。

    • 插入元素: 根据索引位置,将元素存放到此位置。
    • 搜索元素: 根据索引,找到存储在该索引位置的元素。

    在理想情况下,不同的键都能转化为不同的索引值。当然,这只是理想情况,所以我们需要面对两个或者多个键都会散列到相同的索引值的情况。这就是哈希冲突的问题。

    二、哈希函数

    2.1. 直接定址法(常用)

    取关键字的某个线性函数作为散列地址:hash(key)=A*key + B
    优点:简单、均匀
    缺点:实现需要知道关键字的分布情况,并且只适合查找比较小,且连续分布的情况
    适用场景:查找字符串中,第一次出现的单词:构建一个数组 hash[ch-‘a’] 即为对应的地址
    不适用场景:给一批数据, 1 5 8 100000 像这数据跨度大,数据元素不连续,很容易造成空间浪费

    2.2. 除留余数法(常用)

    设散列表中允许的地址数为m,通常是取一个不大于m,但是最接近或者等于m的质数num,作为除数,按照哈希函数进行计算hash(key)= key%num, 将关键码转换成哈希地址
    优点:使用场景广泛,不受限制。
    缺点:存在哈希冲突,需要解决哈希冲突,哈希冲突越多,效率下降越厉害。

    2.3. 几种不常用的方法

    1. 平方取中法

    hash(key)=key*key 然后取函数返回值的中间的几位,作为哈希地址
    比如 25^2 = 625 取中间的一位 2 作为哈希地址

    比较适合不知道关键字的分布,而位数又不是很大的情况

    1. 折叠法

    将关键字从左到右分割成位数相等的几部分(最后一部分可以短些),然后将这几部分叠加求和,并且按照散列表长度,取最后几位作为散列地址

    适用于不知道关键字分布,关键字位数比较多的情况

    1. 随机数法

    选取一个随机函数,取关键字的随机函数值,作为它的哈希地址,hash(key) = random(key),random为随机函数

    通常用于关键字长度不等的情况

    1. 数学分析法

    通过实现分析关键字,来获取哈希地址

    比如用每个人的手机号码充当关键字,如果采用前三位作为哈希地址,那么冲突的概率是非常大的。如果采用的是中间3位那么冲突的概率要小很多

    常用于处理关键字位数比较大的情况,且事前知道关键字的分布和关键字的若干位的分布情况


    三、哈希冲突

    不同关键字通过相同哈希函数计算出相同的哈希映射地址,这种现象称为哈希冲突或哈希碰撞。
    在这里插入图片描述

    解决哈希冲突通常有两种方法:闭散列(开放地址发)和开散列(链地址法)。


    四、闭散列

    闭散列也叫做开放地址法,当发生哈希冲突的时候,如果哈希表未被填满,说明在哈希表中必然还有空位置,那么可以把key存放到冲突位置的"下一个"空位置中去,寻找下一个空位置的方法有线性探测法和二次探测法

    4.1. 线性探测

    从发生冲突的位置开始,依次向后探测,直到寻找到下一个位置为止

    优点:实现非常简单
    缺点:一旦发生哈希冲突,所有的冲突连在一起,容易产生数据"堆积",即不同关键码占据了可利用的空位置,使得寻找某关键码的位置需要进行多次比较,导致搜索效率降低。
    在这里插入图片描述

    4.2. 负载因子

    随着哈希表中数据的增多,产生哈希冲突的可能性也随着增加。
    我们将数据插入到有限的空间,那么空间中的元素越多,插入元素时产生冲突的概率也就越大,冲突多次后插入哈希表的元素,在查找时的效率必然也会降低。介于此,哈希表当中引入了负载因子(载荷因子):

    散列表的载荷因子定义为 α = 填入表中的元素 / 散列表的长度

    α是散列表装满程度的标志因子,α越大表明装入表中的元素越多,产生冲突的可能性也就越大,反之填入表中的元素越少,冲突可能性越低,空间利用率也就越低

    闭散列:一般将载荷因子控制在 0.7-0.8以下,超过0.8查表时候的缓存不中率会按照指数曲线上升(哈希可能性冲突越大),因此一般hash库中,都将α设置在0.8以下。 闭散列,千万不能为满,否则在插入的时候会陷入死循环

    开散列/哈希桶:一般将载荷因子控制在1。超过1,那么链表就挂得越长,效率也就越低

    4.3. 二次探测

    线性探测的缺陷是产生哈希冲突,容易导致冲突的数据堆积在一起,这是因为线性探测是逐个的找下一个空位置.
    二次探测为了缓解这种问题(不是解决),对下一个空位置的查找进行了改进(跳跃式查找):
    POS = (H+i2)%m
    其中:i=1、2、3…
    H是发生哈希冲突的位置
    m是哈希表的大小
    在这里插入图片描述

    4.4. 插入和删除操作

    插入操作比较简单:通过哈希函数插入元素在哈希表中的位置,如果发生了哈希冲突,则使用线性探测或二次探测寻找下一个空位置插入元素。
    但是删除操作比较麻烦,采用闭散列处理哈希冲突时,不能随便删除哈希表中已有的元素,如果直接删除元素,会影响其他元素的搜索(比如原来下标为40的元素因为前面删除了一个元素下标变成了39)。
    因此线性探测采用标记的伪删除法来删除下一个元素。

    4.5. 扩容操作

    为了减少冲突,哈希表的大小最好是素数。为了能够获取每次增容后的大小,将需要用到的素数序列提前用一个数组存储起来,当我们需要增容时就从该数组当中进行获取。

    4.6. 代码实现

    namespace CloseHash//闭散列
    {
    	enum State
    	{
    		EMPTY,
    		EXIT,
    		DELETE
    	};
    	template<class K,class V>
    	struct  HashData
    	{
    		pair<K, V> _kv;
    		State _state=EMPTY;//节点的状态默认为空
    	};
    	template<class K>
    	struct  Hash
    	{
    		size_t operator()(const K& key)
    		{
    			return key;
    		}
    	};
    	template<>
    	struct  Hash<string>
    	{
    		size_t operator()(const string& s)
    		{
    			size_t value = 0;
    			for (auto ch : s)
    			{
    				value += ch;
    				value *= 131;
    			}
    			return value;
    		}
    	};
    	template<class K, class V,class HashFunc=Hash<K>>
    	struct  HashTable
    	{
    	public:
    		size_t GetNextPrime(size_t prime)
    		{
    			static const int PRIMECOUNT = 28;//给成静态,不用重复生成
    			static const size_t primeList[PRIMECOUNT] =
    			{
    				53ul, 97ul, 193ul, 389ul, 769ul,
    				1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
    				49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
    				1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
    				50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
    				1610612741ul, 3221225473ul, 429496729ul
    			};
    
    			size_t i = 0;
    			for (; i < PRIMECOUNT; ++i) {
    				if (primeList[i] > prime)
    					return primeList[i];
    			}
    
    			return primeList[i];
    		}
    		bool Insert(const pair<K, V>& kv)
    		{
    			HashData<K, V>* ret = Find(kv.first);
    			if (ret) //哈希表中已经存在该键值的键值对(不允许数据冗余)
    			{
    				return false; //插入失败
    			}
    
    			//进行扩容检测
    			if (_n == 0 || (_n / _table.size() * 10 > 7))//当前个数为0或者载荷因子超过了,则进行扩容
    			{
    				//size_t newsize = _size == 0 ? 10 : 2 * _tables.size();//初始化给10,后续扩容两倍
    
    				//选取素数
    				size_t newsize = GetNextPrime(_table.size());
    
    				//扩容之后,需要重新计算元素的位置
    
    				HashTable<K, V, HashFunc> newHT;
    				newHT._table.resize(newsize);
    
    				for (auto& e : _table)
    				{
    					if (e._state == EXIT)
    						newHT.Insert(e._kv);
    				}
    				_table.swap(newHT._table);//进行交换
    			}
    	
    			HashFunc hf;
    			size_t start= hf(kv.first) % _table.size();
    			size_t index = start;
    			//探测后面的位置,线性探测或二次探测
    			size_t i = 1;
    			while (_table[index]._state == EXIT)
    			{
    				index =start+i;
    				index %= _table.size();
    				++i;
    			}
    			_table[index]._kv = kv;
    			_table[index]._state = EXIT;
    			++_n;
    			return true;
    		}
    		HashData<K,V>* Find(const K& key)
    		{
    			if (_table.size() == 0) return nullptr;
    
    			HashFunc hf;
    			size_t start = hf(key) % _table.size();
    			size_t index = start;
    			size_t i = 1;
    			while (_table[index]._state != EMPTY)
    			{
    				if (_table[index]._state== EXIT
    					&&_table[index]._kv.first == key)
    				{
    					return &_table[index];
    				}
    				index = start + i;
    				index %= _table.size();
    				++i;
    			}
    			return nullptr;
    		}
    
    		bool Erase(const K& key)
    		{
    			HashData<K, V>* ret = Find(key);
    			if (ret == nullptr)
    			{
    				return false;
    			}
    			else
    			{
    				ret->_state = DELETE;
    				return true;
    			}
    		}
    
    	private:
    		vector<HashData<K,V>> _table;
    		size_t _n = 0;
    	};
    }
    

    五、开散列(哈希桶)

    开散列又名哈希桶/开链法,首先对关键码集合采用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表串联起来,各个链表的头节点存储在哈希表中
    在这里插入图片描述

    5.1. 开散列扩容

    与闭散列不同,开散列需要负载因子达到1的时候才进行扩容。
    因为在理想的情况下每个桶下面只有一个节点。哈希桶的载荷因子控制在1,当大于1的时候就进行扩容,这样平均下来,每个桶下面只有一个节点;

    与闭散列进行比较: 看起来哈希桶之中存储节点的指针开销比较大,其实不然。闭散列的负载因子需要保证小于0.7,来确保有足够的空间降低哈希冲突的概率,而表项的空间消耗远远高于指针所占的空间效率,因此哈希桶更能节省空间。

    5.2. 代码实现

    namespace OpenHash//开散列
    {
    	template<class K,class V>
    	struct HashNode
    	{
    		HashNode<K, V>*_next;
    		pair<K, V>_kv;
    		HashNode(const pair<K, V>& kv)
    			:_next(nullptr)
    			,_kv(kv)
    		{} 
    	};
    	template<class K>
    	struct  Hash
    	{
    		size_t operator()(const K& key)
    		{
    			return key;
    		}
    	};
    	template<>
    	struct  Hash<string>
    	{
    		size_t operator()(const string& s)
    		{
    			size_t value = 0;
    			for (auto ch : s)
    			{
    				value += ch;
    				value *= 131;
    			}
    			return value;
    		}
    	};
    	template<class K, class V, class HashFunc = Hash<K>>
    	struct HashTable
    	{
    	public:
    		typedef HashNode<K, V> Node;
    		Node* Find(const K& key)
    		{
    			HashFunc hf;
    			if (_table.size() == 0) return nullptr;
    			size_t index = hf(key) % _table.size();
    			Node* cur = _table[index];
    			//在桶中进行查找
    			while (cur)
    			{
    				if (cur->_kv.first == key)
    				{
    					return cur;
    				}
    				else
    				{
    					cur = cur->_next;
    				}
    			}
    			return nullptr;
    		}
    
    		bool Insert(const pair<K, V>& kv)
    		{
    			HashFunc hf;
    			if (Find(kv.first)) return false;//列表里已经存在kv
    
    			//负载因子到1时进行增容
    			if (_n == _table.size())
    			{
    				vector<Node*>newtable;
    				size_t newSize = _table.size() == 0 ? 10 : _table.size() * 2;
    				newtable.resize(newSize);
    
    				//遍历旧表中的节点,重新计算映射位置,挂到新表中
    				for (size_t i = 0; i < _table.size(); ++i)
    				{
    					if (_table[i])
    					{
    						Node* cur = _table[i];
    						while (cur)
    						{
    							//记录原来cur后面的节点
    							Node* next = cur->_next;
    							size_t index = hf(cur->_kv.first) % newtable.size();
    							//头插
    							cur->_next = _table[index];
    							_table[index] = cur;
    							cur = next;
    						}
    						_table[i] = nullptr;
    					}
    				}
    				_table.swap(newtable);
    			}
    			size_t index = hf(kv.first) % _table.size();
    			Node* newnode = new Node(kv);
    			newnode->_next = _table[index];
    			_table[index] = newnode;
    			++_n;
    		}
    		bool Erase(const K& key)
    		{
    			HashFunc hf;
    			size_t index = hf(key) % _table.size();
    			Node* prev = nullptr;
    			Node* cur = _table[index];
    			//在桶中找到对应的节点进行删除
    			while (cur)
    			{
    				if (cur->_kv.first == key)
    				{
    					//头结点的情况
    					if (_table[index] == cur)
    					{
    						_table[index] = cur->_next;
    					}
    					else
    					{
    						prev->_next = cur->_next;
    					}
    					--_n;
    					delete cur;
    					return true;
    				}
    				prev = cur;
    				cur = cur->_next;
    			}
    			//要删的节点不存在
    			return false;
    		}
    	private:
    		vector<Node*> _table;
    		size_t _n=0;//有效数据的个数
    	};
    }
    

    六、闭散列和开散列的比较

    1. 开散列处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短;
    2. 由于开散列中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况;
    3. 闭散列为减少冲突,要求负载因子α较小,故当结点规模较大时会浪费很多空间。而开散列中可取α≥1,且结点较大时,开散列中增加的指针域可忽略不计,因此节省空间;
    4. 在用开散列构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对闭散列构造的散列表,删除结点不能简单地将被删结点的空间置为空,否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中,空地址单元(即开放地址)都是查找失败的条件。因此在用开放地址法处理冲突的散列表上执行删除操作,只能在被删结点上做删除标记,而不能真正删除结点。实际删除操作待表格重新整理时在进行,这种方法也被称为惰性删除。

    资料参考:
    哈希表、哈希桶的实现
    哈希表底层探索
    数据结构之(一)Hash(散列)
    哈希之开散列,闭散列

    展开全文
  • 基数排序、桶排序和计数排序的区别

    万次阅读 多人点赞 2019-04-18 00:11:08
    1.桶排序(Bucket Sort) 基本思路是: 将待排序元素划分到不同的痛。先扫描一遍序列求出最大值 maxV 最小值 minV , 设桶的个数为 k ,则把区间 [minV, maxV] 均匀划分成 k 个区间,每个区间就是一个桶。将序列中的...
  • 442. 数组中重复的数据 ...由于a[i]的范围比较特殊,我们可以利用桶排序的思想来解决这道题。 即我们创建出一个数组hash当成‘桶’,并对其内元素都初始化为0,接着开始遍历数组,一旦hash[nums[i]]==0,
  • 之前一直分不清桶排序和基数排序,现在拿出来这两比较一下1、算法思路:桶排序桶排序(Bucket Sort)假设输入数据服从均匀分布,然后将输入数据均匀地分配到有限数量的桶中,然后对每个桶再分别排序,对每个桶再使用...
  • 哈希结构 哈希概念 常见的K-V结构,实现了元素关键码与元素值的映射关系,但没有实现元素关键值与元素存储位置的映射关系,在遍历过程中,一般的顺序表或搜索二叉树要进行关键值的多次比较,其中顺序表的时间...
  • 1.冒泡排序 2.插入排序 3.选择排序 4.归并排序 5.希尔排序 6.快速排序 7.堆排序 … 调用sort函数实现快速排序: //演示 #include <bits/stdc++.h> using namespace std; bool cmp(const int &...
  • 方法一:直接使用哈希表,通过重新定义sort函数的cmp方式,注意sort函数只能对pair为元素的vector数组排序,不能直接对map排序! class Solution { public: static bool cmp(pair<int, int>& m, pair&...
  • 桶排序(hash排序)

    万次阅读 2017-06-17 16:17:29
    让我们回忆一下数据结构课程上的内容,当数据量比较大而且内存无法装下的时候,我们可以采用外排序的方法来进行排序,这里我们可以采用归并排序,因为归并排序有一个比较好的时间复杂度O(NlgN)。 排完序之后我们...
  • 排序充斥着我们的生活,比如站队、排队买票、考试排名、公司业绩排名、将电子邮件按时间排序、QQ 好友列表中的会员红名靠前,等等。 这里先举个例子,通过这个例子让我们接触第 1 个算法。 在某个期末考试中,老师要...
  • 1、主要思想:桶排序的大体思路就是先将数组分到有限个桶中,再对每个桶中的数据进行排序,可以说是鸽巢排序的一种归纳结果(对每个桶中数据的排序可以是桶排序的递归,或其他算法,在桶中数据较少的时候用插入排序...
  • 桶排序及代码实现

    2022-03-31 22:14:24
    桶排序是一种用到了哈希表的排序方法。哈希表查找的方法是用取余做哈希函数,排序用取整做函数。 桶排序是计数排序的升级版,计数排序的索引是这个数字出现的次数,而桶排序则更加灵活,索引可以由哈希函数任意设置...
  • 算法的时间复杂度并不能代表算法的实际执行时间,...数据 经过哈希函数 计算出数据在哈希表中的位置,然后标记,方便之后的查找,它的时间复试度最快能达到:O(1)。 但是该算法有很大局限性,不适合浮点型、字符串型
  • 排序列表是数组和哈希表的组合,它包含一个可使用键或索引访问各项的列表,如果您使用索引访问各项,则它是一个动态数组(ArrayList),如果您使用键访问各项,则它是一个哈希表(Hashtable),集合中的各项总是按...
  • 645. 错误的集合 描述 集合 s 包含从 1 到 n 的整数。...桶排序哈希? 用数组记录原数组每个元素出现的次数,出现次数为0则为未出现,出现次数为2,则表示重复。 class Solution { public int[] f
  • 图解排序算法之(桶排序

    千次阅读 2018-06-17 23:23:50
    桶排序:桶排序(Bucket Sort)假设输入数据服从均匀分布,然后将输入数据均匀地分配到有限数量的桶中,然后对每个桶再分别排序,对每个桶再使用...由于桶排序和计数排序一样均对输入的数据进行了某些假设限制,因此...
  • 这种思想相当于桶排序,为每个值设立一个桶,桶内记录这个值出现的次数,然后对桶进行排序。我们先通过桶排序得到三个桶 [1,2,3,4],它们的值分别 为 [4,2,1,1],表示每个数字出现的次数。紧接着,我们对桶的频次...
  • C++希尔排序、桶排序

    2021-07-05 18:44:07
    记录一下希尔排序和桶排序,方便以后复习。
  • 十大排序--桶排序

    2022-03-31 15:04:05
    简介明了,通俗易懂的讲解十大排序算法之桶排序
  • LeetCode面试题 01.02. 判定是否互为字符重排的三种解法:哈希排序
  • golang桶排序

    千次阅读 热门讨论 2020-10-31 09:11:44
    看一下golang桶排序代码,很简单。通过哈希表实现,先用哈希表存值,在通过哈希表的下标进行遍历,通过哈希表进行了排序 package main import ( "fmt" "container/list" ) func bucketSort(theArray []int,...
  • 代码02:BucketSort,Java接口简介,面向对象的设计,泛型,存储桶排序。 代码03:使用迷宫求解器队列堆栈搜索迷宫,提供了10个迷宫文件,从maze1.txt到maze10.txt。 代码04:散列字符串,使用多项式将字符串...
  • ⭐️博客哈希和哈希桶完整代码已上传至gitee:https://gitee.com/byte-binxin/cpp-class-code 目录概念哈希函数哈希冲突哈希冲突的解决闭散列概念哈希表闭散列的实现(采用线性探测)哈希表整体框架插入元素查找...
  • 时间复杂度为O(n)的排序算法有计数排序、基数排序和桶排序,三者的基本思想差不多,某种意义上都是一种哈希算法,通过把无序数组的元素哈希到有序键值上实现排序。 计数排序由于空间消耗过大,在此不予考虑。 ...
  • 桶排序

    2017-08-03 15:40:37
    【算法】桶排序 标签: 排序算法桶排序 2015-11-19 13:18 1413人阅读 评论(1) 收藏 举报 分类: java(32) 作者同类文章X Data Structure And Algorithm(14) 作者同类文章X 目录(?)...
  • 本文从最简单的一个排序算法——桶排序开始,分析桶排序的实现思路,代码实现,性能特点以及适用场景。0、其他排序算法索引(待更)1、桶排序思想一个简单例子:对6个人的英语测试成绩(1~10分)进行排序。假如分数是[6,...
  • 然后遍历哈希表,同时进行桶排序,以链表的形式把二维数组中每个单词的地址存在桶里。最后输出桶中数据即可。 本函数在code::blocks17.12中运行正常。 #include <stdio.h> #include <stdlib.h> #define ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 21,934
精华内容 8,773
关键字:

哈希排序和桶排序