数据结构与算法总结

1. 链表

链表是最基本的数据结构，面试官也常常用链表来考察面试者的基本能力，而且链表相关的操作相对而言比较简单，也适合考察写代码的能力。链表的操作也离不开指针，指针又很容易导致出错。综合多方面的原因，链表题目在面试中占据着很重要的地位。

链表问题中的一个重要的方法叫双指针法。定义两个指针，一个叫慢指针，另一个叫快指针。通常慢指针每次向前移动一个节点，而快指针每次向前移动若干个节点。这个方法通常用于寻找链表中特定的位置。比如找到链表的中点，可以让快指针每次移动两个节点。这样当快指针到达链表末尾时，慢指针刚好在链表中间的位置。

链表结点声明如下：

struct ListNode
{
    int value;
    ListNode * next;
    ListNode(int x) : value(x), next(NULL) {}
};

1.1 求单链表中结点的个数

这是最最基本的了，应该能够迅速写出正确的代码，注意检查链表是否为空。时间复杂度为O（n）。

int GetListLenght(ListNode* head)
{
    if(head == NULL)    return 0;
    ListNode* current = head;
    int len = 0;
    while(current != NULL)
    {
        len++;
        current = current->next;
    }
    return len;
}

1.2 将单链表反转

从头到尾遍历原链表，每遍历一个结点，将其摘下放在新链表的最前端。注意链表为空和只有一个结点的情况。时间复杂度为O（n）。

ListNode* ReverseList(ListNode* head)
{
    if(head == NULL || head->next == NULL)    return head;
    ListNode* reverseHead = NULL;
    ListNode* current = head;
    while(current != NULL)
    {
        ListNode* temp = current;
        current = current->next;
        temp->next = reverseHead;
        reverseHead = temp;
    }
    return reverseHead;
}

1.3 查找单链表中的倒数第K个结点（k>0）

使用两个指针，先让前面的指针走到正向第k个结点，这样前后两个指针的距离差是k-1，之后前后两个指针一起向前走，前面的指针走到最后一个结点时，后面指针所指结点就是倒数第k个结点。

ListNode * RGetKthNode(ListNode * head, unsigned int k)
{
    if(head == NULL)    return NULL;
    ListNode* aHead = head, behind = head;
    while(k>1)
    {
        if(aHead == NULL)    return NULL;
        aHead = aHead->next;
        k--;
    }
    while(aHead->next != NULL)
    {
        behind = behind->next;
        aHead = aHead->next;
    }
    return behind;
}

1.4 判断一个单链表中是否有环

如果一个链表中有环，也就是说用一个指针去遍历，是永远走不到头的。因此，我们可以用两个指针去遍历，一个指针一次走两步，一个指针一次走一步，如果有环，两个指针肯定会在环中相遇。时间复杂度为O（n）。

bool HasCycle(ListNode* head)
{
    ListNode* fast = head,* slow = head;
    while(fast != NULL && fast->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)    return true;
    }
    return false;
}

1.5 判断一个单链表中是否有环，如果存在，求进入环中的第一个节点

这题不光要求出是否有环，而且还需要得到这个环开始的节点。譬如下面这个，起点就是n2。

        n6-----------n5
        |              |
n1------n2----n3----n4|

我们仍然可以使用两个指针fast和slow，fast走两步，slow走一步，判断是否有环，当有环重合之后，譬如上面在n5重合了，那么如何得到n2呢？
首先我们知道，fast每次比slow多走一步，所以重合的时候，fast移动的距离是slot的两倍，我们假设n1到n2距离为a，n2到n5距离为b，n5到n2距离为c，fast走动距离为a+ b+c+b，而slow为 a+b，有方程a+b+c+b=2x(a+b)，可以知道a=c，所以我们只需要在重合之后，一个指针从n1，而另一个指针从n5，都每次走一步，那么就可以在n2重合了。

ListNode* DetectCycle(ListNode* head)
{
    ListNode *slow = head, *fast = head;
    while(fast != NULL && fast->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
        {
            ListNode* slow2 = head;
            while(slow2 != slow)
            {
                slow2 = slow2->next;
                slow = slow->next;
            }
            return slow2;
        }
    }
    return NULL;
}

1.6 合并两个排好序的链表

利用附加头结点简化操作

