一、快速排序算法

步驟1：選取一串?dāng)?shù)字中的中心軸

步驟2：將大于中心軸的數(shù)字放在右邊

步驟3：將小于中心軸的數(shù)字放在左邊

步驟4：分別對(duì)左右兩個(gè)序列重復(fù)前三步操作

public class QuickSort : MonoBehaviour
{
    private void Start()
    {
        int[] Nums = { 4, 3, 6, 1, 8, 0, 3, 2, 5, 7};
        Sort(Nums, 0, 9);
        for (int i = 0; i < 10; i++)
        {
            Debug.Log(Nums[i]);
        }
    }
    void Sort(int[] nums,int left,int right)
    {
        //退出條件
        if (left  >= right)
            return;
        int i = left;
        int j = right;

        //中心元素取為第一個(gè)元素
        int temp = nums[left];

        while(i != j)
        {
            //從最右邊的元素開(kāi)始比較中心元素
            while(i < j && nums[j] >= temp)
            {
                j--;
            }
            if(i < j )
            {
                nums[i] = nums[j];
            }
           while(i < j && nums[i] <= temp)
            {
                i++;
            }
           if(i < j)
            {
                nums[j] = nums[i];
            }
        }
        nums[i] = temp;
        Sort(nums, left, i - 1);
        Sort(nums, i+1, right);
    }
}

二、冒泡排序算法

步驟一、從數(shù)組的最左側(cè)兩個(gè)元素進(jìn)行比較

步驟二、將較大的數(shù)向右移動(dòng)，再進(jìn)行比較

步驟三、直到將最大的數(shù)字放在最右邊

步驟四、重復(fù)上述操作，不過(guò)這次比較數(shù)組的數(shù)量-1

public class BubbleSort : MonoBehaviour
{
    private void Start()
    {
        int[] array = { 6, 5, 8, 7, 1, 2, 3, 5 };
        Sort(array);
        for (int i = 0; i < array.Length; i++)
        {
            Debug.Log(array[i]);
        }
    }

    private void Sort(int[] array)
    {
        //進(jìn)行i次排序，對(duì)數(shù)組內(nèi)所有元素都進(jìn)行比較
        for (int i = 0; i < array.Length - 1; i++) 
        {
            //對(duì)某一元素進(jìn)行的相鄰元素的比較，比較次數(shù)差i次
            for(int j = 0; j < array.Length-1-i; j++)
            {
                if(array[j] > array[j+1])
                {
                    int temp = array[j];
                    //如果左邊的數(shù)字比右邊的大，就把大的數(shù)字向右平移一位
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }
}

三、二分查找（要求數(shù)組順序排列）

一、初始化三個(gè)序號(hào)，分別代表第一個(gè)，最后一個(gè)和中間序號(hào)

二、用中間序號(hào)的值和目標(biāo)值進(jìn)行對(duì)比，如果相等就返回

三、如果中間序號(hào)的值大于目標(biāo)值，就向左縮小范圍

四、如果中間序號(hào)的值小于目標(biāo)值，就向右縮小范圍

第一種實(shí)現(xiàn)：常規(guī)實(shí)現(xiàn)

public class BinarySearch : MonoBehaviour
{
    private void Start()
    {
        int[] array = { 8, 11, 21, 28, 32, 43, 48, 56, 69, 72, 80, 94 };
        Debug.Log(Search(array, 80)); 
    }
    private int Search(int[] array,int key)
    {
        var min = 0;
        var max = array.Length - 1;
        var mid = 0;
        while(min <= max)
        {
            mid = (min + max) / 2;
            if(array[mid] > key)
            {
                max = mid - 1;
            }
            else if(array[mid] < key)
            {
                min = mid + 1;
            }
            else if(array[mid] == key)
            {
                return mid;
            }
        }
        return 0;
    }
}

第二種實(shí)現(xiàn)：遞歸實(shí)現(xiàn)

Debug.Log(SearchTwo(array, 80,0,12));
 
private int SearchTwo(int[] array,int key,int low,int high)
    {
        if (low > high)
            return -1;
        var mid = (low + high) >> 1;
        if (array[mid] > key)
        {
            return SearchTwo(array, key, low, mid - 1);
        }
        else if (array[mid] < key)
        {
            return SearchTwo(array, key, mid + 1, high);
        }
        else
            return mid;
    }
}

四、基于四叉樹(shù)/八叉樹(shù)的碰撞檢測(cè)

五、隨機(jī)尋路算法、跟蹤算法、閃避算法（與跟蹤算法相反）

DFS(Deep First Search)、BFS(Breadth Fitst Search)

六：A*尋路算法

A*主要是利用三個(gè)數(shù)值來(lái)計(jì)算最佳路徑，分別是G代價(jià)、H代價(jià)、F代價(jià)

G：從某節(jié)點(diǎn)到開(kāi)始節(jié)點(diǎn)的移動(dòng)距離

H：從某節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的估計(jì)移動(dòng)距離，從任何節(jié)點(diǎn)迭代實(shí)際所需的距離大于或者等于H代價(jià)。

F：F代價(jià)等于G+H,F值越低，作為尋徑選擇就越有吸引力

我們的目標(biāo)是簡(jiǎn)單的選擇最低的F代價(jià)，不斷的重復(fù)，直到我們的目標(biāo)節(jié)點(diǎn)

代碼部分可以見(jiàn)：

(1條消息) Unity A星（A Star/A*）尋路算法_unity尋路算法_九本才的博客-CSDN博客

現(xiàn)在有A*的尋路插件

七：B*尋路算法

理解B*可以把它想象成一個(gè)朝著目標(biāo)前進(jìn)的貪吃蛇，如果遇到障礙就會(huì)分裂成兩條蛇，一左一右繞開(kāi)障礙，只要有一條蛇碰到目標(biāo)就結(jié)束尋路

優(yōu)點(diǎn)：目標(biāo)點(diǎn)在封閉空間內(nèi)時(shí)，BStar效率優(yōu)勢(shì)明顯

缺點(diǎn)：喜歡貼著墻走

八、Nav Mesh導(dǎo)航系統(tǒng)

NacigationMesh是一種數(shù)據(jù)結(jié)構(gòu)，用于描述游戲世界的可行走表面

Navigation是Unity自帶的導(dǎo)航，具備基本的Bake，NavMesh和NavMeshAgent等基本導(dǎo)航功能

新版中有NavMeshComponent，能夠?qū)崿F(xiàn)動(dòng)態(tài)烘焙

步驟：

打開(kāi)Navgation面板、

設(shè)置烘焙參數(shù)(Bake Agent)、

設(shè)置行走區(qū)域(設(shè)置為Navigation Static)、烘焙

角色添加尋路控制器(Nav Mesh Agent)、

掛在一個(gè)腳本到Player身上，告訴目標(biāo)點(diǎn)即可

using UnityEngine;
using UnityEngine.AI;

public class Player : MonoBehaviour
{
	private NavMeshAgent agent;
	public Transform target;

