Unity中的快速排序算法&&二分查找

一、 快速排序

介绍：
　　快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来，且在大部分真实世界的数据，可以决定设计的选择，减少所需时间的二次方项之可能性。
步骤：
从数列中挑出一个元素，称为 "基准"（pivot），
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

using UnityEngine;
using System.Collections;

public class QuickSort : MonoBehaviour {
    //定义一个数组
    private int[] array = new int[] { 5, 9, 3, 1, 4, 7, 2 };

    void Awake()
    {
        //调用排序方法
        QuickSortArray(array, 0, array.Length - 1);
        //打印数组
        foreach (int item in array)
        {
            Debug.Log(item);
        }
    }
    /// <summary>
    /// 快速排序的方法
    /// </summary>
    /// <param name="array">数组</param>
    /// <param name="start">数组起始位置</param>
    /// <param name="end">数组终止位置</param>
    void QuickSortArray(int[] array, int start, int end)
    {
        //若数组中数小于等于0直接返回
        if (start >= end) return;
        //定义一个基准值
        int pivot = array[start];
        //定义2个索引指向数组的而开头和结束
        int left = start;
        int right = end;
        //按照从小到大的排序，直到2数相遇结束排序
        while (left < right)
        {
            //第一轮比较
            //把所有left右边的数都和基准值比较,获得最左边数在排序后位于数组中的位置（索引）
            while (left < right  && array[right] >= pivot) 
            {
                right--;
            }
            //将该数放到数组中的该位置
            array[left] = array[right];
            //第二轮比较
            //把所有left右边的数都和基准值比较,获得最左边数在排序后位于数组中的位置（索引）
            while (left < right && array[left] <= pivot)
            {
                left++;
            }
            //将该数放到数组中的该位置
            array[right] = array[left];
        }
        //将2轮比较之后的数组的起始值再赋为基准值（已经得到最大值，并在最后一位）
        array[left] = pivot;
        //递归该方法（每次剔除一个排好的数）
        QuickSortArray(array, start, left - 1);
        QuickSortArray(array, left + 1, end);
    }
}

2、演示的结果图如下

快速排序.gif

二、二分查找

1、简介

二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。简单的来说利用的原理就是我们中学所学的二分查找，空间复杂度为O(n),时间复杂度为O(log(n))。

2、伪算法图

二分查找.jpg.png

注意使用二分查找的数组必须是排序好的数组。

3、结合快速排序的算法写的二分查找代码

using System;
namespace QucikSortDemo
{
    class Program
    {
        static void Main(string[] args)
        {
            //定义数组
            int[] array = new int[] { 5, 8, 6, 1, 3, 4, 2, 7 };
            //快排
            QuickSort(array, 0, array.Length - 1);
            //二分查找
            BinSearch(array, array.Length,5);
            Console.ReadKey();
        }
        /// <summary>
        /// 二分查找
        /// </summary>
        /// <param name="array"></param>
        /// <param name="arrayLength"></param>
        /// <param name="key"></param>
        /// <returns></returns>
        static int BinSearch(int [] array,int arrayLength,int key)
        {
            //最小索引
            int low = 0;
            //最大索引
            int high = arrayLength;
            //中间索引
            int mid = (low + high) / 2;
            //直到最小索引小于最大索引跳出循环
            while (low <=high)
            {
                //若中间值为所有查找的数key
                if (array[mid] == key)
                {
                    //输出中间数key
                    Console.WriteLine("数字{0}存在，在数组的索引为{1}", key, mid);
                    return mid;
                    
                }
                //中间数大于key时，查找左边的数
                if (array[mid] > key)
                {
                    mid--;
                }
                //中间数小于key，查找右边
                else
                {
                    mid++;
                }
            }
            //否则输出无要查找的值
            Console.WriteLine("数字{0}不存在", key);
            return -1;
            
        }

        /// <summary>
        /// 快速排序算法
        /// </summary>
        /// <param name="array"></param>
        /// <param name="start"></param>
        /// <param name="end"></param>
        static void QuickSort(int [] array ,int start , int end)
        {
            int left = start;
            int right = end;
            if (start >= end)
            {
                return;
            }
            int privot = array[left];
            while (left < right)
            {
                while (left < right && array[right] >= privot)
                {
                    right--;
                }
                array[left] = array[right];
                while (left < right && array[left] <= privot)
                {
                    left++;
                }
                array[right] = array[left];
            }
            array[left] = privot;
            QuickSort(array, start, end - 1);
            QuickSort(array, start + 1, end);
        }
    }
}