ListNode* MergeTowList(ListNode* head1, ListNode* head2)
{
    ListNode* dummy(0);
    ListNode* temp = &dummy;
    while(head1 != NULL && head2 != NULL)
    {
        int val1 = head1->value;
        int val2 = head2->value;
        if(val1 < val2)
        {
            temp->next = head1;
            temp = head1;
            head1 = head1->next;
        }
        else
        {
            temp->next = head2;
            temp = head2;
            head2 = head2->next;
        }
    }
    if(head1 != NULL)    temp->next = head1;
    else if(head2 != NULL)    temp->next = head2; 
    return dummy.next;
}

1.7 去除有序链表中的重复元素

ListNode *DeleteDuplicates(ListNode *head) {
    if (head == nullptr) return nullptr;
    for (ListNode *prev = head, *cur = head->next; cur; cur = prev->next) {
        if (prev->val == cur->val) {
            prev->next = cur->next;
            delete cur;
        } 
        else {
            prev = cur;
        }
    }
    return head;
}

1.8 判断两个单链表是否相交

如果两个链表相交于某一节点，那么在这个相交节点之后的所有节点都是两个链表所共有的。也就是说，如果两个链表相交，那么最后一个节点肯定是共有的。先遍历第一个链表，记住最后一个节点，然后遍历第二个链表，到最后一个节点时和第一个链表的最后一个节点做比较，如果相同，则相交，否则不相交。时间复杂度为O(len1+len2)，因为只需要一个额外指针保存最后一个节点地址，空间复杂度为O(1)。参考代码如下：

bool IsIntersected(ListNode* head1, ListNode* head2)
{
    if(head1 == NULL || head2 == NULL)    return false;
    ListNode* tail1 = head1;
    while(tail1->next != NULL)    tail1 = tail1->next;
    ListNode* tail2 = head2;
    while(tail2->next != NULL)    tail2 = tail2->next;
    return tail1 == tail2;
}

1.9 求两个单链表相交的第一个节点

对第一个链表遍历，计算长度len1，同时保存最后一个节点的地址。对第二个链表遍历，计算长度len2，同时检查最后一个节点是否和第一个链表的最后一个节点相同，若不相同，不相交，结束。

两个链表均从头节点开始，假设len1大于len2，那么将第一个链表先遍历len1-len2个节点，此时两个链表当前节点到第一个相交节点的距离就相等了，然后一起向后遍历，知道两个节点的地址相同。时间复杂度，O(len1+len2)。参考代码如下：

ListNode* FindFirstCommonNode( ListNode *head1, ListNode *head2) {
    if(head1 == NULL && head2 == NULL)    return NULL;
    int len1=0,len2=0;
    ListNode* list1 = head1;
    ListNode* list2 = head2;
    while(list1 != NULL){
        list1 = list1->next;
        len1++;
    }
    while(list2 != NULL){
        list2 = list2->next;
        len2++;
    }
    
    int interval;
    ListNode* longList;
    ListNode* shortList;
    if(len1>=len2){
        interval = len1-len2;
        longList = head1;
        shortList = head2;
    }
    else{
        interval = len2-len1;
        longList = head2;
        shortList = head1;
    }
    
    for(int i=0;i<interval;i++)    longList = longList->next;
    
    while(longList != NULL && shortList != NULL && longList != shortList){
        longList = longList->next;
        shortList = shortList->next;
    }
    
    return longList;
}

2. 二叉树

树是一种比较重要的数据结构，尤其是二叉树。二叉树是一种特殊的树，在二叉树中每个节点最多有两个子节点，一般称为左子节点和右子节点（或左孩子和右孩子），并且二叉树的子树有左右之分，其次序不能任意颠倒。二叉树是递归定义的，因此，与二叉树有关的题目基本都可以用递归思想解决，当然有些题目非递归解法也应该掌握，如非递归遍历节点等等。

二叉树节点定义如下：

struct BinaryTreeNode
{
    int value;
    BinaryTreeNode* left;
    BinaryTreeNode* right;
    BinaryTreeNode(int x) : value(x), left(NULL), right(NULL) {}
};

2.1 求二叉树中的结点个数

递归解法：

• 如果二叉树为空，节点个数为0
• 如果二叉树不为空，二叉树节点个数 = 左子树节点个数 + 右子树节点个数 + 1

int GetNodeNumber(BinaryTreeNode* root)
{
    if(root == NULL)    return 0;
    return GetNodeNumber(root->left) + GetNodeNumber(root->right) + 1;
}

2.2 求二叉树的深度

