百度面试常见算法（快排、堆排序、归并排序)

百度面试时常用的一些手写算法题，包括快速排序、堆排序、 归并排序、单链表转置和求链表倒数第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;
}