	void Start()
	{
		agent = GetComponent<NavMeshAgent>();
		agent.destination = target.position;
	}
}

九、數(shù)組中僅出現(xiàn)過(guò)一次的元素

方法一：使用位異或運(yùn)算

僅針對(duì)數(shù)組中只出現(xiàn)一次的情況

使用位運(yùn)算，最后只剩下沒(méi)有重復(fù)的元素

using UnityEngine;
/// <summary>
/// 某個(gè)只出現(xiàn)一次的數(shù)字
/// 思路：采用異或操作，相同為0，不同為1
/// a^a = 0; a^0 = a;
/// </summary>
public class SingleNumber : MonoBehaviour
{
    public int[] nums = { 1, 2, 3, 2, 1 };
    private void Start()
    {
        SingleNumber1(nums);
    }
    public void SingleNumber1(int[] nums )
    {
        int result = 0;
        for(int i = 0; i < nums.Length; i++)
        {
            //第一次異或操作完了就是第一個(gè)元素，然后第一個(gè)元素和第二個(gè)元素對(duì)比
            //如果兩個(gè)相同，返回就是0，如果不相同，
            result ^= nums[i];
        }
        Debug.Log(result);
    }
}

方法二：使用Set集合

HashSet具有去重性

使用!Add即可

   /// <summary>
    /// 使用HashSet來(lái)解決，HashSet具有去重特性！
    /// </summary>
    /// <param name="nums"></param>
    public void SingleNumber2(int[] nums)
    {
        HashSet<int> hash = new HashSet<int>();
        for (int i = 0; i< nums.Length;i++)
        {
            if(!hash.Add(nums[i]))
            {
                hash.Remove(nums[i]);
            }
        }
        foreach (var item in hash)
            Debug.Log(item);
    }
}

十、多數(shù)元素

給定一個(gè)大小為 n 的數(shù)組?nums ，返回其中的多數(shù)元素。多數(shù)元素是指在數(shù)組中出現(xiàn)次數(shù) 大于?? n/2 ??的元素。

方法一、排序后輸出中間元素即可