递归解法：

• 如果二叉树为空，二叉树的深度为0
• 如果二叉树不为空，二叉树的深度 = max(左子树深度， 右子树深度) + 1

int GetDeepth(BinaryTreeNode* root)
{
    if(root == NULL)    return 0;
    int depthLeft = GetDeepth(root->left);
    int depthRight = GetDeepth(root->right);
    return depthLeft > depthRight ? (depthLeft + 1) : (depthRight + 1);
}

2.3 前序遍历，中序遍历，后序遍历

前序遍历递归解法：如果二叉树为空，空操作；如果二叉树不为空，访问根节点，前序遍历左子树，前序遍历右子树。中序遍历递归解法：如果二叉树为空，空操作；如果二叉树不为空，中序遍历左子树，访问根节点，中序遍历右子树。后序遍历递归解法：如果二叉树为空，空操作；如果二叉树不为空，后序遍历左子树，后序遍历右子树，访问根节点。

void preOrderTraverse(BinaryTreeNode* root)
{
    if(root == NULL)    return;
    visit(root);
    PreOrderTraverse(root->left); // 前序遍历左子树  
    PreOrderTraverse(root->right); // 前序遍历右子树
}

void InOrderTraverse(BinaryTreeNode* root)
{
    if(root == NULL)    return;
    InOrderTraverse(root->left); // 中序遍历左子树 
    visit(root); // 访问根节点 
    InOrderTraverse(root->right); // 中序遍历右子树  
}

void PostOrderTraverse(BinaryTreeNode * root)  
{  
    if(root == NULL)    return;  
    PostOrderTraverse(root->left); // 后序遍历左子树  
    PostOrderTraverse(root->right); // 后序遍历右子树  
    Visit(root); // 访问根节点  
} 

2.4 层次遍历

相当于广度优先搜索，使用队列实现。队列初始化，将根节点压入队列。当队列不为空，进行如下操作：弹出一个节点，访问，若左子节点或右子节点不为空，将其压入队列。

void LevelTraverse(BinaryTreeNode* root)
{
    if(root == NULL) return ;
    queue<BinaryTreeNode*> que;
    que.push(root);
    while(!que.empty())
    {
        BinaryTreeNode* tempNode = que.front();
        que.pop();
        visit(tempNode);
        if(root->left != NULL)    que.push(tempNode->left);
        if(root->right != NULL)    que.push(tempNode->right);
    }
    return ;
}

2.5 求二叉树第K层的节点个数

递归解法：

• 如果二叉树为空或者k<1返回0
• 如果二叉树不为空并且k==1，返回1
• 如果二叉树不为空且k>1，返回左子树中k-1层的节点个数与右子树k-1层节点个数之和

int GetNodeNumKthLevel(BinaryTreeNode* root, int k)
{
    if(root == NULL || k<1)    return 0;
    if(k == 1)    return 1;
    int numLeft = GetNodeNumKthLevel(root->left, k-1);
    int numRight = GetNodeNumKthLevel(root->right,k-1);
    return numLeft + numRight;
}

2.6 求二叉树中叶子节点的个数

递归解法：

• 如果二叉树为空，返回0；
• 如果二叉树不为空且左右子树为空，返回1；
• 如果二叉树不为空，且左右子树不同时为空，返回左子树中叶子节点个数加上右子树中叶子节点个数。

int GetLeafNodeNum(BinaryTreeNode * root)  
{  
    if(root == NULL)  return 0;  
    if(root->left == NULL && root->right == NULL)  return 1;  
    int numLeft = GetLeafNodeNum(root->left); // 左子树中叶节点的个数  
    int numRight = GetLeafNodeNum(root->right); // 右子树中叶节点的个数  
    return (numLeft + numRight);  
}

2.7 判断两棵二叉树是否结构相同

不考虑数据内容。结构相同意味着对应的左子树和对应的右子树都结构相同。递归解法如下：

• 如果两棵二叉树都为空，返回真
• 如果两棵二叉树一棵为空，另一棵不为空，返回假
• 如果两棵二叉树都不为空，如果对应的左子树和右子树都同构返回真，其他返回假

bool StructureCmp(BinaryTreeNode * root1, BinaryTreeNode * root2)  
{  
    if(root1 == NULL && root2 == NULL) // 都为空，返回真  
        return true;  
    else if(root1 == NULL || root2 == NULL) // 只有一个为空，返回假  
        return false;  
    bool resultLeft = StructureCmp(root1->left, root2->left); // 比较对应左子树   
    bool resultRight = StructureCmp(root1->right, root2->right); // 比较对应右子树  
    return (resultLeft && resultRight);  
} 

