精华内容
下载资源
问答
  • 实验 内部排序

    千次阅读 2018-01-28 16:42:39
    一、实验目的 1.熟悉并掌握各种排序方法的设计思路。 2.掌握各种具体排序算法在计算机上的实现。 3.掌握各种排序方法的性能比较。 二、实验内容 ...(1)设哈希表长为20,用除留余法构造一

    ZZU的学弟学妹们不要抄作业哦~(`Д´)

    一、实验目的
    1.熟悉并掌握各种排序方法的设计思路。
    2.掌握各种具体排序算法在计算机上的实现。
    3.掌握各种排序方法的性能比较。

    二、实验内容
    1.直接插入排序、冒泡排序和简单选择排序算法实现,分析各种方法进行排序时对关键字的比较次数和移动次数。
    2.快速排序算法的实现。

    三、实验要求
    1.直接插入排序、冒泡排序和简单选择排序算法实现。(1)设哈希表长为20,用除留余数法构造一个哈希函数。
    (1)输入同样一组整型数据,作为待排序记录的关键字序列。
    (2)实现直接插入排序算法,输出排序后结果。
    (3)实现冒泡插入排序算法,输出排序后结果。
    (4)实现简单选择排序算法,输出排序后结果。

    2.快速排序算法的实现。
    (1)输入一组整型数据,作为待排序记录的关键字序列。
    (2)实现快速排序算法,输出排序后结果。

    四、详细程序清单

    //排序 
    #include<stdio.h>
    #include<stdlib.h>
    
    #define MAXSIZE 20
    #define INFINITY 0x7FFFFFFF //定义最大值∞
    
    typedef int KeyType;
    typedef int InfoType;
    typedef struct{
    	KeyType key;
    	InfoType otherinfo;
    }RedType;
    typedef struct{
    	RedType r[MAXSIZE+1];
    	int length;
    }SqList;
    
    void InsertSort(SqList &L)//直接插入排序 
    {
    	int i,j;
    	for(i=2;i<=L.length;i++)
    	  	if(L.r[i].key<L.r[i-1].key)
    	  	{
           		L.r[0]=L.r[i];
    			L.r[i]=L.r[i-1];
    			for(j=i-2;L.r[0].key<L.r[j].key;j--)
    				L.r[j+1]=L.r[j];
    			L.r[j+1]=L.r[0];	
    	  	}	
    }
    
    void BubbleSort(SqList &L)//冒泡插入排序
    {
    	int i,j,temp;
    	for(i=1;i<=L.length;i++)
    		for(j=1;j<=L.length-i;j++)
    			{
    				if(L.r[j].key>L.r[j].key)
    				{
    					temp=L.r[j].key;
    					L.r[j].key=L.r[j].key;
    					L.r[j].key=temp;
    				}
    			}	
    }
    
    int SelectMinKey(SqList L,int i)//选择最小值 
    {
    	int min=INFINITY;
    	for(i;i<=L.length;i++)
    		{
    			if(L.r[i].key<INFINITY)
    			min=L.r[i].key;
    		}
    	return min;	
    }
    
    void BSelectSort(SqList &L)//简单选择排序
    {
    	int i,j,temp;
    	for(i=1;i<=L.length;i++)
    	{
    		j=SelectMinKey(L,i);
    		if(i!=j)
    		{
    			temp=L.r[j].key;
    			L.r[j].key=L.r[j].key;
    			L.r[j].key=temp;			
    		}
    	}
    }
    
    int Partition(SqList &L,int low,int high)//快速排序
    {
    	int pivotkey;
    	L.r[0]=L.r[low];
    	pivotkey=L.r[low].key;
    	while(low<high)
    	{     
    		while(low<high&&L.r[high].key>=pivotkey) --high;
            L.r[low]=L.r[high];
            while(low<high&&L.r[low].key<=pivotkey)  ++low;
            L.r[high]=L.r[low];
        }
        L.r[low]=L.r[0];   
        return low;
    }
    
    void QSort(SqList &L,int low,int high)//快速排序 
    {
    	int pivotloc;
    	if(low<high) 
        {
    	    pivotloc=Partition(L,low,high);
            QSort(L,low,pivotloc-1); 
            QSort(L,pivotloc+1,high);
        }
    }
    
    void QuickSort(SqList &L)
    {
    	QSort(L,1,L.length); 
    }
    
    void Show(SqList L)//显示 
    {
    	for(int i=1;i<=L.length;i++)
    	printf("%d ",L.r[i].key);
    }
    
    int main()
    {
    	SqList L;
    	printf("输入长度:");
    	scanf("%d",&L.length);
    	printf("输入元素:");
    	for(int i=1;i<=L.length;i++)
    		scanf("%d",&L.r[i].key);
    	InsertSort(L);
    	printf("直接插入排序结果:");
    	Show(L);
    	BubbleSort(L);
    	printf("\n冒泡插入排序结果:");
    	Show(L);
    	BSelectSort(L);
    	printf("\n简单插入排序结果:");
    	Show(L);
    	QuickSort(L);
    	printf("\n快速排序结果:    ");
    	Show(L);
    } 
    
    

    五、程序运行结果
    这里写图片描述

    六、实验心得体会
    1.本次作业总共使用了四种排序方法,使我更加深刻地认识到了四中不同排序算法的差别和优劣。
    2.快速排序虽然难以理解,却是效率最高的排序算法,须牢牢掌握。
    3.这是最后一次写实验报告了,回首这一学期,感触良多。我本来就很喜欢编程,也打ACM,但是刚开始接触《数据结构》这本书的时候还是觉得晦涩难懂,不过随着逐渐的学习,越来越能感受到这本书的美妙。一学期的锻炼让我梳理清楚了数据的结构,对原来不常用的算法进行了查漏补缺,尤其是编程风格得到了很大提高。但我还有很多很多不足:书上有些代码的写法我依然不能很好的理解;我经常为了省事滥用全局变量;函数的嵌套有时复杂繁乱;代码风格不统一:大小写用法不统一,变量名、函数名不统一,有时候觉得这样写好,有时又觉得那样写好。
    4.学习编程的道路还很长很长,以后会更加努力!

    展开全文
  • 如何对n个数进行排序,要求时间复杂度O(n),空间复杂度O(1) 二,解答 关键:哈希表,空间复杂度O(1)中1的含义(只要是常量就可以) 看上去似乎任何已知的算法都无法做到,如果谁做到了,那么所有的排序方法...

    一,题目

            如何对n个数进行排序,要求时间复杂度O(n),空间复杂度O(1)

     

    二,解答

            关键:哈希表,空间复杂度O(1)中1的含义(只要是常量就可以)
            看上去似乎任何已知的算法都无法做到,如果谁做到了,那么所有的排序方法:QuickSort,ShellSort,HeapSort,BubbleSort等等等等,都可以扔掉了,还要这些算法干吗阿?不过实际上,在数字范围有限制的情况下,是有一个这样的算法的,只需要用一个数组记录每个数字出现次数就可以了。
            假定你的数字范围在0到65535范围之内,定义一个数组count[65536](这个空间是常量,和n无关,所以是O(1) ),初值全部为0。
            那么假设有下面这些数字:
                    100,200,300,119,0,6...
            那么对于每个这个数字,都做在count中记录一下:
                   100 => count[100]++
                   200 => count[200]++
                   300 => count[300]++
                   119 => count[119]++
                   0 => count[0]++
                    6 => count[6]++
             ...
           最后,遍历一边所有这些数字就可得到0~65535每个数字的个数(在count数组中),然后再顺序遍历count数组,count[n] = m,则输出m个n,(比如说有count[3] = 2, 那么说明有2个数字3),依次输出,最后可得结果。第一次遍历是O(n),第二次遍历是O(1),为常量,所以最后的时间复杂度为O(n),而空间复杂度为
    O(1)
    这个算法很简单,相信大家都会,只是这个题太过于变态了,一般会把面试者吓住。

    转载于:https://www.cnblogs.com/secbook/archive/2012/08/21/2654958.html

    展开全文
  • 数据结构与算法.xmind

    2020-06-19 17:04:23
    排序算法 内排序 八大基础排序 选择排序 简单选择排序 思想 每次选择最大的插入到末尾中 做法 外层for循环控制次数 内层for循环找出最大的值的角标 找出...
  • 又到了金九银面试旺季了,只有你准备充分了,那么你想要的机会才有机会...先把原数组进行一次排序,再对排序好的数组从头到尾进行遍历,很容易找到重复的数字,排序长度为n的数组需要O(nlogn)的时间。 哈希表法 ...

    又到了金九银十面试旺季了,只有你准备充分了,那么你想要的机会才有机会入你怀中。

    下面是数据结构与算法的正菜部分:

    一、找出数组中重复的数字

    在一个长度为n的数组里的所有数字都在0~n-1的范围内。找出数组中任意一个重复的数字。

    注意:如果题目改成找出数组中重复的数字的话,就需要和面试官沟通,我是找出所有重复的数字还是只需要找出一个就好了。

    排序法

    先把原数组进行一次排序,再对排序好的数组从头到尾进行遍历,很容易找到重复的数字,排序长度为n的数组需要O(nlogn)的时间。

    哈希表法

    可以借助哈希表解决该问题,从头到尾扫描该数组,判断该扫描到的数是否存在于该哈希表中,如果不存在则放于该哈希表中,如果存在则为重复元素。这个算法的时间复杂度是O(n),但却是以大小为O(n)的空间复杂度为代价。

    交换法

    如果没有重复元素的话,那么重排该数组后,数字i会出现在下标i的位置。如果有重复元素的话,下标i的位置可能不止一个数字,也可能没有数字。

    从头到尾扫描数组,扫描到下标为i的数字(用m表示)看是否等于i,如果是则接着扫描下一个数字,如果不是,再拿它和下标为m的那个数字比较,如果相等,则找到一个重复数字,如果不相等,就和它交换。重复这样的操作,直到找到重复的数字。

    代码实例:
    如果不存在重复元素的话,返回-1(具体返回的值可以和面试官沟通)

    public int getDuplicateNumber(int[] numbers){
            int len = numbers.length;
            if(numbers == null || len <= 0) return -1;
            for(int i=0;i<len;i++){
                if(numbers[i] < 0 || numbers[i] > len-1)
                    return -1;
            }
            
            for(int i=0;i<len;i++){
                
                while(numbers[i] != i){
                    if(numbers[i] == numbers[numbers[i]]){
                        return numbers[i];  //找到重复元素
                    }
                    else {
                        //交换numbers[i]和numbers[numbers[i]]的值
                        int temp = numbers[i];
                        numbers[i] = numbers[temp];
                        numbers[temp] = temp;
                    }
                }
                
            }
            return -1;
        }
    

    二、不能修改数组找出重复的数字

    在一个长度为n+1的数组里的所有数字都在1~n的范围内。找出数组中任意一个重复的数字。不能改变原数组并且不可借助大小超过O(n)的辅助空间。

    二分法

    因为长度是n+1,所以该数组至少有一个重复的数字。可以根据长度进行一半一半的分割。比如长度为8的数组,把它分两半:1-4,5-7。先在数组中找在1-4范围内的数的个数,如果超过4个说明重复的数字在1-4中。这样就缩小了范围,之后继续二分,在数组中分别找1-2,3-4这两组数字的个数,直到找到一个重复的数字。

    public int getDuplicateNumber2(int[] numbers){
            int len = numbers.length;
            if(numbers == null || len <= 0) return -1;
            int start = 1;
            int end = len-1;
            
            while(end >= start){
                int middle = ((end - start) >> 1)+start;
                int count = countRange(numbers,len,start,middle);
                if(end == start){
                    if(count > 1) return start;  //找到重复元素
                    else break;
                }
                if(count >(middle-start+1))
                    end = middle;
                else
                    start = middle+1;
            
            }
            return -1;
        }
        
    private int countRange(int[] numbers, int len, int start, int end) {
            if(numbers == null)
                return 0;
            int count = 0;
            for(int i=0;i<len;i++){
                if(numbers[i]>=start && numbers[i]<=end)
                    ++count;
            }
            return count;
        }
    

    倒数第K个节点

    在一个单链表中找到倒数第k个节点

    很容易想到先遍历一次链表节点个数n,第二次遍历只需要找第n-k+1个节点。

    当你说出这个想法的时候,面试官肯定会提示你他期待的答案是只允许遍历一次链表

    关键点:是否可以想到使用两个指针,移动过程中两个所在位置始终相差k-1的距离。当前一个指针移到尾部时,后一个指针正好指向倒数第k个结点。

        public ListNode findKthTail(ListNode pHead, int k){
            if(pHead == null || k<=0) return null;
            ListNode pAHead = pHead;      
            ListNode pBehind = null;
            
            //使前面的指针快与后面的节点k-1个节点位
            for(int i=0;i<k-1;i++){
                if(pAHead.next != null){  //容易忽视隐藏的边界条件,有可能k的值大于节点数
                    pAHead = pAHead.next;
                }else{
                    return null;
                }   
            }
            //让两个指针始终保持k-1个节点位,等前面的节点到尾节点时,后一个节点到达倒数第k个节点
            pBehind = pHead;
            while(pAHead.next != null){
                pAHead = pAHead.next;
                pBehind = pBehind.next;
            }
            return pBehind;
        }
    

    引申:如果让一次遍历找链表的中间结点可以使用类似的方法。只需要在指针移动时,前一个指针一次移动两个节点,后一个指针一次移动一个节点。前一个指针到达尾部时,后一个指针到达中间节点。

    反转链表

    反转一个单链表,返回它的头节点。

    很容易想到的是直接反转,后一个节点指向前一个节点。但是会有一个问题,到为尾节点的时候,会发生链表中断,这是因为尾节点的下一个结点为空。

    关键点:要将前一个节点保存下来,所以要使用三个指针

    public ListNode reverseListNode(ListNode pHead){
            if(pHead ==null) return null;
            ListNode pNewHead = null;
            ListNode pPre = null;
            ListNode pCur = pHead;
            
            while(pCur !=null){
                ListNode pNext = pCur.next;
                if(pNext == null){  //找到新的头节点
                    pNewHead = pCur;  
                }
                pCur.next = pPre;  //反转
                pPre = pCur;
                pCur = pNext;
                
            }
            return pNewHead;
        }
    

    是否可以想到添加一个指针来保存之前的节点是解题的关键。

    总结

    最后我在这里分享一下这段时间从朋友,大佬那里收集到的一些2019-2020BAT 面试真题解析,里面内容很多也很系统,包含了很多内容:Android 基础、Java 基础、Android 源码相关分析、常见的一些原理性问题等等,可以很好地帮助我们深刻理解Android相关知识点的原理以及面试相关知识(还有音视频相关的学习视频)

    这份资料把大厂面试中常被问到的技术点整理成了 PDF ,包知识脉络 + 诸多细节;还有 高级架构技术进阶脑图 帮助大家学习提升进阶,也节省大家在网上搜索资料的时间来学习,也可以分享给身边好友一起学习。

    这里也分享给广大面试同胞们,希望每位程序猿们都能面试成功~

    以上内容均放在了开源项目:我的github 中已收录,里面包含不同方向的自学Android路线、面试题集合/面经、及系列技术文章等,资源持续更新中...

    展开全文
  • 最简单粗暴的思路就是 使用排序算法对元素按照频率由高到低进行排序,然后再取前 kk 元素。 以下排序算法,任你挑选! 可以发现,使用常规的诸如 冒泡、选择、甚至快速排序都是不满足题目要求,它们的时间...

    栈与队列:TOP-K问题:前 K 个高频元素

    在这里插入图片描述
    解法一:粗暴排序法
    最简单粗暴的思路就是 使用排序算法对元素按照频率由高到低进行排序,然后再取前 kk 个元素。

    以下十种排序算法,任你挑选!
    在这里插入图片描述
    可以发现,使用常规的诸如 冒泡、选择、甚至快速排序都是不满足题目要求,它们的时间复杂度都是大于或者等于 O(n log⁡n)O(nlog⁡n),而题目要求算法的时间复杂度必须优于 O(n log n)O(nlogn)。

    解法二:

    • 借助 哈希表 来建立数字和其出现次数的映射,遍历一遍数组统计元素的频率
    • 维护一个元素数目为 k 的最小堆
    • 每次都将新的元素与堆顶元素(堆中频率最小的元素)进行比较
    • 如果新的元素的频率比堆顶端的元素大,则弹出堆顶端的元素,将新的元素添加进堆中
    • 最终,堆中的 k 个元素即为前 k 个高频元素

    对于优先队列的实现原理在这里,加强理解:点我跳转

    代码如下:

    class Solution {
    public:
            class Com
            {
            public:
                bool operator ()(const pair<int, int>& lhs, const pair<int, int>& rhs)
                {
                    return lhs.second > rhs.second;
                }
            };
    
           vector<int> topKFrequent(vector<int>& nums, int k) {    
           // map<nums[i],对应出现的次数>
           unordered_map<int, int> map;
           for(int i = 0; i < nums.size(); i++)
           {
               map[nums[i]]++;
           }
           // 定义一个小顶堆,大小为k
           priority_queue<pair<int, int>, vector<pair<int, int>>, Com> pri_que;
           for(auto it = map.begin(); it != map.end(); it++)
           {
               pri_que.push(*it);
               // 如果堆的大小大于了K,则队列弹出,保证堆的大小一直为k
               if(pri_que.size() > k)
               {
                   pri_que.pop();
               }
           }
           // 找出前K个高频元素,因为小顶堆先弹出的是最小的,所以倒叙来输出到数组
            vector<int> result(k);
            for(int i = k - 1; i >= 0; i--) 
            {
                result[i] = pri_que.top().first;
                pri_que.pop();
            }
            return result; 
        }
    };
    

    题解参考:

    作者:MisterBooo
    链接:https://leetcode-cn.com/problems/top-k-frequent-elements/solution/leetcode-di-347-hao-wen-ti-qian-k-ge-gao-pin-yuan-/
    来源:力扣(LeetCode)
    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    展开全文
  • 2.4 怎样表示一个算法 24 2.4.1 用自然语言表示算法 24 2.4.2 用流程图表示算法 24 2.4.3 三种基本结构和改进的流程图 28 2.4.4 用N-S 流程图表示算法 29 2.4.5 用伪代码表示算法 30 2.4.6 用计算机语言表示算法 31 ...
  • 以一计算机教师教学为场景,讲解数据结构和相关算法的知识。通篇以一种趣味方式来叙述,大量引用了各种各样的生活知识来类比,并充分运用图形语言来体现抽象内容,对数据结构所涉及到的一些经典算法做到逐行分析、...
  • 大话数据结构

    2019-01-10 16:35:22
    作品目录编辑 第1章数据结构绪论 1 1.1开场白 2 如果你交给某人一程序,你将折磨他一整天;如果你教某人如何编写程序,你将折磨他一辈子。...7.8.2拓扑排序算法 272 7.9关键路径 277 假如造一轮子要0.5天、造...
  • 大话数据结构 程杰

    2018-09-01 10:06:43
    目录: 第1章数据结构绪论 1 1.1开场白 2 如果你交给某人一程序,你将折磨他一整天;如果你教某人如何编写程序,你将折磨他一辈子。...7.8.2拓扑排序算法 272 7.9关键路径 277 假如造一轮子要0.5天、造一...
  • 5.7.1 KMP模式匹配算法原理 135 5.7.2 next数组值推导 139 5.7.3 KMP模式匹配算法实现 141 5.7.4 KMP模式匹配算法改进 142 5.7.5 nextval数组值推导 144 5.8 总结回顾 146 5.9 结尾语 146 《璇玑图》共八百四字,...
  • 以一计算机教师教学为场景,讲解数据结构和相关算法的知识。通篇以一种趣味方式来叙述,大量引用了各种各样的生活知识来类比,并充分运用图形语言来体现抽象内容,对数据结构所涉及到的一些经典算法做到逐行分析、...
  • 大话数据结构-程杰

    2014-07-13 23:45:52
    很多年前我们的科学家觉得像这种有多0和1重复字符的字符串,却需要挨个遍历的算法,是非常糟糕的事情。 5.7.1 KMP模式匹配算法原理 135 5.7.2 next数组值推导 139 5.7.3 KMP模式匹配算法实现 141 5.7.4 KMP...
  • 3.2 禁止进行指令重排序。(保证有序性) 划重点:volatile 关键字能保证可见性和有序性,但是不能保证操作的原子性。 可见性只能保证每次读取的是最新的值,但是volatile没办法保证对变量的操作的原子性。 本工程...
  • 数据结构实验

    2012-04-13 09:55:47
    1.编写程序任意输入二叉树的结点个数和结点值,构造一棵二叉树,采用三种递归遍历算法(前序、中序、后序)对这棵二叉树进行遍历并计算出二叉树的高度。 2 .编写程序生成下面所示的二叉树,并采用中序遍历的非递归...
  • 实例110 通过定义方法求一个数的平方 实例111 使用重载方法实现不同类型数据的计算 5.2 结构与类 实例112 通过结构计算矩形的面积 实例113 通过类继承计算梯形面积 实例114 封装类实现一个简单的计算器 实例...
  • 实例110 通过定义方法求一个数的平方 实例111 使用重载方法实现不同类型数据的计算 5.2 结构与类 实例112 通过结构计算矩形的面积 实例113 通过类继承计算梯形面积 实例114 封装类实现一个简单的计算器 实例...
  • 实例110 通过定义方法求一个数的平方 实例111 使用重载方法实现不同类型数据的计算 5.2 结构与类 实例112 通过结构计算矩形的面积 实例113 通过类继承计算梯形面积 实例114 封装类实现一个简单的计算器 实例...
  • 实例110 通过定义方法求一个数的平方 133 实例111 使用重载方法实现不同类型数据的计算 135 5.2 结构与类 136 实例112 通过结构计算矩形的面积 136 实例113 通过类继承计算梯形面积 137 实例114 封装类实现一个简单...
  •  实例110 通过定义方法求一个数的平方 133  实例111 使用重载方法实现不同类型数据的计算 135 5.2 结构与类 136  实例112 通过结构计算矩形的面积 136  实例113 通过类继承计算梯形面积 137  实例114 封装...
  • 4.2 排序算法 191 实例128 直接插入排序 192 实例129 希尔排序 193 实例130 起泡排序 194 实例131 快速排序 195 实例132 选择排序 197 实例133 归并排序 198 4.3 查找算法 199 实例134 顺序查找 ...
  • c语言经典案例

    2014-10-30 08:06:57
    实例010 3个数由小到大排序 11 实例011 猴子吃桃 13 实例012 阳阳买苹果 14 第3章 算法入门 15 实例013 任意次方后的最后三位 16 实例014 计算某日是该年的第几天 16 实例015 婚礼上的谎言 18 实例016 百元买百鸡 19...
  • 数据结构(C++)有关练习题

    热门讨论 2008-01-02 11:27:18
    综合(课程设计) 内容及步骤: 1、假定一维数组a[n]中的每个元素值均在[0,200]区间内,用C++编写一个算法,分别统计出落在[0,20],[21,50],[51,80],[81,130],[131,200]等各区间内的元素个数。...
  • 实例146 统计字符个数 实例147 实现字节数组和字符串的相互转换 实例148 用VB分离出文本框的单词 第6章 过程与函数 6.1 自定义过程 实例149 过程值传递参数 实例150 过程引用传递参数 实例151 不借助第3个...
  • 《数据结构 1800题》

    热门讨论 2012-12-27 16:52:03
    8. 一个算法具有 5特性: (1)有穷性 、 (2)确定性 、 (3)可行性 ,有零或多输入、有一或多输出。 《数据结构 1800题》 9.已知如下程序段 FOR i:= n DOWNTO 1 DO {语句 1} BEGIN x:=x+1;...
  • C++网络爬虫项目

    2018-07-04 00:59:17
    而网页排序最重要的两参考因素,一是“内容相似 性”,即哪些网页是和用户的搜索意图密切相关的;一是网页重要性,即哪 些网页是质量较好或相对重要的,而这往往可以从“链接分析”的结果中获 得。综合以上两...
  • java开源包1

    千次下载 热门讨论 2013-06-28 09:14:34
    JCaptcha4Struts2 是一 Struts2的插件,用来增加验证码的支持,使用时只需要用一 JSP 标签 (<jcaptcha:image label="Type the text "/> ) 即可,直接在 struts.xml 中进行配置,使用强大的 JCaptcha来生成验证码...

空空如也

空空如也

1 2 3
收藏数 43
精华内容 17
关键字:

哈希排序算法进行十个数排序