记录下现在所流行的各种各样的排序，用于之后使用。暂时集成：插入排序，希尔排序，快排，堆排序，归并排序。
using System;
using System.Collections.Generic;
namespace Sort {
static public class Sort {
//插入排序
public delegate Q Condition<T,Q> (T t) where Q:IComparable;
static public void Insertion_Sort<T,Q> (T[] a,Condition<T,Q> condition) where Q:IComparable {
int i,j;
int n = a.Length;
for (i = 1;i < n;i++) {
T temp = a[i];
for (j = i;j > 0 && condition(temp).CompareTo(condition(a[j - 1])) < 0;--j)
a[j] = a[j - 1];
a[j] = temp;
}
}
static public void Insertion_Sort<T,Q> (List<T> a,Condition<T,Q> condition) where Q:IComparable {
int i,j;
int n = a.Count;
for (i = 1;i < n;i++) {
T temp = a[i];
for (j = i;j > 0 && condition(temp).CompareTo(condition(a[j - 1])) < 0;--j)
a[j] = a[j - 1];
a[j] = temp;
}
}
//希尔排序
public static void Shell_Sort<T,Q> (T[] arr,Condition<T,Q> condition) where Q:IComparable {//希尔排序 也是插入排序的一种
//增量gap，并逐步缩小增量 gap一般都是 /2/2这样操作
for (int gap = arr.Length / 2;gap > 0;gap /= 2) {
//从第gap个元素，逐个对其所在组进行直接插入排序操作
for (int i = gap;i < arr.Length;i++) {
int j = i;
T temp = arr[j];
if (condition(temp).CompareTo(condition(arr[j - 1])) < 0) {
while (j - gap >= 0 && condition(temp).CompareTo(condition(arr[j - 1])) < 0) {
//移动法
arr[j] = arr[j - gap];//向上挪移
j -= gap;
}
arr[j] = temp;
}
}
}
}
public static void Shell_Sort<T,Q> (List<T> arr,Condition<T,Q> condition) where Q:IComparable {//希尔排序 也是插入排序的一种
//增量gap，并逐步缩小增量 gap一般都是 /2/2这样操作
for (int gap = arr.Count / 2;gap > 0;gap /= 2) {
//从第gap个元素，逐个对其所在组进行直接插入排序操作
for (int i = gap;i < arr.Count;i++) {
int j = i;
T temp = arr[j];
if (condition(temp).CompareTo(condition(arr[j - 1])) < 0) {
while (j - gap >= 0 && condition(temp).CompareTo(condition(arr[j - 1])) < 0) {
//移动法
arr[j] = arr[j - gap];//向上挪移
j -= gap;
}
arr[j] = temp;
}
}
}
}
//快排
public static void Quick_Sort<T,Q> (T[] arr,Condition<T,Q> condition) where Q:IComparable {
if (arr != null && arr.Length != 0) {
QuickSort<T,Q>(arr,condition,0,arr.Length - 1);
}
}
static void QuickSort<T,Q> (T[] arr,Condition<T,Q> condition,int left,int right) where Q:IComparable {//快速排序 确定一个key,然后两个指针和key进行比较，如果左指针小于key 左就++，如果右指针大于key 右指针就--，直到两者停下然后交换。
if (left >= right) {
return;
}
int begin = left;
int end = right;
int key = right;
while (left < right) {
while (left < right && condition(arr[left]).CompareTo(condition(arr[key])) <= 0)
left++;
while (left < right && condition(arr[right]).CompareTo(condition(arr[key])) >= 0)
right--;
if (left < right && condition(arr[left]).CompareTo(condition(arr[key])) != 0)
swap(ref arr[left],ref arr[right]);
}
if (condition(arr[left]).CompareTo(condition(arr[key])) != 0)
swap(ref arr[left],ref arr[key]);
QuickSort(arr,condition,begin,left - 1);
QuickSort(arr,condition,left + 1,end);
}
public static void Quick_Sort<T,Q> (List<T> arr,Condition<T,Q> condition) where Q:IComparable {
if (arr != null && arr.Count != 0) {
QuickSort<T,Q>(arr,condition,0,arr.Count - 1);
}
}
static void QuickSort<T,Q> (List<T> arr,Condition<T,Q> condition,int left,int right) where Q:IComparable {//快速排序 确定一个key,然后两个指针和key进行比较，如果左指针小于key 左就++，如果右指针大于key 右指针就--，直到两者停下然后交换。
if (left >= right) {
return;
}
int begin = left;
int end = right;
int key = right;
while (left < right) {
while (left < right && condition(arr[left]).CompareTo(condition(arr[key])) <= 0)
left++;
while (left < right && condition(arr[right]).CompareTo(condition(arr[key])) >= 0)
right--;
if (left < right && condition(arr[left]).CompareTo(condition(arr[key])) != 0)
swap(arr,left,right);
}
if (condition(arr[left]).CompareTo(condition(arr[key])) != 0)
swap(arr,left,key);
QuickSort(arr,condition,begin,left - 1);
QuickSort(arr,condition,left + 1,end);
}
//堆排序
static private void heapSort<T,Q> (T[] a,Condition<T,Q> condition,int n,int k) where Q:IComparable {//堆排序
int k1 = 2 * k + 1;//左边
int k2 = 2 * k + 2;//右边
if (k1 >= n && k2 >= n)
return;
T a1;
T a2;
T a3;
if (k2 < n) {
a1 = a[k1];
a2 = a[k2];
a3 = a[k];
if (condition(a3).CompareTo(condition(a1)) < 0 && condition(a3).CompareTo(condition(a2)) < 0)
return;
if (condition(a1).CompareTo(condition(a2)) < 0) {
swap<T>(ref a[k1],ref a[k]);
heapSort(a,condition,n,k1);
} else {
swap<T>(ref a[k2],ref a[k]);
heapSort(a,condition,n,k2);
}
} else {
a1 = a[k1];
a3 = a[k];
if (condition(a3).CompareTo(condition(a1)) < 0)
return;
if (condition(a1).CompareTo(condition(a3)) < 0) {
swap<T>(ref a[k1],ref a[k]);
heapSort(a,condition,n,k1);
}
}
}
static public void Heap_Sort<T,Q> (T[] a,Condition<T,Q> condition) where Q:IComparable {//堆排序
for (int i = (a.Length - 1) / 2;i >= 0;i--)
heapSort<T,Q>(a,condition,a.Length,i);
int n = a.Length;
List<T> aa = new List<T>();
while (a.Length > 0 && condition(a[0]).CompareTo(condition(a[n - 1])) != 0) {
aa.Add(a[0]);
a[0] = a[n - 1];
n--;
heapSort(a,condition,n,0);
}
aa.Add(a[0]);
for (int i = 0;i < aa.Count;i++) {
a[i] = aa[i];
}
}
static private void heapSort<T,Q> (List<T> a,Condition<T,Q> condition,int n,int k) where Q:IComparable {//堆排序
int k1 = 2 * k + 1;//左边
int k2 = 2 * k + 2;//右边
if (k1 >= n && k2 >= n)
return;
T a1;
T a2;
T a3;
if (k2 < n) {
a1 = a[k1];
a2 = a[k2];
a3 = a[k];
if (condition(a3).CompareTo(condition(a1)) < 0 && condition(a3).CompareTo(condition(a2)) < 0)
return;
if (condition(a1).CompareTo(condition(a2)) < 0) {
swap<T>(a,k1,k);
heapSort(a,condition,n,k1);
} else {
swap<T>(a,k2,k);
heapSort(a,condition,n,k2);
}
} else {
a1 = a[k1];
a3 = a[k];
if (condition(a3).CompareTo(condition(a1)) < 0)
return;
if (condition(a1).CompareTo(condition(a3)) < 0) {
swap<T>(a,k1,k);
heapSort(a,condition,n,k1);
}
}
}
static public void Heap_Sort<T,Q> (List<T> a,Condition<T,Q> condition) where Q:IComparable {//堆排序
for (int i = (a.Count - 1) / 2;i >= 0;i--)
heapSort<T,Q>(a,condition,a.Count,i);
int n = a.Count;
List<T> aa = new List<T>();
while (a.Count > 0 && condition(a[0]).CompareTo(condition(a[n - 1])) != 0) {
aa.Add(a[0]);
a[0] = a[n - 1];
n--;
heapSort(a,condition,n,0);
}
aa.Add(a[0]);
for (int i = 0;i < aa.Count;i++) {
a[i] = aa[i];
}
}
//归并排序
public static void Merge_Sort<T,Q> (T[] arr,Condition<T,Q> condition) where Q:IComparable {
T[] temp = new T[arr.Length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
mergeSort<T,Q>(arr,condition,0,arr.Length - 1,temp);
}
private static void mergeSort<T,Q> (T[] arr,Condition<T,Q> condition,int left,int right,T[] temp) where Q:IComparable {
if (left < right) {
int mid = (left + right) / 2;
mergeSort<T,Q>(arr,condition,left,mid,temp);//左边归并排序，使得左子序列有序
mergeSort<T,Q>(arr,condition,mid + 1,right,temp);//右边归并排序，使得右子序列有序
merge<T,Q>(arr,condition,left,mid,right,temp);//将两个有序子数组合并操作
}
}
private static void merge<T,Q> (T[] arr,Condition<T,Q> condition,int left,int mid,int right,T[] temp) where Q:IComparable {
int i = left;//左序列指针
int j = mid + 1;//右序列指针
int t = 0;//临时数组指针
while (i <= mid && j <= right) {
if (condition(arr[i]).CompareTo(condition(arr[j])) < 0) {
temp[t++] = arr[i++];
} else {
temp[t++] = arr[j++];
}
}
while (i <= mid) {//将左边剩余元素填充进temp中
temp[t++] = arr[i++];
}
while (j <= right) {//将右序列剩余元素填充进temp中
temp[t++] = arr[j++];
}
t = 0;
//将temp中的元素全部拷贝到原数组中
while (left <= right) {
arr[left++] = temp[t++];
}
}
public static void Merge_Sort<T,Q> (List<T> arr,Condition<T,Q> condition) where Q:IComparable {
T[] temp = new T[arr.Count];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
mergeSort<T,Q>(arr,condition,0,arr.Count - 1,temp);
}
private static void mergeSort<T,Q> (List<T> arr,Condition<T,Q> condition,int left,int right,T[] temp) where Q:IComparable {
if (left < right) {
int mid = (left + right) / 2;
mergeSort<T,Q>(arr,condition,left,mid,temp);//左边归并排序，使得左子序列有序
mergeSort<T,Q>(arr,condition,mid + 1,right,temp);//右边归并排序，使得右子序列有序
merge<T,Q>(arr,condition,left,mid,right,temp);//将两个有序子数组合并操作
}
}
private static void merge<T,Q> (List<T> arr,Condition<T,Q> condition,int left,int mid,int right,T[] temp) where Q:IComparable {
int i = left;//左序列指针
int j = mid + 1;//右序列指针
int t = 0;//临时数组指针
while (i <= mid && j <= right) {
if (condition(arr[i]).CompareTo(condition(arr[j])) < 0) {
temp[t++] = arr[i++];
} else {
temp[t++] = arr[j++];
}
}
while (i <= mid) {//将左边剩余元素填充进temp中
temp[t++] = arr[i++];
}
while (j <= right) {//将右序列剩余元素填充进temp中
temp[t++] = arr[j++];
}
t = 0;
//将temp中的元素全部拷贝到原数组中
while (left <= right) {
arr[left++] = temp[t++];
}
}
static void swap<T> (List<T> a,int n,int m) {
T t;
t = a[n];
a[n] = a[m];
a[m] = t;
}
static void swap<T> (ref T a,ref T b) {
T t;
t = b;
b = a;
a = t;
}
}
}
将他做成一个DLL之后，以后就是我们的人啦，
调用方法：
struct TextSort {
public TextSort(string name, int id) {
this.name = name;
this.id = id;
}
string name;
int id;
public int returnID() {
return id;
}
}
List<TextSort> sortList;
void Start() {
sortList = new List<TextSort>();
sortList.Add(new TextSort("name1", 4));
sortList.Add(new TextSort("name2", 5));
sortList.Add(new TextSort("name3", 1));
sortList.Add(new TextSort("name3", 2));
Sort.Sort.Insertion_Sort<TextSort, int>(sortList, (a)=>{
return a.returnID();
});
foreach (var sortObject in sortList) {
Debug.Log(sortObject.returnID());
}
}
成果
网友评论