2.8 判断二叉树是不是平衡二叉树

平衡二叉树：
递归解法：

• 如果二叉树为空，返回真
• 如果二叉树不为空，如果左子树和右子树都是AVL树并且左子树和右子树高度相差不大于1，返回真，其他返回假

bool IsAVL(BinaryTreeNode * root, int & height)  
{  
    if(root == NULL) // 空树，返回真  
    {  
        height = 0;  
        return true;  
    }  
    int heightLeft;  
    bool resultLeft = IsAVL(root->left, heightLeft);  
    int heightRight;  
    bool resultRight = IsAVL(root->right, heightRight);  
    // 左子树和右子树都是AVL，并且高度相差不大于1，返回真  
    if(resultLeft && resultRight && abs(heightLeft - heightRight) <= 1) 
    {  
        height = max(heightLeft, heightRight) + 1;  
        return true;  
    }  
    else  
    {  
        height = max(heightLeft, heightRight) + 1;  
        return false;  
    }  
}

2.9 求二叉树的镜像

递归解法：

• 如果二叉树为空，返回空
• 如果二叉树不为空，求左子树和右子树的镜像，然后交换左子树和右子树

BinaryTreeNode* Mirror(BinaryTreeNode* root)
{
    if(root == NULL)    return NULL;
    BinaryTreeNode* mLeft = Mirror(root->left); // 求左子树镜像
    BinaryTreeNode* mRight = Mirror(root->right); // 求右子树镜像
    // 交换左子树和右子树
    root->left = mRight;
    root->right = mLeft;
    return root;
}

2.10 迭代的遍历算法

//利用栈进行递归前序遍历
void PreorderTraversal(BinaryTreeNode* root)
{
    stack<const BinaryTreeNode*> s;
    if(root != NULL)    s.push(root);
    while(!s.empty())
    {
        const BinaryTreeNode* temp = s.top();
        s.pop();
        visit(temp);
        if(temp->right != NULL) s.push(temp->right);
        if(temp->left != NULL) s.push(temp->left);
    }
}

void InOrderTraversal(BinaryTreeNode* root)
{
    stack<const BinaryTreeNode*> s;
    const BinaryTreeNode* temp = root;
    while(!s.empty() || temp !=NULL)
    {
        if(temp != NULL){
            s.push(temp);
            temp = temp->left;
        }
        else{
            temp = s.top();
            s.pop();
            visit(temp);
            temp = temp->right;
        }
    }
}

void PostOrderTraversal(BinaryTreeNode* root)
{
    stack<const BinaryTreeNode*> s;
    const BinaryTreeNode* temp = root, * pre = NULL;
    do{
        while(temp != NULL){
            s.push(temp);
            temp = temp->left;
        }
        pre = NULL;
        while(!s.empty()){
            temp = s.top();
            s.pop();
            //如果该结点的右子节点不存在或已被访问，就访问它
            if(temp->right == pre){
                visit(temp);
                pre = temp;
            }
            else{
                s.push(temp);
                temp = temp->right;
                break;
            }
        }
    }while(!s.empty());
}

2.11 判断是否存在一条从root到其中一个叶子节点的路径的和等于给定的值

直接使用深度优先遍历求解

bool DFS(int target, int sum, BinaryTreeNode* root)
{
    if(root == NULL)    return false;
    sum += root->value;
    if(root->left == NULL && root->right == NULL)
    {
        if(sum == target)    return true;
        else return false;
    }
    bool leftPart = DFS(target,sum,root->left);
    bool rightPart = DFS(target,sum,root->right);
    return leftPart || rightPart;
}

bool hasPathSum(BinaryTreeNode* root,int sum)
{
    if(root == NULL)    return false;
    return DFS(sum,0,root);
}

3. 字符串操作与算法

3.1 字符串匹配算法

3.1.1 朴素的匹配算法

就是所谓的暴力匹配。假设文本T长度为m，模式串P长度为n，算法从文本第1位从左向右开始与模式串P进行匹配，无论是否匹配成功，模式串都后移1位开始继续进行重新匹配，总共进行m-n+1次匹配。算法极其简单，因此效率极其有限，时间复杂度为O(m*n)，故不常被用。

