经典算法代码集

美女镇楼

本文是经典算法的集合，使用C#语言来实现。

1. 二叉树

二叉树结构定义

public class BTNode<T>
{
    public T data;

    public BTNode<T> leftChild;

    public BTNode<T> rightChild;

    public BTNode(T t)
    {
        data = t;
    }
}

1.1 二叉树的遍历

先定义一个遍历处理的泛型委托如下：

public delegate void TravelFunc<T> (BTNode<T> t);

二叉树的遍历，根据节点的遍历顺序，分为先序、中序、后序遍历三种，而通常的实现包括递归遍历和非递归遍历。

1.1.1 递归遍历

递归遍历算法相当好理解，以先序为例，针对树中任意节点，先处理自己，再处理左子节点，最后处理右子节点，可以很直观的写出递归遍历的代码，很简单，这里只要注意递归结束的条件即可。

    // 先序递归遍历
    public static void preOrderTravel_Recursive<T>(BTNode<T> t, TravelFunc<T> func)
    {
        if (t != null && func != null)
        {
            func(t);

            preOrderTravel_Recursive<T>(t.leftChild, func);

            preOrderTravel_Recursive<T>(t.rightChild, func);
        }
    }

    // 中序递归遍历
    public static void inOrderTravel_Recursive<T>(BTNode<T> t, TravelFunc<T> func)
    {
        if (t != null && func != null)
        {
            inOrderTravel_Recursive<T>(t.leftChild, func);

            func(t);

            inOrderTravel_Recursive<T>(t.rightChild, func);
        }
    }

    // 后序递归遍历
    public static void postOrderTravel_Recursive<T>(BTNode<T> t, TravelFunc<T> func)
    {
        if (t != null && func != null)
        {
            postOrderTravel_Recursive<T>(t.leftChild, func);
            postOrderTravel_Recursive<T>(t.rightChild, func);

            func(t);
        }
    }

1.1.2 非递归遍历

如果不使用递归算法，那么很明显需要使用循环来进行替代，并且需要借助堆栈来完成，整体思想就是在处理节点时，若节点非空，则先入栈，针对左子节点和右字节点依次处理。当节点为空时，从栈顶取出元素，根据先序、中序和后序逻辑分别处理栈顶节点。

• 先序遍历：
  若当前节点非空，执行当前节点，再将当前节点入栈，处理左子节点
  若当前节点为空，取出栈顶节点，处理栈顶节点的右子节点

    public static void preOrderTravel<T>(BTNode<T> t, TravelFunc<T> func)
    {
        Stack<BTNode<T>> stack = new Stack<BTNode<T>>();
        BTNode<T> curNode = t;
        while (stack.Count > 0 || curNode != null)
        {
            if (curNode != null)
            {
                func(curNode);
                stack.Push(curNode);
                curNode = curNode.leftChild;
            }
            else
            {
                curNode = stack.Pop();
                curNode = curNode.rightChild;
            }
        }
    }

• 中序遍历
  若当前节点非空，将当前节点入栈，处理左子节点
  若当前节点为空，取出栈顶节点，执行栈顶节点，然后处理栈顶的右子节点

    public static void inOrderTravel<T>(BTNode<T> t, TravelFunc<T> func)
    {
        Stack<BTNode<T>> stack = new Stack<BTNode<T>>();
        BTNode<T> curNode = t;
        while (stack.Count > 0 || curNode != null)
        {
            if (curNode != null)
            {                
                stack.Push(curNode);
                curNode = curNode.leftChild;
            }
            else
            {
                curNode = stack.Pop();
                func(curNode);
                curNode = curNode.rightChild;
            }
        }
    }

• 后序遍历
  后序遍历在处理完子节点之后再处理父节点，需要知道当前处理完的节点是否右子节点
  若当前节点非空，将当前节点入栈，处理左子节点
  若当前节点为空，取出栈顶，若上次处理的是栈顶的左子节点，则将取出的栈顶入栈，处理它的右子节点
  若上次处理的是栈顶的右子节点，则执行栈顶节点，处理空节点

    public static void postOrderTravel<T>(BTNode<T> t, TravelFunc<T> func)
    {
        Stack<BTNode<T>> stack = new Stack<BTNode<T>>();
        BTNode<T> curNode = t;
        Stack<bool> rightFlagStack = new Stack<bool>();
        while (stack.Count > 0 || curNode != null)
        {
            if (curNode != null)
            {
                stack.Push(curNode);
                rightFlagStack.Push(false);
                curNode = curNode.leftChild;
            }
            else
            {
                curNode = stack.Pop();
                bool lastIsRight = rightFlagStack.Pop();
                if (lastIsRight)
                {
                    func(curNode);                    
                    curNode = null;
                } else
                {
                    stack.Push(curNode);
                    rightFlagStack.Push(true);
                    curNode = curNode.rightChild;
                }                
            }
        }
    }

