堆排序的实现（联发科子公司创发科技笔试）及判断单向链表的环
来源：程序员人生 发布时间：2014-10-08 18:52:11 阅读次数：2660次
先上代码：
#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;
}
另外还有大端小端、指针、语法方面的小的选择题。
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