void NaiveMatch(const char* T,const char* P)
{
    int m = strlen(T);
    int n = strlen(P);
    for(int i=0;i<m-n;i++){
        int j;
        for(j=0;j<n;j++)
            if(T[i+j] != P[j])    break;
        if(j==n)    cout<<i<<" ";
    }
    cout<<endl;
}

3.1.2 Horspool算法

int* HorspoolTable(const char *P)  
{  
    int n = strlen(P);  
    int *ht = new int[256];  
    for (int i=0; i<256; i++)  
        ht[i] = n;  
    for (int i=0; i<n-1; i++)  
        ht[(int)P[i]] = n - i - 1;  
    return ht;  
}  
  
void Horspool(const char *T, const char *P)  
{  
    int m = strlen(T);  
    int n = strlen(P);  
    int *ht = HorspoolTable(P);  
  
    int i=0, k=n-1;  
    while (i<=m-n)  
    {  
        for (k=n-1; k>=0 && T[i+k]==P[k]; k--) ;  
  
        if (k==-1)  
            cout<<i<<" ";  
        i = i + ht[(int)T[i+n-1]];  
    }  
    cout<<endl;  
    delete []ht;  
}  

3.2 将字符串转换为整数

需考虑各种条件，如空字符，正负号，非法输入等问题，还要考虑超出int范围的问题。下面的代码中，若是非法输入，则输出0，也没考虑超出范围的问题。若要考虑非法输入，可设置一个全局变量。

int StrToInt(string s)
{
    int result = 0;
    //判断是否为空字符串
    if(s.empty())    return result;
    int flag = 0;
    for(int i=0;i<s.size();i++){
        if(i == 0){
            //正负号判断
            if(s[i] == '+')    flag = 1;
            else if(s[i] == '-')    flag = -1;
            else if(s[i] >= '0' && s[i] <= '9'){
                result = s[i] - '0';
                flag = 1;
            }
            else break;
        }
        else{
            if(s[i] >= '0' && s[i] <= '9')
                result = result*10 + (s[i] - '0');
            //非法输入返回0
            else{
                result = 0;
                break;
            }
        }
    }
    return flag*result;
}

4. 排序算法总结

4.1 冒泡排序

基本思想：每次比较两个相邻的元素，如果他们的顺序错误就把他们交换过来。

时间复杂度：

• 最好的情况下，待排序记录已经有序，只需要一趟排序就可以完成，所以冒泡排序的最好时间复杂度为 O(n)。
• 最坏的情况下，待排序记录反序，这时需要 n - 1 趟排序，每趟排序需要比较 n - i 次比较操作，这时比较和移动的次数达到最大值，所以冒泡排序的最坏时间复杂度为 O(n ^ 2)。
• 平均时间复杂度为 O(n ^ 2)。因为它移动的次数较多，其平均时间性能还不如直接插入排序。

void bubble_sort(int s[],int n)
{
    for (int i=0;i<n;i++)
    {
        for (int j=n-1;j>i;j--)
        {
            if (s[j-1]>s[j])
            {
                swap(s[j-1],s[j]);
            }
        }
    }
}

冒泡排序的优化：在算法中增加一个标志exchange，用以标识本趟冒泡结果是否发生了交换；如果没有发生交换则exchange=false，表示全部元素已经排好，因而可以结束算法；如果exchange=true，表示本趟有元素发生交换，还需执行下一趟排序。

void new_bubble_sort(int s[],int n)
{
    bool exchange;
    for (int i=0;i<n;i++)
    {
        exchange = false;
        for (int j=n-1;j>i;j--)
        {
            if (s[j-1]>s[j])
            {
                swap(s[j-1],s[j]);
                exchange =true;
            }
        }
        if(exchange == false)   return;
    }
}

4.2 插入排序

基本思想：每次将一个待排序元素按其大小插入到前面已经排好的序列中的适当位置，直至元素全部插入为止

时间复杂度分析： 直接插入排序算法主要进行有两个操作，查找比较，移动记录。这两个操作均和记录长度n相关。其平均时间复杂度为O(n^2)。这在排序算法里面算慢的，但是当记录较少时，它的效率还是可以不错的。

空间复杂度分析：直接插入排序只需要一个元素的辅助空间，用于元素的位置交换O(1)。

直接插入排序是稳定排序。它在元素基本有序的情况下（接近最好情况），比较和移动的次数都较少，效率是很高的。