public class Majority : MonoBehaviour
{
    int[] nums = { 1, 2, 3, 4, 5, 6, 7, 2, 2, 2, 2, 2 };
    private void Start()
    {
        Major1(nums);
        Major2(nums);
    }
    /// <summary>
    /// 方法1：先排序，再輸出一半中的元素
    /// </summary>
    /// <param name="nums"></param>
    public void Major1(int [] nums)
    {
        Array.Sort(nums);
        Debug.Log(nums[nums.Length/2]);
    }

方法二、摩爾投票法

把第一個(gè)元素作為開(kāi)始元素，如果緊接的兩個(gè)元素不相同，count就減，如果相同，count就加，到最后還剩下的count就是最多的元素

/// <summary>
    /// 方法2：摩爾投票法
    /// </summary>
    public void Major2(int[] nums)
    {
        int major = nums[0];
        int count = 1;
        for (int i = 1; i < nums.Length; i++)
        {
            //消除完了，就進(jìn)行下一個(gè)
            if(count == 0)
            {
                count++;
                major = nums[i];
            }
            //跟后面的元素相同的話，這個(gè)元素?cái)?shù)目就繼續(xù)增加
            else if(major == nums[i])
            {
                count++;
            }
            else
            {
                count--;
            }
        }
        Debug.Log(major);
    }
}

十一、合并兩個(gè)有序數(shù)組

給你兩個(gè)按 非遞減順序 排列的整數(shù)數(shù)組?nums1 和 nums2，另有兩個(gè)整數(shù) m 和 n ，分別表示 nums1 和 nums2 中的元素?cái)?shù)目。

請(qǐng)你 合并 nums2 到 nums1 中，使合并后的數(shù)組同樣按 非遞減順序 排列。

輸入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
輸出：[1,2,2,3,5,6]
解釋：需要合并 [1,2,3] 和 [2,5,6] 。
合并結(jié)果是 [1,2,2,3,5,6] ，其中斜體加粗標(biāo)注的為 nums1 中的元素。

方法1：使用三目運(yùn)算符

即：

x?y:z 表示如果表達(dá)式x為true，則返回y；
如果x為false，則返回z

是省略if{}else{}的簡(jiǎn)單形式。

using UnityEngine;
/// <summary>
/// 合并兩個(gè)有序數(shù)組
/// </summary>

public class Merge : MonoBehaviour
{
    int[] nums1 = { 1, 2, 3,0,0,0 };
    int[] nums2 = { 2, 5, 6 };
    private void Start()
    {
        MergeNums(nums1, 3, nums2, 3);
        foreach (var item in nums1)
        {
            Debug.Log(item);
        }
    }
    /// <summary>
    /// 合并有序數(shù)組方法1
    /// </summary>
    /// <param name="數(shù)組1"></param>
    /// <param name="數(shù)組1的長(zhǎng)度"></param>
    /// <param name="數(shù)組2"></param>
    /// <param name="數(shù)組2的長(zhǎng)度"></param>
    public int[] MergeNums(int[] nums1,int m,int[] nums2,int n)
    {
        int i = m - 1;
        int j = n - 1;
        int end = m + n - 1;
        while(j>=0)
        {
            nums1[end--] = (i >= 0 && nums1[i] > nums2[j]) ? nums1[i--] : nums2[j--];
        }
        return nums1;
    }
}

方法二：使用官方API

Array.Copy：合并兩個(gè)數(shù)組

Array.Sort:排序方法，由小及大

public void MegerNums2(int[] num1, int m ,int[] nums2, int n )
    {
        Array.Copy(nums2, 0, nums1, m, n);
        Array.Sort(nums1);
    }

十二、雞蛋掉落

給你 k 枚相同的雞蛋，并可以使用一棟從第 1 層到第 n 層共有 n 層樓的建筑。

已知存在樓層 f ，滿足?0 <= f <= n ，任何從 高于 f 的樓層落下的雞蛋都會(huì)碎，從 f 樓層或比它低的樓層落下的雞蛋都不會(huì)破。

每次操作，你可以取一枚沒(méi)有碎的雞蛋并把它從任一樓層 x 扔下（滿足?1 <= x <= n）。如果雞蛋碎了，你就不能再次使用它。如果某枚雞蛋扔下后沒(méi)有摔碎，則可以在之后的操作中 重復(fù)使用 這枚雞蛋。

請(qǐng)你計(jì)算并返回如果要確定?f?確切的值?的話，我們的?最小操作次數(shù)?是多少？

? ?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-462910.html

到了這里，關(guān)于游戲開(kāi)發(fā)中常用的算法1(20道題一篇文章)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！