百度面试时常用的一些手写算法题,包括快速排序、堆排序、 归并排序、单链表转置和求链表倒数第K个节点
1 快速排序 O(nlogn)
void quickSort(int s[], int l, int r)
{
if(l < r)
{
int i = l, j = r, x = s[l];
while(i<j)
{
while(i<j&&s[j]>x)
j--;
if(i<j)
s[i++] = s[j];
while(i<j&&s[i]<x)
i++;
if(i<j)
s[j--] = s[i];
}
s[i] = x;
quickSort(s, l, i-1);
quickSort(s, i+1, r);
}
}
2 堆排序O(nlog(n))
//已知H[start~end]中除了start之外均满足堆的定义
//本函数进行调整,使H[start~end]成为一个大顶堆
void HeapAdjust(int H[], int start, int end)
{
int temp = H[start];
for(int i = 2*start + 1; i<=end; i*=2)
{
//因为假设根结点的序号为0而不是1,所以i结点左孩子和右孩子分别为2i+1和2i+2
if(i<end && H[i]<H[i+1])//左右孩子的比较
{
++i;//i为较大的记录的下标
}
if(temp > H[i])//左右孩子中获胜者与父亲的比较
{
break;
}
//将孩子结点上位,则以孩子结点的位置进行下一轮的筛选
H[start]= H[i];
start = i;
}
H[start]= temp; //插入最开始不和谐的元素
}
void HeapSort(int A[], int n)
{
//先建立大顶堆
for(int i=(n-1)/2; i>=0; --i)
{
HeapAdjust(A,i,n-1);
}
//进行排序
for(int i=n-1; i>0; --i)
{
//最后一个元素和第一元素进行交换
int temp=A[i];
A[i] = A[0];
A[0] = temp;
//然后将剩下的无序元素继续调整为大顶堆
HeapAdjust(A,0,i-1);
}
}
3 归并排序 O(nlogn)
//将有序数组a[]和b[]合并到c[]中
void MemeryArray(int a[], int n, int b[], int m, int c[])
{
int i, j, k;
i = j = k = 0;
while (i < n && j < m)
{
if (a[i] < b[j])
c[k++] = a[i++];
else
c[k++] = b[j++];
}
while (i < n)
c[k++] = a[i++];
while (j < m)
c[k++] = b[j++];
}
//将有二个有序数列a[first...mid]和a[mid...last]合并。
void mergearray(int a[], int first, int mid, int last, int temp[])
{
int i = first, j = mid + 1;
int m = mid, n = last;
int k = 0;
while (i <= m && j <= n)
{
if (a[i] <= a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
while (i <= m)
temp[k++] = a[i++];
while (j <= n)
temp[k++] = a[j++];
for (i = 0; i < k; i++)
a[first + i] = temp[i];
}
void mergesort(int a[], int first, int last, int temp[])
{
if (first < last)
{
int mid = (first + last) / 2;
mergesort(a, first, mid, temp); //左边有序
mergesort(a, mid + 1, last, temp); //右边有序
mergearray(a, first, mid, last, temp); //再将二个有序数列合并
}
}
bool MergeSort(int a[], int n)
{
int *p = new int[n];
if (p == NULL)
return false;
mergesort(a, 0, n - 1, p);
delete[] p;
return true;
}
4 单链表转置
Link_Dode * ReverseLink(Link_Node *head)
{
if(head==null || head->next==)
return head;
Link_Node *next;
Link_Node *prev = NULL;
while(head != NULL)
{
next = head->next;
head->next = prev;
prev = head;
head = next;
}
return prev;
}
5 求链表倒数第K个节点
Link_Node* theK(Link_Node* head, int k)
{
if(k<0)
return NULL;
Link_Node* slow, *fast;
slow = fast = head;
int i = k;
for(i; i>0&&fast!=NULL; i--)
{
fast = fast->next;
}
if(i>0) return NULL;
while(fast != NULL)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}
继续阅读
- 我的微信小程序
- 这是我的微信小程序扫一扫
-
- 我的微信公众号
- 我的微信公众号扫一扫
-
评论