精华内容
下载资源
问答
  • 算法的时间复杂度并不能代表算法的实际执行时间,...数据 经过哈希函数 计算出数据在哈希表中的位置,然后标记,方便之后的查找,它的时间复试度最快能达到:O(1)。 但是该算法有很大局限性,不适合浮点型、字符串型

    算法的时间复杂度并不能代表算法的实际执行时间,有些时候看似复杂度高的速度反面快。

    查找算法:
    顺序查找:
    对待查找的数据没有要求,时间复杂度: O(n)
    二分查找:
    对待查找的数据必须有序,时间复杂度: O(logn)
    块查找:
    是一种数据处理的思想,不是特定的算法,当数据量过多时,可以先把数据进行分块处理,然后再进行查找,例如英语词典。
    哈希查找:
    数据 经过哈希函数 计算出数据在哈希表中的位置,然后标记,方便之后的查找,它的时间复试度最快能达到:O(1)。
    但是该算法有很大局限性,不适合浮点型、字符串型数据,需要额外的存储空间,空间复杂度高,是一种典型的用空间换取时间的算法。

    哈希函数设计方法:
    直接定址法:把数据直接当作数组的下标。
    数字分析法:分析数据的特点来设计哈希,常用的方法就是找到最大值与最小值,最大值-最小值+1来确定哈希表的长度,数据-最小值访问哈希表。

    在这里插入图片描述

    排序算法:
    冒泡:数据左右进行比较,把最大的数据交换到最后,特点是该算法对数据的有序性敏感,在排序过程中可以立即发现已经完成。
    时间复杂度:O(n),O(n^2)
    稳定

    // 冒泡排序
    void bubble_sort(TYPE* arr,size_t len)
    {
    	bool flag = true;
    	for(int i=len-1; i>0 && flag; i--)
    	{
    		flag = false;
    		for(int j=0; j<i; j++)
    		{
    			if(arr[j] > arr[j+1])
    			{
    				swap(arr[j],arr[j+1]);
    				flag = true;
    			}
    		}
    	}
    	show_arr(arr,len);
    	printf(":%s\n",__func__);
    }
    

    选择:假定最开始的位置是最小值并记录下标min,然后与后面的数据进行比较,如果有比以min为下标的数据小的则min的更新,最后如果min的如果发生改变,则交换min与最开始位置的数据,虽然时间复杂度挺高的,但数据交换的次数比较小,因此实际运行速度并不慢(数据交换比数据比较耗时)。
    时间复杂度:O(n^2)
    不稳定

    // 选择排序
    void select_sort(TYPE* arr,size_t len)
    {
    	for(int i=0; i<len-1; i++)
    	{
    		int min = i;
    		for(int j=i+1; j<len; j++)
    		{
    			if(arr[j] < arr[min]) min = j;
    		}
    		if(i != min) swap(arr[i],arr[min]);
    	}
    	show_arr(arr,len);
    	printf(":%s\n",__func__);
    }
    

    插入:把数据看作两部分,一分部是有序,把剩余的数据逐个插入进行,适合对已经排序后的数据,新增数据并排序。
    时间复杂度:O(n^2)
    稳定

    // 插入排序
    void insert_sort(TYPE* arr,size_t len)
    {
    	for(int i=1,j=0; i<len; i++)
    	{
    		int val = arr[i];
    		for(j=i; j>0 && arr[j-1] > val; j--)
    		{
    			arr[j] = arr[j-1];
    		}
    		if(j != i) arr[j] = val;
    	}
    	show_arr(arr,len);
    	printf(":%s\n",__func__);
    }
    

    希尔:是插入排序的增加版,由于插入排序时,数据移动的速度比较发慢,所以增加了增量的概念,以此来提高排序速度。
    时间复杂度:O(nlogn)
    不稳定

    // 希尔排序
    void shell_sort(TYPE* arr,size_t len)
    {
    	for(int k=len/2; k>0; k/=2)
    	{
    		for(int i=k,j=0; i<len; i++)
    		{
    			int val = arr[i];
    			for(j=i; j-k>=0 && arr[j-k] > val; j-=k)
    			{
    				arr[j] = arr[j-k];
    			}
    			if(j != i) arr[j] = val;
    		}
    	}
    	show_arr(arr,len);
    	printf(":%s\n",__func__);
    }
    

    快速:找到一个标杆,一面从左找比标杆大的数据,找到后把放在标杆的右边,另一个从右边找比标杆小的数据,找到后把放在标杆的左边,最终标杆左边的数据都比它小,右边的数据都比它大,这样就整体有序,然后按同样的方法排序标杆左边的数据和标杆右边的数据。
    它的综合性能最高,因此叫快速排序,笔试时考的最多的排序。
    时间复杂度:O(nlogn)
    不稳定

    void _quick_sort(TYPE* arr,int left,int right)
    {
    	if(left >= right) return;
    	int l=left,r=right;
    	TYPE pv = arr[l];
    	while(l<r)
    	{
    		while(l<r && arr[r] >= pv) r--;
    		arr[l] = arr[r];
    		while(l<r && arr[l] <= pv) l++;
    		arr[r] = arr[l];
    	}
    
    	arr[l] = pv;
    	_quick_sort(arr,left,l-1);
    	_quick_sort(arr,l+1,right);
    }
    
    void quick_sort(TYPE* arr,size_t len)
    {
    	_quick_sort(arr,0,len-1);
    	show_arr(arr,len);
    	printf(":%s\n",__func__);
    }
    

    归并:先一组把数据拆分成单独的个体,然后按从小到大的顺序进行合并,由于需要使用额外的内存空间因此避免的数据交换的耗时,也是一种典型的用空间换取时间的算法,可递归实现也可以循环实现。
    时间复杂度:O(nlogn)
    稳定

    // 合并
    void merge(TYPE* arr,TYPE* tmp,int l ,int p , int r)
    {
    	if(arr[p] < arr[p+1]) return;
    
    	int k = l , i = l , j = p+1;
    	while(i<=p && j<=r)
    	{
    		if(arr[i] < arr[j])
    			tmp[k++] = arr[i++];
    		else
    			tmp[k++] = arr[j++];
    	}
    	while(i<=p) tmp[k++] = arr[i++];
    	while(j<=r) tmp[k++] = arr[j++];
    	//while(l<=r) arr[l] = tmp[l++]; 
    	memcpy(arr+l,tmp+l,sizeof(TYPE)*(r-l+1));
    }
    
    // 拆分
    void _merge_sort(TYPE* arr,TYPE* tmp,int l,int r)
    {
    	if(l >= r) return;
    	int p = (l+r)/2;
    	_merge_sort(arr,tmp,l,p);
    	_merge_sort(arr,tmp,p+1,r);
    	merge(arr,tmp,l,p,r);
    }
    
    // 归并
    void merge_sort(TYPE* arr,size_t len)
    {
    	TYPE* tmp = malloc(sizeof(TYPE)*len);
    	_merge_sort(arr,tmp,0,len-1);
    	free(tmp);
    	show_arr(arr,len);
    	printf(":%s\n",__func__);
    }
    
    void merge_for_sort(TYPE* arr,size_t len)
    {
    	TYPE* tmp = malloc(sizeof(TYPE)*len);
    	TYPE* src = arr , *des = tmp;
    
    	for(int s=1; s<len; s*=2)
    	{
    		for(int l=0; l<len; l+=s*2)
    		{
    			int r = (l+s*2<len)?l+s*2:len;
    			int p = (l+s<len)?l+s:len; 
    			int k = l , i = l , j = p;
    			while(i<p && j<r)
    			{
    				if(src[i] < src[j])
    					des[k++] = src[i++];
    				else
    					des[k++] = src[j++];
    			}
    			while(i<p) des[k++] = src[i++];
    			while(j<r) des[k++] = src[j++];
    		}
    		swap(des,src);
    	}
    	if(src != arr) memcpy(arr,src,sizeof(TYPE)*len);
    	free(tmp);
    
    	show_arr(arr,len);
    	printf(":%s\n",__func__);
    }
    

    堆:把数据当作完全二叉树,然后树中调整为大根树,然后把根节点交换到最后,然后数量–,然后再调整为大根树,直到数量为1时结束,可递归实现也可以循环实现。
    时间复杂度:O(nlogn)
    不稳定

    void create_heap(TYPE* arr,int root,size_t len)
    {
    	if(root >= len) return;
    	int left = root*2+1 , right = root*2+2;
    	create_heap(arr,left,len);
    	create_heap(arr,right,len);
    	if(right < len && arr[left] < arr[right])
    		swap(arr[left],arr[right]);
    	if(left < len && arr[root] < arr[left])
    		swap(arr[root],arr[left]);
    }
    
    void heap_sort(TYPE* arr,size_t len)
    {
    	create_heap(arr,0,len);	
    	for(int i=len-1; i>0; i--)
    	{
    		swap(arr[0],arr[i]);
    		create_heap(arr,0,i);
    	}
    
    	show_arr(arr,len);
    	printf(":%s\n",__func__);
    }
    
    void heap_for_sort(TYPE* arr,size_t len)
    {
    	for(int i=len-1; i>0; i--)
    	{
    		int p = (i+1)/2-1;
    		if(arr[i] > arr[p]) swap(arr[i],arr[p]);
    	}
    	show_arr(arr,len);
    	printf("\n");
    
    	for(int i=len-1; i>0; i--)
    	{
    		swap(arr[0],arr[i]);
    		for(int j=0; j<i; j++)
    		{
    			if(j*2+2<i && arr[j*2+1]<arr[j*2+2])
    			{
    				swap(arr[j*2+1],arr[j*2+2])
    			}
    			if(j*2+1<i && arr[j]<arr[j*2+1])
    			{
    				swap(arr[j],arr[j*2+1])
    			}
    		}
    	}
    	show_arr(arr,len);
    	printf(":%s\n",__func__);
    }
    

    计数:找出数据中的最大值和最小值,创建哈希表,把数据-最小值当作数组中的下标访问哈希表并标记数量,然后遍历哈希表,当表中的值大于时,把下标+最小值依次放入数组中,是一种典型的用空间换取时间的算法。
    该排序算法理论上速度非常快,但有很大局限性,适合排序整型数据,而且数据的差值不宜过大,否则会非常浪费内存,数据越平均、重复数越多,性价比越高。
    时间复杂度:O(n+k);
    稳定

    void count_sort(TYPE* arr,size_t len)
    {
    	TYPE min = arr[0] , max = arr[len-1];
    	for(int i=0; i<len; i++)
    	{
    		if(arr[i] < min) min = arr[i];
    		if(arr[i] > max) max = arr[i];
    	}
    	TYPE* tmp = calloc(sizeof(TYPE),max-min+1);
    	for(int i=0; i<len; i++)
    	{
    		tmp[arr[i]-min]++;
    	}
    	for(int i=0,j=0; i<=max-min; i++)
    	{
    		while(tmp[i]--)
    		{
    			arr[j++] = i+min;
    		}
    	}
    	free(tmp);
    	show_arr(arr,len);
    	printf(":%s\n",__func__);
    }
    

    桶:把数据根据值,存储到不同桶中,然后再调用其它排序函数,对桶中的数据进行排序,然后再拷贝到数组中,以到降低排序规模来提高排序的时间,是一种典型的用空间换取时间的算法。
    时间复杂度:O(n+k);
    稳定

    void _bucket_sort(TYPE* arr,size_t len,int cnt,TYPE range)
    {
    	TYPE* bucket[cnt],*bucketed[cnt];
    	for(int i=0; i<cnt; i++)
    	{
    		bucket[i] = malloc(sizeof(TYPE)*len);
    		bucketed[i] = bucket[i];
    	}
    
    	for(int i=0; i<len; i++)
    	{
    		for(int j=0; j<cnt; j++)
    		{
    			if(range*j<=arr[i] && arr[i]<range*(j+1))
    			{
    				*(bucketed[j]) = arr[i];
    				bucketed[j]++;
    			}
    		}
    	}
    	for(int i=0; i<cnt; i++)
    	{
    		int size = bucketed[i]-bucket[i];
    		if(size > 1) count_sort(bucket[i],size);
    		memcpy(arr,bucket[i],sizeof(TYPE)*size);
    		arr += size;
    		free(bucket[i]);
    	}
    }
    
    void bucket_sort(TYPE* arr,size_t len)
    {
    	_bucket_sort(arr,len,4,25);	
    	show_arr(arr,len);
    	printf(":%s\n",__func__);
    }
    

    基数:是桶排序的具体实现,首先创建10个队列(队列),然后逆序计算出数据的个十百… 然后压入到对应的队列中,然后再从队列中弹出存储的数组中,当下标为0队列中有len个数据时,排序结束。
    时间复杂度:O(n+k);
    稳定

    void radix_sort(TYPE* arr,size_t len)
    {
    	ListQueue* queue[10] = {};
    	for(int i=0; i<10; i++)
    	{
    		queue[i] = create_list_queue();
    	}
    
    	for(int i=1; i<=10&&size_list_queue(queue[0])<len; i++)
    	{
    		int mod = pow(10,i);
    		int div = mod / 10;
    
    		for(int j=0; j<len; j++)
    		{
    			int index = arr[j]%mod/div;
    			push_list_queue(queue[index],arr[j]);
    		}
    		int k = 0;
    		for(int j=0; j<10; j++)
    		{
    			while(!empty_list_queue(queue[j]))
    			{
    				arr[k++] = head_list_queue(queue[j]);
    				pop_list_queue(queue[j]);
    			}
    		}
    	}
    	for(int i=0; i<10; i++)
    	{
    		destory_list_queue(queue[i]);
    	}
    
    	show_arr(arr,len);
    	printf(":%s\n",__func__);
    }
    

    如何判断排序算法是否稳定:
    待排序的数组中,如果有值相同的数据,排序过程中如果不会改它们的前后顺序,则认为该排序算法稳定。

    展开全文
  • 然后遍历哈希表,同时进行桶排序,以链表的形式把二维数组中每个单词的地址存在桶里。最后输出桶中数据即可。 本函数在code::blocks17.12中运行正常。 #include <stdio.h> #include <stdlib.h> #define ...

    先用一个二维数组(char**)存储所有单词列表,然后用哈希函数计算每个单词的哈希值,存入哈希表中。然后遍历哈希表,同时进行桶排序,以链表的形式把二维数组中每个单词的地址存在桶里。最后输出桶中数据即可。
    本函数在code::blocks17.12中运行正常。

    #include <stdio.h>
    #include <stdlib.h>
    #define wordnum 450
    #define tablecapacity 1087
    #define barrelcapacity 40
    
    //哈希表内每个元素
    typedef struct HashEntity{
        char* s;//该字符串
        int times;//该字符出现的次数(题目要求)
        int distance;//存在哈希表中的偏移位置。默认为0
        int deleted;//1表示被删除,0表示未被删除
    }HashEntity;
    
    //哈希表
    typedef struct HashTable{
        HashEntity* data;
        int tablesize;
    }HashTable;
    
    //桶排序里的节点
    typedef struct node{//桶排序以链表为实现方式
        char* data;//单词地址
        struct node* pNext;//链接到下一个节点
    }node;
    
    node* barrel[barrelcapacity];//node*格式的40个桶
    
    char str[]="Throwing the spotlight on whether purchase a high-technology device when it first released, Some individuals accepts that enjoying the latest device makes possible to release the high pressure and sense the high technology, while the dismiss as exaggeration waiting some time can bring more benefit for them. However, I reckon that I will buy a electronic device when most people adopt it  for the follow reasons and examples.First and foremost, compared with **immediately** experience a new released device, waiting for several month in favor for individuals of saving money. Set the first **price** of the high technology products really high, which would haven been **expelled** by the competitive market, the company constantly leaves a high quality imagine for the product and even can advertise their identical product idea which require **customer** cast most money on it. For instance, when iPhone 6 first released, Its price is more than five thousand but I did not think it worth that money. As a result, I purchased it less than four thousand for six months.What is more, in term of the sense of operating the device, a **machine** have been put into the market is useful and people can exploit the new function of it. Everyone attempt to exploit the latest technology that applying to electronic products to sense the **convenient** of the modern society, but only few of them realize that without the software matching with the device, the main function cannot be exert. The superiority of purchasing the product after it released for several months is that the software developers are given chance to craft something **amazing** and embody the now function of the device. The point in case is that when the **HoloLens** first released, only the original system can be operated which is elusive and difficult to operate the subtle objects. However, several months latter, some software enterprise and single software developer **respectively** design the new operation system and applications to display the world of **virtual reality.**In addition, I am not deny that people who prefer to purchase the new high-technology device immediately do something wrong. It is universal acknowledge that the the electronic products renew faster than other **products** which makes people who wait for long time miss the developing process of technology. Nonetheless, it is the minor factor for us students when compared with saving money and a stable operating experience.After all discussion above, we can safely draw the conclusion that purchasing an electronic product until most people adopt is pave the way for individuals to save money and enjoy a **desirable** using experience.";
    
    ///单词处理:分割单词
    char** sparate_words(){
        int i=-1;//对str[i]的计数器
        int j=0;//对单词内每个字母的计数器word[][j]
        int k=0;//对单词个数的计数器word[k][]
        int lock=0;//进入单词的触发器
        char** word=(char**)malloc(wordnum*sizeof(char*));//大约50个词
        memset(word,0,wordnum*sizeof(char*));
        while(str[++i]!='\0'){
            if(lock==0){//1. 未记录单词时
                if((str[i]>='a'&&str[i]<='z')||(str[i]>='A'&&str[i]<='Z')){//1.1 遇到字母
                    lock=1;//开始记录
                    word[k]=(char*)malloc(10*sizeof(char));//开辟新的一片空间
                    word[k][j++]=str[i];//把这个字母录入
                    continue;
                }
            }else if(lock==1){//2. 正在记录单次时
                if((str[i]>='a'&&str[i]<='z')||(str[i]>='A'&&str[i]<='Z')){//2.1 遇到字母
                    word[k][j++]=str[i];//记录字母
                    continue;
                }else if(str[i]==' '||str[i]==','||str[i]=='.'||str[i]=='?'||str[i]=='!'||str[i]=='\''){//2.2 遇到空格或符号
                    lock=0;//结束记录
                    word[k++][j]='\0';//添加结束符,前进单词计数器
                    j=0;//重置字母计数器
                }
            }
        }
        return word;
    }
    
    ///单词处理:打印单词列表
    void read_word_list(char** word){
        for(int i=0;i<wordnum;i++){
            printf("%s\n",word[i]);
        }
    }
    
    ///哈希表:利用位移法(秦九韶算法)实现的散列函数
    int hash(char* s,int tablesize){
        unsigned int res=0;
        char temp;
        int i=0;
        while(s[i]!='\0'){
            temp=s[i++];
            res=(res<<5)+(int)temp;//<<5就是乘以32的意思
        }
        printf("res=%d\n",res%tablesize);
        return res%tablesize;
    }
    
    ///哈希表:创建一个哈希表
    HashTable* create_hashtable(int tablesize){
        HashTable* newtable=(HashTable*)malloc(sizeof(HashTable));
        memset(newtable,0,sizeof(HashTable));
        newtable->tablesize=tablesize;
        newtable->data=(HashEntity*)malloc(tablesize*sizeof(HashEntity));
        memset(newtable->data,0,tablesize*sizeof(HashEntity));
        return newtable;
    }
    
    ///哈希表:给哈希表插入数值
    void insert_to_hashtable(HashTable* table,char* x){
        if(x==0){
            return;
        }
        printf("%s\n",x);
        int hashvalue=hash(x,table->tablesize);
        int crash=0;//冲突数
    
        while(table->data[hashvalue+crash].s!=0){//此处data[hash+crash]已被占有
            if(strcmp(table->data[hashvalue+crash].s,x)==0){//但是已占有的就是已经出现过的这个
                printf("在[%d]处已有\n",hashvalue+crash);
                table->data[hashvalue].times++;
                return;
            }
            crash++;
        }
        if(table->data[hashvalue+crash].s==0){//此处data[hash+crash]还没有被占用
            printf("添加到[%d]处\n",hashvalue+crash);
            table->data[hashvalue+crash].s=x;
            table->data[hashvalue+crash].distance=crash;
            table->data[hashvalue+crash].times=0;
            table->data[hashvalue+crash].deleted=0;
            return;
        }
    }
    
    ///哈希表:打印整个哈希表
    void print_hashtable(HashTable* table){
        for(int i=0;i<tablecapacity;i++){
            if(table->data[i].s==0){
                continue;
            }
            printf("%s   出现了",table->data[i].s);
            printf("%d次\n",table->data[i].times+1);
            add_to_barrel(table->data[i].s,table->data[i].times+1);
        }
    }
    
    ///桶排序:把x插入到桶的x位置
    void add_to_barrel(char* x,int key){
        node* position;
        position=barrel[key];
        while(1){
            if(position->data==NULL){
                position->data=x;
                position->pNext=(node*)malloc(sizeof(node));
                position->pNext->data=NULL;
                position->pNext->pNext=NULL;
                break;
            }else if(position->data!=NULL){
                position=position->pNext;
            }
        }
    }
    
    ///桶排序:输出桶中的内容
    void print_barrel_sort(){
        node* pnode;
        for(int i=barrelcapacity-1;i>=0;i--){
            pnode=barrel[i];
            printf("%d次:",i);
            while(pnode->data!=NULL){
                printf("%s/ ",pnode->data);
                pnode=pnode->pNext;
            }
            if(pnode->data==NULL){
                printf("\n");
                continue;
            }
        }
    }
    
    ///桶排序:初始化
    void init_barrel(){
        for(int i=0;i<barrelcapacity;i++){
            free(barrel[i]);
            barrel[i]=(node*)malloc(sizeof(node));
            barrel[i]->data=NULL;
            barrel[i]->pNext=NULL;
        }
    }
    
    
    int main()
    {
        char** word=sparate_words();
        HashTable* table=create_hashtable(tablecapacity);
        for(int i=0;i<wordnum;i++){
            printf("\n>>>>i=%d\n",i);
            insert_to_hashtable(table,word[i]);
        }
        init_barrel();
        print_hashtable(table);
        print_barrel_sort();
    }
    
    
    展开全文
  • 桶排序

    热门讨论 2016-07-24 13:19:13
     米老师再给我们将桶排序之前,把桶排序和选择排序的运行效果进行比较,发现桶排序的速度比选择排序快很多,然后就对排序有了很浓的兴趣,想知道它的原理,为什么会那么快。同时也到网上淘了本《哈希算法》,真所谓...

    前言

             软考考了两次还是没有过,主要是因为还没有找到学习算法的技巧,米老师着急了,再一次给我上了一节算法课。

     

    兴趣是最好的老师

          米老师再给我们将桶排序之前,把桶排序和选择排序的运行效果进行比较,发现桶排序的速度比选择排序快很多,然后就对排序有了很浓的兴趣,想知道它的原理,为什么会那么快。同时也到网上淘了本《哈希算法》,真所谓是兴趣是最好的老师。接下来米老师给我们讲了桶排序,觉得挺简单的,可是自己回来敲的时候也可谓是一波三折啊。

     

    桶排序概述

           桶排序也叫箱排序,工作原理是将数组分到有限数量的桶子里。每个桶子再个别排序。比如:有5,3,5,2,8,需要对这组数用桶排序进行比较,这个时候我们可以先定义0-10个桶,桶的编号为0-10,再把数字放到所对应的桶中,并给相应的桶进行计数。5就放在第5个桶,这个时候就给第5个桶标上1,3的时候就放在第三个桶里,然后在第三个桶标上1,3后面的5是第二次出现,在第5个桶上再加1,也就是二了,依次类推下去。这个时候呢已经把这个5个数放在桶子里了,我们就可以桶的记号大于0的桶拿出来,如果记号为1就拿出一次,如果是二就拿出两次,到最后,你会发现拿出来的桶的编号就是排序好的数组了。如图所示


     

    实践

       说了那么多,不到代码中练练也是不行滴。

      

    <span style="font-size:18px;"> public static void Main(string[] args)
                
            {
              
                
                int[] a = new int[11];//定义11个桶,编号从0-10,也就是有11个变量
                for (int i = 0; i <= 10; i++)//遍历11个桶
                {
                    a[i] = 0;//对桶进行初始化
                }
    
                int t = 0;//定义某一个桶的初值为0
    
                Console.WriteLine("程序启动,请准备输入成绩!");
    
                for (int  i = 0; i < 5; i++)//遍历输入5个学生的成绩
                {
                    Console.WriteLine("请输入【学生" + (i + 1).ToString() + "】的成绩:");//因为对应的桶最大的数是10 所以不能输入比10大的数
                    t = Convert.ToInt32(Console.ReadLine());//把输入的成绩放入对应的桶中
                    a[t] = a[t] + 1;//对桶进行计算,每放进一个数加一
                }
    
                Console.WriteLine("成绩输入完成,进行桶排序!");
    
                Console.WriteLine("桶排序:");
                for (int i = 0; i <=10; i++)//依次判断这11个所对应了多少次成绩
                {
                    if (a[i] != 0)//判断桶内是否有成绩
                    {
                        for (int j = 1; j <= a[i]; j++)//循环遍历桶的下标值,也就是桶所对应的成绩
                        {
                            Console.WriteLine(i); 
                        }
                       
                    }             
                }
                
                Console.WriteLine("请按任意键退出!");
                Console.ReadKey();
            }</span>

    总结

            桶排序在数字分布均匀的情况下是挺快的,但如果在类似于 1,6, 18888这样的数组中也是够呛的,那么我们又改用什么样的算法来将这组数进行排序呢?性能优化必然涉及到算法,看来在什么情况下选择使用什么样的算法是一个很重要的问题,但是前提是我们也要对这些算法熟悉。继续往下学吧。

    展开全文
  • 哈希函数和哈希

    2021-01-16 11:00:42
    哈希函数和哈希表? 哈希函数和哈希表是非常重要的内容,在面试的时候最经常使用。尤其是辅助作用。 哈希函数的算法的原理是超纲的内容(底层的实现是位运算),常见的哈希算法有扩展MD5(返回2^ 64)、SHA1(返回2^...

    哈希表实现源码
    C++中以哈希表为底层数据结构的容器

    哈希函数和哈希表?

    哈希函数算法的原理是超纲的内容(底层的实现是位运算),常见的哈希算法有扩展MD5(返回2^ 64)、SHA1(返回2^128)(哈希函数的实现有数千种实现方法)

    什么是哈希函数(散列函数)

    1) 输入域是无限的。
    2) 输出域虽然很大,但是有限的。
    3) 哈希函数不是随机函数,没有任何的随机成分。相同的输入值,一定得到相同的输出值。
    4) 因为输入域是无限的,输出域是有限的,必然有不同的输入对应相同的输出。(哈希碰撞)
    5) 离散性:虽然输入域是无穷大,输出域是s,但是不同的输入如果想要得到整个s域上所有的返回值,在整个s域上的返回值会几乎均匀分布。 (均衡性越好->离散性越好->函数越优良)

    哈希函数特点

    1)与输入的规律没有关系,否则就没有办法做到均匀性了
    2)作用是打乱输入规律,但不是随机的,没有任何随机因素
    3)得到的哈希code取模后同样是均匀的。取余m,那么在0~m-1上也是均匀分布

    要求让你找1000个独立的哈希函数,那你会怎么办?

    去找hash函数库吗?错了。应该把得到的16个16进制的数分成两部分,高八个(h1)与低八个(h2)是独立的,可以用h1+n*h2来构造不同的哈希函数或者是找两个哈希函数进行组合计算。

    可以认为哈希code中每个位都是独立的,所以通过每个位置元素的组合本身就可以得到许多哈希函数。

    哈希表(散列表)的经典结构

    哈希表开头就是哈希域,这个一般是经过我们压缩了的哈希域,但可以保证离散性。
    经典结构:哈希前面的哈希域作为桶,后面挂一个链表。当容量不够的时候,进行扩容。会先分配一个空间(桶)(例如17个空间),如果是put一个记录,那么就会将key1拿出来计算hash code,然后拿着这个值取模17,然后将这个键值对挂在对应的位置下,如果冲突了,首先检查在对应位置上是否有后面加入的key,如果有就直接修改key对应的值为新值,如果不存在那么就像一个链表一样往后挂。即相同的key是不额外占用空间的,不同的key占用额外空间。因为哈希函数的性质,所以我们可以近似认为每个链表都是均匀增长的,如果达到指定的长度之后(随着每条链表的长度增加,操作效率就会降低),我们就进行哈希扩容,桶的个数增加一倍,先将每一个数据拿出来之后重新进行计算然后取模,重新寻找他在哪个桶里,完成。一般情况下默认哈希表的增删改查都是O(1)的,但是常数项比较大,和已有的数据量是无关的,因为哈希函数在计算的时候代价比较高。

    开放地址法:如果一个桶被占用了,就顺序向下移动。用完之后就进行扩容。

    扩容不需要代价吗?你为什么说自己可以做到O(1)?

    当我们将不同的数据挂到哈希域中之后,我们发现我们查找的难度就小了,因为我们只需要根据需要查的值计算出它所挂的域,然后我们就在指定的域开始遍历链表,就成了,但是如果随着数据量的增大, 导致我们每个链表的长度都很大,这样我们可以扩展哈希表,降低每个链表的查询难度,扩容的时间复杂度可以做到O(1)。扩容之后需要重新计算每个数据需要挂载的位置(O(N))。扩容的时候是可以离线的,也就是说,扩容的时候你想查,那么我就让你查旧结构(虽然慢,但是可以查),新结构创建好之后,在让你查新结构。

    一方面,样本量N,如果每次扩容都翻倍,那么我们需要进行log(n)次,如果增加5倍,所以扩容的代价平均下来很低。你会说那也不至于是O(1)吧?!实际在使用过程中可以进行离线扩容,也就是说在扩容的时候,不妨碍你查询老结构,等到新结构建立起来之后就可以使用新结构了。这样就不需要占用在线时间了。所以说hash的增删改查是O(1)的。离线是怎么做到的?这个技巧一般使用在服务器上的,在JAVA中所有的结构都是JVM托管的,在C++中可能就要忍受log5(N)的代价了。

    哈希表的增删改查都是O(1),因为我们可以做到离线扩容,他在数学上肯定不是O(1)。经典结构本身就是存在扩容代价,但实际上可以通过各种优化策略来大幅度降低这个代价,所以可以认为O(1),但是常数项比较大,原因是哈希函数在计算的时候代价比较高。

    C++实现中的具体问题

    虽然开链法不要求表格大小必须为质数,但是在linuxC++中,仍然以质数来设计表格的大小,并且先将28个质数计算好,以备随时访问。所以STL中以哈希表为底层数据结构的所有容器,当他们满载后,扩容不是几倍几倍增长的。
    clear操作并不会影响到哈希表的桶子大小,只是将链表中的数据释放了。

    面试题:

    假设有一个大文件,每一行都是一个字符串,无序的,文件大小为100T,我想把这个文件中重复的字符串打印出来。问你怎么做?

    如果你单CPU,单核,一台机器,去完成这件事情,那就废了。

    方法:通过哈希来分流。 首先,应该问面试官,“你给我多少台机器?”,他说:我给你1000台机器来做这件事情。然后把机器标好号,从0到999。随后问面试官文件存在于哪儿?告诉你存在于一个分布式文件系统上,然后问他“那我要想按行读取文件是不是有效率非常高的工具啊?”,他告诉你,有!。最后将每一行读出来,让后计算其hashcode,然后模上1000,模出来的值对应处理他的机器编号。这样我就将所有不同的字符串均分到1000台机器上。而且相同的文本一定会分配到一台机器上。然后在一台机器上完成重复检查。这样很快。如果还是太大,那么就再次通过哈希函数来实现多任务处理。使用哈希函数来做分流,相同输入导致相同输出,不同输入导致均匀分布的特征。

    展开全文
  • Description 在n个数中,找出出现次数最多那个数字,并且输出出现的次数...出现次数最多的数字次数。 Sample Input 3 1 1 2 Output 1 2 #include <bits/stdc++.h> using namespace std; int main() { int a
  • 借助 哈希表 来建立数字其出现次数的映射,遍历一遍数组统计元素的频率 维护一个元素数目为 k 的最小堆 每次都将新的元素与堆顶元素(堆中频率最小的元素)进行比较 如果新的元素的频率比堆顶端的元素大,则弹出堆...
  • 参考:https://github.com/jackfrued/Python-100-Days/blob/master/Day16-20数据结构算法算法:解决问题的方法步骤评价算法的好坏:渐近时间复杂度渐进空间复杂度渐近时间复杂度的大o标记:O(c)-常量时间...
  • 浅显易懂的桶排序

    2016-05-11 12:06:00
    想准备将所有的排序算法都总结出来,方便你查阅,也方便我复习和记忆,下面来说桶排序: 首先必须申明,桶排序和计数排序完全不同,不可混为一谈:(这里实例用单链表来操作) 还是老方法,看文字就是烦,直接上图...
  • 代码02:BucketSort,Java接口简介,面向对象的设计,泛型,存储桶排序。 代码03:使用迷宫求解器队列堆栈搜索迷宫,提供了10个迷宫文件,从maze1.txt到maze10.txt。 代码04:散列字符串,使用多项式将字符串...
  • 散列 call by value 通过值去索引。 java 中有 HashMap散列 Hashtable散列表 利用key-value pair存到相应的位置。 python 中有 dictionary字典 利用hashtable 数据结构算法是硬币的两面...哈希算法: 如果...
  • Python实现8大排序算法

    2019-08-01 23:03:21
    8大算法:冒泡排序,选择排序,插入排序,快速排序,堆排序,归并排序,哈希排序桶排序(未实现) 制造一个计数器模拟个无序列表: # 计时器: import time def cal_time(func): def wapper(*args,**kwargs)...
  • 一、桶排序 桶排序中的两种排序思想:计数排序和基数排序
  • 自己整理的用C语言写的数据结构和排序查找算法。数据结构包括:栈,队列,两...算法包括:10个排序(冒泡,插入,选择,快排,归并,排,希尔等),5个插入(直接插入,哈希,对于KMP SUNDAY 字典树 可能整理的不全)
  • Hive分

    2020-02-17 14:20:55
    语法:创建表时使用clustered子句指定要分的字段的数量,也可以指定排序。 clustered by(字段名) sorted by (排序字段) into 数量 buckets 二:示例 1. 创建分表 create table tbl_bucket(...
  • 计数排序

    2019-05-03 16:24:00
     计数排序类似与桶排序,也是用空间换取了时间,计数排序要求数组必须在一个确定的区间内。  过程:1. 首先找出数组的最大值最小值;2. 遍历数组,以数字作为键,该数字出现的次数作为值插入哈希表中;3. 在...
  • 一、HashMap1、基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值 null 键。(除了非同步允许使用 null 之外,...容量是哈希表中的数量,初始容量只是哈希表在创建时的容...
  • 对于排序算法, 通常简单的, 为大家所熟知的有, 选择排序, 冒泡排序, 快速排序, 当然还有哈希, 桶排序之类的, 本文仅比较最为常见的选择, 冒泡快排,文中通过示例代码介绍的非常详细,需要的朋友可以参考借鉴,下面...
  • 优质文章,及时送达一、HashMap1、基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 值 键。...容量是哈希表中的数量,初始容量只是哈希表在创建时的容量。加载因子...
  • 桶排序 由于通常排序的时间复杂度都是O(nlog(n)),当需要的表长不长,排序的元素集中在一个数据范围内,这种排序的时间更优 总结 字符哈希和正整数的哈希是有取值范围的 通用的方法 头插法的好处不需要额外遍历...

空空如也

空空如也

1 2 3 4 5 ... 8
收藏数 147
精华内容 58
关键字:

哈希排序和桶排序