首页 > 代码库 > 堆排序的实现(联发科子公司创发科技笔试)及判断单向链表的环
堆排序的实现(联发科子公司创发科技笔试)及判断单向链表的环
先上代码:
#include <iostream> #include <algorithm> using namespace std; void HeapAdjust(int data[],int i,int length) { int nChild; int nTemp; for(nTemp=data[i]; 2*i+1<length ;i=nChild) { nChild=2*i+1; if(nChild<length-1&&data[nChild+1]>data[nChild])//比较哪个孩子比自己大,如果是右孩子的话,就要将nChild++; { nChild++; } if(nTemp<data[nChild])//如果比自己的最大的孩子小,就交换 { data[i]=data[nChild]; data[nChild]=nTemp; } else//如果比最大的孩子还大,就不交换 break; } } void HeapSort(int a[],int n) { for(int i=n/2-1;i>=0;i--)/*把a[]构建成一个大顶堆*/ { HeapAdjust(a,i,n); } for(int j=n-1;j>=1;j--) { swap<int>(a[j],a[0]);//STL swap HeapAdjust(a,0,j); } } int main() { int a[10] = {9,3,7,5,3,4,2,0,1,6}; HeapSort(a,10); for(int i=0;i<10;i++) cout<<a[i]<<" "; cout<<endl; return 0; }
上面主要是功能函数,主函数大家搞定啦!我调试通过了已经!
堆排序的时间复杂度为O(nlogn),最坏的情况也是这个时间复杂度,空间复杂度是O(1)。但是堆排序是不稳定的!
在面试过程中,很多时候都会用到堆排序,比如下面的题目都是堆排序的典型题目:
1.给你100w个数据求最大的10个元素。这个时候我们可以使用小顶堆!这个是为什么呢!
2.给你100w个数据求最小的10个元素。这个时候我们可以使用大顶堆!这个是为什么呢!
相信会有很多同学会问出上面的两个疑问,答案其实很简单,在求最大的元素的时候,我们建立一个有10个元素的小顶堆,那么堆顶元素肯定是最小的,然后拿剩余的元素和堆顶进行比较,如果比堆顶大,就替换这个元素,然后调整堆,调整完之后堆顶依然是10个元素中最小的,依次比较剩余的元素。
堆排序与直接插入排序的区别
直接选择排序中,为了从R[1..n]中选出关键字最小的记录,必须进行n-1次比较,然后在R[2..n]中选出关键字最小的记录,又需要做n-2次比 较。事实上,后面的n-2次比较中,有许多比较可能在前面的n-1次比较中已经做过,但由于前一趟排序时未保留这些比较结果,所以后一趟排序时又重复执行 了这些比较操作。 堆排序可通过树形结构保存部分比较结果,可减少比较次数。
如果一个单向链表,其中有环,怎么找出这个链表循环部分的第一个节点?
//如果链表中没有环,返回false bool loop(node* head) { bool flag = true; if (head == NULL) { flag = false; } node* one = head; node* two = head->next; if (two == NULL) { flag = false; } while (one != two) { if (one != NULL) { one = one->next; } if (two != NULL) { two = two->next; } if (two == NULL) { break; } two = two->next; if (one == NULL || two == NULL) { break; } } if (one == NULL || two == NULL) { flag = false; } return flag; } /* 思想为:假设该节点在x位置处,假设步长为1的指针和步长为2的指针相遇在x+z处,循环的长度为y,那么2(x+z)-(x+z)=k*y, 那么当一个指针再从开始出后移时,另一个指针从相遇点开始后移时,这两个指针就会在循环开始处相遇。 */ node* findLoopPlace(node* head, unsigned int* place = NULL) { //查找循环的位置,place存储位置 if (!loop(head)) { return NULL; } node* one = head; node* two = head->next; unsigned int count = 1; while (one != two) { one = one->next; two = two->next->next; } one = head; while (one != two) { if (count != 1) { one = one->next; } two = two->next; count++; } *place = count; return one; }另外还有大端小端、指针、语法方面的小的选择题。
堆排序的实现(联发科子公司创发科技笔试)及判断单向链表的环
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。