注：此处使用了一个堆栈来记录每次处理的节点是否右子节点，你也可以使用一个局部变量记录最近一次处理的节点，然后和每次非空节点的右子节点作比较。

2. 数值判断类

2.1 判断是否 2 的 n 次幂

题目：给定一个正整数，判断它是否 2 的 n 次幂
思考：这里很容易陷入这样的想法：从 n 开始循环用 2 去取余，若余数为1非0，那么返回0，除到最后得到1都没出现余数非0的情况，那么返回1，代码如下

    // x 是否 2 的 n 次幂
    public static bool isPowerOfTwo(uint x)
    {        
        if (x == 0)
        {
            return false;
        }

        if (x == 1)
        {
            return true;
        }

        bool ret = true;
        uint value = x;        
        while (value >= 2)
        {
            if (value % 2 != 0)
            {
                ret = false;
                break;
            }
            value = value / 2;
        }
        return ret;
    }

这个算法虽然没有问题，但是它效率比较低，有没有更高效取巧的方法呢？我们来考虑 2 的 n 次幂的数值有什么特点，我们列举复合条件的 4、8、16 等数值的二进制表示并观察

数值 x	x 的二进制表示	x - 1 的二进制表示	x & (x -1 ) 的二进制表示
1	0000 0001	0000 0000	0000 0000
2	0000 0010	0000 0001	0000 0000
4	0000 0100	0000 0011	0000 0000
8	0000 1000	0000 0111	0000 0000
16	0001 0000	0000 1111	0000 0000

通过观察我们可以得到一个结论 : 若一个数是 2 的 n 次幂，那么它和它减1的数进行与运算，得到的值为0，于是可以得到如下的优化算法：

    public static bool isPowerOfTwoEffective(uint x)
    {
        if (x == 0)
        {
            return false;
        }

        return (x & (x - 1)) == 0;
    }

3. 数据结构

3.1 使用堆栈来模拟队列的操作

队列的特性是先进先出，堆栈的特性是后进先出，这里需要使用两个堆栈来实现队列的特点，代码如下

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class KrinQueue<T>
{
    Stack<T> inStack = new Stack<T>();
    Stack<T> outStack = new Stack<T>();

    // 队列大小
    public int Count
    {
        get
        {
            return inStack.Count + outStack.Count;
        }
    }

    // 入队，如果 outStack 非空说明上次操作为出队，先反序到 inStack，再追加元素，否则直接追加
    public void Enqueue(T value)
    {
        if (outStack.Count > 0)
        {
            while (outStack.Count > 0)
            {
                T top = outStack.Pop();
                inStack.Push(top);
            }

            inStack.Push(value);
        } else
        {
            inStack.Push(value);
        }
    }

    // 出队，若 outStack 非空说明上次操作为出队，直接从 outStack 栈顶取元素即为出队，否则从 inStack 反序到 outStack，取栈顶元素即可出队
    public T Dequeue()
    {
        T value = default(T);
        if (outStack.Count > 0)
        {
            value = outStack.Pop();
        } else
        {
            while (inStack.Count > 0)
            {
                T v = inStack.Pop();
                outStack.Push(v);
            }

            value = outStack.Pop();
        }

        return value;
    }
}

4. 排序

4.1 快速排序

排序思想：递归进行，在待排序序列中取第一个元素作为 pivot，从序列尾部扫描，遇到比 pivot 小的元素，则交换到 pivot 所在位置，然后从序列头部扫描，遇到比 pivot 大的元素，则和 pivot 当前位置交换，一直到两个扫描的下标相遇，可以确保 pivot 元素左边的所欲元素都比 pivot 小，pivot 右边的元素都比 pivot 大，对前后两个子序列递归同样的逻辑即可，递归结束条件是起始位置不小于终止位置，代码如下：

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class QuickSort : KrinSort
{
    private static void _QuickSort<T>(T[] array, int start, int end) where T : System.IComparable
    {
        if (start < 0 || end >= array.Length || start >= end)
        {
            return;
        }


        T pivot = array[start];
        int i = start;
        int j = end;

        if (start >= end)
        {
            return;
        }
        while (i < j)
        {
            while (i < j && array[j].CompareTo(pivot) > 0)
            {
                j--;
            }

            array[i] = array[j];

            while (i < j && array[i].CompareTo(pivot) < 0)
            {
                i++;
            }

            array[j] = array[i];
        }

        array[i] = pivot;

        _QuickSort<T>(array, start, i - 1);

        _QuickSort<T>(array, i + 1, end);
    }

    public override void Sort<T>(T[] array)
    {
        if (array == null)
        {
            return;
        }

        _QuickSort<T>(array, 0, array.Length - 1);
    }
}