4.2.1 直接插入排序

void insert_sort(int s[],int n)
{
    for (int i=1;i<n;i++)
    {
        if (s[i]<s[i-1])
        {
            int temp = s[i], j=i-1;
            do 
            {
                s[j+1] = s[j];
                j--;
            } 
            while (j>=0 && temp<s[j]);
            s[j+1] = temp;
        }
    }
}

4.2.2 二分插入排序

利用二分查找，查找待插入元素应插入前面有序序列的位置。

4.3 选择排序

4.3 直接选择排序

基本思想：每次（第i次）在后面待排序元素中选出排序码最小的元素，作为有序元素序列的第i个元素。待n-2趟作完，待排序元素只剩下1个，就不用排序了。

时间复杂度分析：无论待排序记录的初始状态如何，在第i趟排序中选出最小关键字的记录，需做n-i次比较，因此，总的比较次数为：n*(n-1) /2=O(n^2)，当待排序记录的初始状态为正序时，移动次数为 0；当初始状态为反序时，每趟排序均要执行交换操作，总的移动次数取最大值3 *(n-1)。所以，直接选择排序的平均时间复杂度为O(n^2)。

非稳定排序。

void select_sort(int s[],int left,int right)
{
    for (int i=left;i<right;i++)
    {
        int min = i;
        for (int j=i+1;j<=right;j++)
        {
            if(s[j]<s[min]) min = j;
        }
        if(min != i)    swap(s[i],s[min]);
    }
}

4.3.2 堆排序

堆实际上是一棵完全二叉树，对于最大堆，其任何一非叶节点的关键字不小于其左右子节点的关键字。堆排序就是利用大最大堆堆顶记录的是最大关键字这一特性，使得每次从无序中选择最大记录变得简单。其基本思想为：

• 将初始待排序关键字序列(R1,R2....Rn)构建成最大堆，此堆为初始的无序区；
• 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n];
• 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

堆排序是采用的二叉堆进行排序的，二叉堆就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的定义，它的深度至少是lg(N+1)。最多是多少呢？由于二叉堆是完全二叉树，因此，它的深度最多也不会超过lg(2N)。因此，遍历一趟的时间复杂度是O(N)，而遍历次数介于lg(N+1)和lg(2N)之间；因此得出它的时间复杂度是O(N*lgN)。

4.4 快速排序

时间复杂度分析：

• 最坏情况：每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。此时，时间复杂度为 O(n ^ 2)。
• 最好情况：每次划分所取的基准都是当前无序区的"中值"记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数：0(nlgn)。
• 尽管快速排序的最坏时间为 O(n ^ 2)，但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名。它的平均时间复杂度为 O(nlgn)。

空间复杂度分析：快速排序需要一个栈来实现递归。若每次划分较为均匀（也就是对半分，基准值总是中值），则其递归树的高度为O(lgn)，故递归后需栈空间为O(lgn)。最坏情况下，递归树的高度为O(n)，所需的栈空间为O(n)。

int partition(int s[],int low,int high)
{
    int key = s[high];
    int piv = low;
    for (int i=low;i<high;i++)
    {
        if (s[i]<=key)
        {
            swap(s[piv],s[i]);
            piv++;
        }
    }
    swap(s[piv],s[high]);
    return piv;
}

void quick_sort(int s[],int left,int right)
{
    if (left<right)
    {
        int piv = partition(s,left,right);
        quick_sort(s,left,piv-1);
        quick_sort(s,piv+1,right);
    }
}

4.5 归并排序

归并排序是采用分治法的一个非常典型的应用，它要做两件事情：

• “分”, 就是将数组尽可能的分，一直分到原子级别；
• “并”，将原子级别的数两两合并排序，最后产生结果。

至于二个有序数列合并，只要比较二个数列的第一个数，谁小就先取谁安放到临时队列中，取了后将对应数列中这个数删除，直到一个数列为空，再将另一个数列的数据依次取出即可。

void merge(int* array, int tempArray, int left, int middle, int right)
{
    for(int i=left;i<=right;i++)    tempArray[i] = array[i];
    int s1 = left, s2 = mid +1, temp = left;
    while(s1 <=mid && s2 <= right)
    {
        if(tempArray[s1] <= tempArray[s2])
            array[temp++] = tempArray[s1++];
        else    array[temp++] = tempArray[s2++];
    }
    while(s1 <= mid) array[temp++] = tempArray[s1++];
    while(s2 <= right) array[temp] = tempArray[s2++];
}

