排序算法：C#使用泛型和IComparable接口来实现自定义通用堆排序,正态分布排序，排序工具类

2021.3.1更新：文章末尾加入A*算法中提到的排序类 1.堆排序代码

/// <summary> /// 堆排序 /// </summary> /// <typeparam name="T">返回类型</typeparam> /// <param name="type">需要排序的类型</param> /// <param name="isMaxHeap">是否大根堆</param> /// <returns></returns> public static List<T> HeapSort<T>(List<T> type,bool isMaxHeap) { for(int i = type.Count / 2 - 1; i >= 0; i--) { BuildHeap(type, i, type.Count, isMaxHeap); } for (int j = type.Count - 1; j > 0; j--) { Swap(type, 0, j); BuildHeap(type, 0, j, isMaxHeap); } return type; } private static void BuildHeap<T>(List<T> array,int i,int count,bool isMaxHeap) { if (isMaxHeap) { T temp = array[i]; for (int k = 2 * i + 1; k < count; k = 2 * k + 1) { if (k + 1 < count && (array[k] as IComparable<T>).CompareTo(array[k + 1])<0) { k++; } if ((array[k] as IComparable<T>).CompareTo(temp) > 0) { Swap(array, i, k); i = k; } else { break; } } } else { T temp = array[i]; for (int k = 2 * i + 1; k < count; k = 2 * k + 1) { if (k + 1 < count && (array[k] as IComparable<T>).CompareTo(array[k + 1]) > 0) { k++; } if ((array[k] as IComparable<T>).CompareTo(temp) < 0) { Swap(array, i, k); i = k; } else { break; } } } } /// <summary> /// 交换元素 /// </summary> /// <typeparam name="T">返回类型</typeparam> /// <param name="array">堆</param> /// <param name="a">a元素</param> /// <param name="b">b元素</param> private static void Swap<T>(List<T> array,int a ,int b) { T temp = array[a]; array[a] = array[b]; array[b] = temp; }

2.对所需排序的对象实现IComparable接口，不用改变源代码，加一个继承与方法即可

public class T: MonoBehaviour,IComparable<T> { public int CompareTo(T other) { if(自定义判断条件) { return -1; } return 1; } }

3.使用排序，可获取返回值

xxx.HeapSort（List<T> list,true）;//需要大根堆就用true，小根堆就用false

Ex: 使用排序进行正态分布：

/// <summary> /// 进行正态分布排序,数组需要从小到大 /// </summary> /// <typeparam name="T"></typeparam> /// <param name="list"></param> /// <returns></returns> public static List<T> GaussianDistribution<T>(List<T> list) { HeapSort(list, true); T[] temp = new T[list.Count]; T[] array = list.ToArray(); for (int i = 0; i < list.Count; i++) { if (i % 2 == 0) { temp[i / 2] = array[i]; // 下标为偶数的顺序放到前边 } else { temp[list.Count - (i + 1) / 2] = array[i]; // 下标为奇数的从后往前放 } } list.Clear(); foreach (var v in temp) { list.Add(v); } return list; }

A*算法用到的排序工具类：SortTools.cs

using System.Collections; using System.Collections.Generic; using UnityEngine; /// <summary> /// 排序算法工具类 /// 2021.1.26：正态分布排序，堆排序，洗牌算法 /// Write By Alin /// </summary> namespace AlinTools{ public class SortTools { /// <summary> /// 进行正态分布排序,数组需要从小到大（可先用下方堆排序算法对列表进行排序） /// </summary> /// <typeparam name="T"></typeparam> /// <param name="list"></param> /// <returns></returns> public static List<T> GaussianDistribution<T>(List<T> list) { T[] temp = new T[list.Count]; T[] array = list.ToArray(); for (int i = 0; i < list.Count; i++) { if (i % 2 == 0) { temp[i / 2] = array[i]; // 下标为偶数的顺序放到前边 } else { temp[list.Count - (i + 1) / 2] = array[i]; // 下标为奇数的从后往前放 } } list.Clear(); foreach (var v in temp) { list.Add(v); } return list; } public static T[] GaussianDistribution<T>(T[] list) { T[] temp = new T[list.Length]; T[] array = list; for (int i = 0; i < list.Length; i++) { if (i % 2 == 0) { temp[i / 2] = array[i]; // 下标为偶数的顺序放到前边 } else { temp[list.Length - (i + 1) / 2] = array[i]; // 下标为奇数的从后往前放 } } return temp; } /// <summary> /// 堆排序 /// 对于非基础类型要对所需排序的对象实现IComparable接口 public class T : IComparable<T> { public int CompareTo(T other) { if (自定义判断条件) { return -1; } return 1; } } /// SortTools.HeapSort（List<T> list,true）;//需要大根堆就用true，小根堆就用false /// </summary> /// <typeparam name="T">返回类型</typeparam> /// <param name="type">需要排序的类型</param> /// <param name="isMaxHeap">是否大根堆</param> /// <returns></returns> public static List<T> HeapSort<T>(List<T> type, bool isMaxHeap) { for (int i = type.Count / 2 - 1; i >= 0; i--) { BuildHeap(type, i, type.Count, isMaxHeap); } for (int j = type.Count - 1; j > 0; j--) { Swap(type, 0, j); BuildHeap(type, 0, j, isMaxHeap); } return type; } private static void BuildHeap<T>(List<T> array, int i, int count, bool isMaxHeap) { if (isMaxHeap) { T temp = array[i]; for (int k = 2 * i + 1; k < count; k = 2 * k + 1) { if (k + 1 < count && (array[k] as System.IComparable<T>).CompareTo(array[k + 1]) < 0) { k++; } if ((array[k] as System.IComparable<T>).CompareTo(temp) > 0) { Swap(array, i, k); i = k; } else { break; } } } else { T temp = array[i]; for (int k = 2 * i + 1; k < count; k = 2 * k + 1) { if (k + 1 < count && (array[k] as System.IComparable<T>).CompareTo(array[k + 1]) > 0) { k++; } if ((array[k] as System.IComparable<T>).CompareTo(temp) < 0) { Swap(array, i, k); i = k; } else { break; } } } } /// <summary> /// 交换元素 /// </summary> /// <typeparam name="T">返回类型</typeparam> /// <param name="array">堆</param> /// <param name="a">a元素</param> /// <param name="b">b元素</param> private static void Swap<T>(List<T> array, int a, int b) { T temp = array[a]; array[a] = array[b]; array[b] = temp; } /// <summary> /// 洗牌算法 /// </summary> /// <typeparam name="T">泛型</typeparam> /// <param name="arr">泛型数组</param> public void RandomWash<T>(List<T> arr) { for (int i = 0; i < arr.Count; i++) { T temp = arr[i]; int randomID = UnityEngine.Random.Range(i, arr.Count); arr[i] = arr[randomID]; arr[randomID] = temp; } } public void RandomWash<T>(T[] arr) { for (int i = 0; i < arr.Length; i++) { T temp = arr[i]; int randomID = UnityEngine.Random.Range(i, arr.Length); arr[i] = arr[randomID]; arr[randomID] = temp; } } } }