4.2 冒泡排序

排序思想：第一轮排序，将最大的数找出来放到最大位置，第二轮找第二大的数，依次类推，一共需要循环 n 次，代码如下

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class BubbleSort : KrinSort
{
    public override void Sort<T>(T[] array)
    {
        if (array == null || array.Length <= 0)
        {
            return;
        }

        for (int i = 0; i < array.Length - 1; i ++)
        {
            for (int j = 0; j < array.Length - i - 1; j ++)
            {
                if (array[j].CompareTo(array[j + 1]) > 0)
                {
                    T temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }
}

4.3 插入排序

排序思想：下标 index 从 1 到 n，扫描一遍数组，认为 0 - index 部分是已排序数组，将第 index + 1 个元素插入到该部分正确位置，代码:

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class InsertSort : KrinSort
{
    public override void Sort<T>(T[] array)
    {
        if (array == null || array.Length <= 0)
        {
            return;
        }

        for (int i = 0; i < array.Length; i ++)
        {
            for (int j = i; j > 0; j --)
            {
                if (array[j].CompareTo(array[j-1]) < 0)
                {
                    T temp = array[j];
                    array[j] = array[j - 1];
                    array[j - 1] = temp;
                }
            }
        }
    }
}

4.4 选择排序

排序思想：遍历 n 次数组，每次将第 n 大的数放到下标为 n 的位置，在遍历过程中需要进行元素交换，实现代码：

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class SelectSort : KrinSort
{
    public override void Sort<T>(T[] array)
    {
        if (array == null || array.Length <= 0)
        {
            return;
        }

        for (int i = 0; i < array.Length; i ++)
        {
            T value = array[i];
            int select = i;
            for (int j = i; j < array.Length; j ++)
            {                
                if (array[j].CompareTo(value) < 0)
                {
                    value = array[j];
                    select = j;
                }
            }

            T temp = array[i];
            array[i] = array[select];
            array[select] = temp;
        }
    }
}

4.5 归并排序

排序思想：递归将数组等分成两部分，直到不能分（长度为1时），针对每个等分的子数组排序，得到两个子数组结果后，再合并到一起，合并的过程进行比较排序，最终得到完整的有序数组，代码：

using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class MergeSort : KrinSort
{
    public override void Sort<T>(T[] array)
    {
        if (array == null || array.Length <= 1)
        {
            return;
        }

        T[] ret = this._MergeSort<T>(array, 0, array.Length - 1); 
        for (int i = 0; i < ret.Length; i ++)
        {
            array[i] = ret[i];
        }
    }

    private T[] _MergeSort<T>(T[] array, int start, int end) where T : IComparable
    {
        int size = end - start + 1;
        T[] arr = new T[size];     
        if (size == 1)
        {
            arr[0] = array[start];
            return arr;
        } else if (size == 2)
        {
            if (array[start].CompareTo(array[end]) > 0)
            {
                arr[0] = array[end];
                arr[1] = array[start];
            }
            else
            {
                arr[0] = array[start];
                arr[1] = array[end];
            }

            return arr;
        }
        else
        {
            int mid = (start + end) / 2;
            T[] ret1 = { };
            if (mid - start >= 0)
            {
                ret1 = _MergeSort<T>(array, start, mid);
            }
            T[] ret2 = { };
            if (end - mid >= 0)
            {
                ret2 = _MergeSort<T>(array, mid + 1, end);
            }
            int idx1 = 0;
            int idx2 = 0;
            int index = 0;
            while (idx1 < ret1.Length || idx2 < ret2.Length)
            {
                if (idx2 >= ret2.Length)
                {
                    for (int i = idx1; i < ret1.Length; i ++)
                    {
                        arr[index] = ret1[i];
                        index++;
                    }
                    break;
                }

                if (idx1 >= ret1.Length)
                {
                    for (int i = idx2; i < ret2.Length; i ++)
                    {
                        arr[index] = ret2[i];
                        index++;
                    }
                    break;
                }

                if (ret1[idx1].CompareTo(ret2[idx2]) < 0)
                {
                    arr[index] = ret1[idx1];
                    idx1++;
                }
                else
                {
                    arr[index] = ret2[idx2];
                    idx2++;
                }

                index++;
            }

            return arr;
        }        
    }
}

参考：
八大排序算法