void merge_sort(int* array, int* tempArray, int left, int right)
{
    if(left >= right)    return ;
    int mid = left + (right - left)/2;
    int tempArray = new int[right-left+1];
    merge_sort(array,tempArray,left,mid);
    merge_sort(array,tempArray,mid+1,right);
    merge(array,tempArray,left,mid,right);
}

5. 查找算法总结

5.1 顺序查找

设想有一个1M的数据，我们如何在里面找到我们想要的那个数据。此时数据本身没有特征，所以我们需要的那个数据可能出现在数组的各个位置，可能在数据的开头位置，也可能在数据的结束位置。这种性质要求我们必须对数据进行遍历之后才能获取到对应的数据。

int find(int array[], int len, int val)
{
    if(array == NULL && length == 0)    return -1;
    for(int i=0;i<len;i++){
        if(val == array[i])
            return i;
    }
    return -1;
}

分析：由于我们不清楚这个数据判断究竟需要多少次。但是，我们知道，这样一个数据查找最少需要1次，那么最多需要n次，平均下来可以看成是（1+n）/2，差不多是n的一半。我们把这种比较次数和n成正比的算法复杂度记为o（n）。

5.2 二分查找

如果数据排列地非常整齐，那结果会是什么样的呢？就像在生活中，如果平时不注意收拾整齐，那么找东西的时候非常麻烦，效率很低；但是一旦东西放的位置固定下来，所有东西都归类放好，那么结果就不一样了，我们就会形成思维定势，这样查找东西的效率就会非常高。那么，对一个有序的数组，我们应该怎么查找呢？二分法就是最好的方法。

int BinaryFind(int array[], int len, int val)
{
    if(array == NULL && length == 0)    return -1;
    int start = 0, end = len-1, middle=0;
    while(start<=end){
        middle = start + (end - start)/2;
        if(val == array[middle])    return middle;
        else if(val > array[middle])    start = middle+1;
        else end = middle-1;
    }
    return -1;
}

分析：上面我们说到普通的数据查找算法复杂度是o（n）。那么我们可以用上面一样的方法判断一下算法复杂度。这种方法最少是1次，那么最多需要多少次呢？我们发现最多需要log（n+1）/log（2）即可。

5.3 二叉搜索树

二叉搜索树是二分查找的二叉树实现，二叉搜索树每个结点都有作为搜索依据的关键码，所有结点的关键码互不相同；左子树（若存在）上的所有结点的关键码都小于根结点的关键码；右子树（若存在）上的所有结点的关键码都大于根结点的关键码；左子树和右子树也是二叉搜索树。

如果对一棵二叉搜索树进行中序遍历，可以按从小到大的顺序，将各结点关键码排列起来，所以也称为二叉排序树。

平衡二叉树是一种高度平衡的二叉搜索树，是为了提高二叉搜索树的效率，减少树的平均搜索长度。其具有以下性质：其左右子树都是平衡二叉树，且左子树和右子树的高度之差的绝对值不超过1。如过它有n个结点，其高度可保持在O(log2n)。

typedef struct _NODE
{
    int data;
    struct _NODE* left;
    struct _NODE* right;
}NODE;

const NODE* find_data(const NODE* pNode, int data){
    if(NULL == pNode)
        return NULL;

    if(data == pNode->data)
        return pNode;
    else if(data < pNode->data)
        return find_data(pNode->left, data);
    else
        return find_data(pNode->right, data);        
}

5.4 Hash表

typedef struct _LINK_NODE
{
    int data;
    struct _LINK_NODE* next;
}LINK_NODE;

LINK_NODE* hash_find(LINK_NODE* array[], int mod, int data)
{
    int index = data % mod;
    if(NULL == array[index])
        return NULL;

    LINK_NODE* pLinkNode = array[index];
    while(pLinkNode){
        if(data == pLinkNode->data)
            return pLinkNode;
        pLinkNode = pLinkNode->next;
    }

    return pLinkNode;
}

分析：hash表因为不需要排序，只进行简单的归类，在数据查找的时候特别方便。查找时间的大小取决于mod的大小。mod越小，那么hash查找就越接近于普通查找；那么hash越大呢，那么hash一次查找成功的概率就大大增加。

6. 二分查找的变种

6.1 给定一个有序（非降序）数组A，可含有重复元素，求最小的i使得A[i]等于target，不存在则返回-1

