堆排序的實現(聯發科子公司創發科技筆試)及判斷單向鏈表的環
來源:程序員人生 發布時間:2014-10-08 18:52:11 閱讀次數:2820次
先上代碼:
#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;
}
另外還有大端小端、指針、語法方面的小的選擇題。
生活不易,碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