Unity3d快速排序算法实现

C#

浏览数:47

2019-10-11

AD:资源代下载服务

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列
快排百科释义

Unity实现快排代码

using UnityEngine;

/// <summary>
/// 快速排序
/// </summary>
public class QuickSortScript : MonoBehaviour
{
    //需要排序的数组
    private int[] array = new[] {3, 5, 6, 8, 9, 7, 4, 2, 0, 1};

    void Awake()
    {
        //调用快速排序
        QuickSort(array, 0, array.Length - 1);
        //循环输出
        foreach (var item in array)
        {
            Debug.Log(item);
        }
    }

    /// <summary>
    /// 快速排序
    /// </summary>
    /// <param name="array"> 要排序的数组 </param>
    /// <param name="start"> 数组的起始位置 </param>
    /// <param name="edn"> 数值的终止位置 </param>
    void QuickSort(int[] array, int start, int end)
    {
        //递归的出口(起始值大于或等于终止值的时候,不再执行,return)
        if (start >= end) return;

        //假设第一个元素作为我们的基准
        int pivot = array[start];

        //升序
        //定义两个指针指向我们数组的开头和结尾
        int left = start; //左边为开始
        int right = end; //右边为结束


        //ToDo
        //按照基准排序(小的数放左边,大的数放右边)
        //直到两个数相遇结束排序
        //如果左边小于右边
        while (left < right)
        {
            //从右往左搜索比pivot大的数值
            while (left < right && array[right] >= pivot)
            {
                right--;
            }
            //比pivot小的数值放左边
            array[left] = array[right];
            //从左往右搜索比pivot大的数值
            while (left < right && array[left] <= pivot)
            {
                left++;
            }
            //比pivot大的数值放右边
            array[right] = array[left];
        }
        //跳出循环的时候,left=right
        //左边都比pivot小,右边都比pivot大,将pivot放在下标当前位置
        array[left] = pivot;

        //递归
        QuickSort(array, start, left - 1);
        QuickSort(array, left + 1, end);
    }
}

作者:好怕怕