C++ 经典算法 口试绝杀

C++ 经典算法 面试绝杀

1.链表逆序

2.链表合并

3.一棵树是否某条路径结点之和等于给定值。并描述算法复杂度

4.你熟悉的排序算法并描述算法复杂度。

         快速排序

         归并排序

         堆排序

         选择排序

         插入排序

        冒泡排序

        折半插入排序

以下代码都能成功通过。

1.链表逆序

#include <iostream>using namespace std;void BInsertSort(int a[],int size){    for(int i=1;i<size;i++)    {        int temp=a[i];               //暂存a[i]        int low=0;        int high=i-1;        while(low<=high)        {            int middle=(low+high)/2;            if(temp<=a[middle])                high=middle-1;            else                low=middle+1;        }        for(int j=i-1;j>=high+1;--j)   //记录后移            a[j+1]=a[j];        a[high+1]=temp;                //插入，注意没有补齐的地方要注意，不然是野指针指向莫名的值。    }}int main(){    int a[]={12,36,24,53,53,30,53,91};    for(int i=0;i<8;i++)        cout<<a[i]<<" ";    cout<<endl;    BInsertSort(a,8);    for(int i=0;i<8;i++)         cout<<a[i]<<" ";    cout<<endl;    return 0;}