此题也就是求target在数组中第一次出现的位置。这里可能会有人想先直接用原始的二分查找，如果不存在直接返回-1，如果存在，然后再顺序找到这个等于target值区间的最左位置，这样的话，最坏情况下的复杂度就是O（n）了，没有完全发挥出二分查找的优势。这里的解法具体过程请参考实现代码与注释。

int searchFirstPos(int A[], int n, int target)  
{  
    if(n <= 0) return -1;  
    int low = 0, high = n-1;  
    while(low < high)  
    {  
        int mid = low+((high-low)>>1);  
        if(A[mid] < target)  
            low = mid+1;  
        else // A[mid] >= target  
            high = mid;  
    }  
    /*  
    循环过程中，当low大于0时，A[low-1]是小于target的，因为A[mid] < target时， 
    low=mid+1；当high小于n-1时，A[high]是大于等于target的，因为A[mid] >= target时， 
    high = mid；循环结束时，low 等于 high，所以，如果A[low](A[high])等于target， 
    那么low(high)就是target出现的最小位置，否则target在数组中不存在。 
    */  
    if(A[low] != target)  
        return -1;  
    else  
        return low;  
}  

6.2 给定一个有序（非降序）数组A，可含有重复元素，求最大的i使得A[i]等于target，不存在则返回-1

int searchLastPos(int A[], int n, int target)  
{     
    if(n <= 0) return -1;  
    int low = 0, high = n-1;  
    while(low < high)  
    {  
        /* 
        这里中间位置的计算就不能用low+((high-low)>>1)了，因为当low+1等于high 
        且A[low] <= target时，会死循环；所以这里要使用low+((high-low+1)>>1)， 
        这样能够保证循环会正常结束。 
        */  
        int mid = low+((high-low+1)>>1);  
        if(A[mid] > target)  
            high = mid-1;  
        else // A[mid] <= target  
            low = mid;  
    }  
    /*  
    循环过程中，当high小于n-1时，A[high+1]是大于target的，因为A[mid] > target时， 
    high=mid-1；当low大于0时，A[low]是小于等于target的，因为A[mid] <= target时， 
    low = mid；循环结束时，low 等于 high，所以，如果A[high](A[low])等于target， 
    那么high(low)就是target出现的最大位置，否则target在数组中不存在。 
    */  
    if(A[high] != target)  
        return -1;  
    else  
        return high;  
}

6.3 给定一个有序（非降序）数组A，可含有重复元素，求target在数组中出现的次数

求出第一次出现位置和最后一次出现位置。由于前面都已实现，这里不多解释。

int count(int A[], int n, int target)  
{  
    int firstPos = searchFirstPos(A, n, target); // 第一次出现位置  
    if(firstPos == -1)  
        return 0;  
    int lastPos = searchLastPos(A, n, target);  // 最后一次出现位置  
    return lastPos-firstPos+1;  // 出现次数  
}

7. 数学相关的算法

7.1 计算最大公约数

辗转相除法
例1 .求两个正数8251和6105的最大公因数.
（分析：辗转相除→余数为零→得到结果）
8251＝6105×1＋2146
显然8251与6105的最大公因数也必是2146的因数,同样6105与2146的公因数也必是8251的因数,所以8251与6105的最大公因数也是6105与2146的最大公因数.
6105＝2146×2＋1813
2146＝1813×1＋333
1813＝333×5＋148
333＝148×2＋37
148＝37×4＋0
则37为8251与6105的最大公因数.

利用辗转相除法求最大公因数的步骤如下：
第一步：用较大的数m除以较小的数n得到一个商q0和一个余数r0；
第二步：若r0＝0,则n为m,n的最大公因数；若r0≠0,则用除数n除以余数r0得到一个商q1和一个余数r1；
第三步：若r1＝0,则r1为m,n的最大公因数；若r1≠0,则用除数r0除以余数r1得到一个商q2和一个余数r2；
……
依次计算直至rn＝0,此时所得到的rn－1即为所求的最大公因数.

//递归版本
int gcd(int a,int b) 
{ 
    int g; 
    if(b==0) 
        g=a; 
    else 
        g=gcd(b,a%b); 
    return g; 
}
//迭代版本
int gcd(int a, int b)
{
    int c;
    if(a<b) swap(a,b);
    while(b != 0){
        c = a%b;
        a = b;
        b = c;
    }
    return a;
}