unity C# 常用算法 和 算法复杂度
1、稳定性
归并排序、冒泡排序、插入排序。基数排序是稳定的
选择排序、快速排序、希尔排序、堆排序是不稳定的
2、时间复杂度
最基础的四个算法：冒泡、选择、插入、快排中，快排的时间复杂度最小O(n*log2n)，其他都是O（n2）
3.排序算法的思想：
(1)冒泡排序：
是相邻元素之间的比较和交换，两重循环O(n2)；所以，如果两个相邻元素相等，是不会交换的。所以它是一种稳定的排序方法
public void PopSort(int[] list)
{
int i, j, temp; //先定义一下要用的变量
for (i = 0; i < list.Length - 1; i++)
{
for (j = i + 1; j < list.Length; j++)
{
if (list[i] > list[j]) //如果第二个小于第一个数
{
//交换两个数的位置，在这里你也可以单独写一个交换方法，在此调用就行了
temp = list[i]; //把大的数放在一个临时存储位置
list[i] = list[j]; //然后把小的数赋给前一个，保证每趟排序前面的最小
list[j] = temp; //然后把临时位置的那个大数赋给后一个
}
}
}
}
(2)选择排序：
每个元素都与第一个元素相比，产生交换，两重循环O(n2)；举个栗子，5 8 5 2 9，第一遍之后，2会与5交换，那么原序列中两个5的顺序就被破坏了。所以不是稳定的排序算法
///
/// 选择排序
///
public class SelectionSorter
{
// public enum comp {COMP_LESS,COMP_EQUAL,COMP_GRTR};
private int min;
// private int m=0;
public void Sort(int[] list)
{
for (int i = 0; i < list.Length - 1; ++i)
{
min = i;
for (int j = i + 1; j < list.Length; ++j)
{
if (list[j] < list[min])
min = j;
}
int t = list[min];
list[min] = list[i];
list[i] = t;
// Console.WriteLine("{0}",list[i]);
}
}
}
(3)插入排序：
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。刚开始这个小序列只包含第一个元素，事件复杂度O(n2)。比较是从这个小序列的末尾开始的。想要插入的元素和小序列的最大者开始比起，如果比它大则直接插在其后面，否则一直往前找它该插入的位置。如果遇见了一个和插入元素相等的，则把插入元素放在这个相等元素的后面。所以相等元素间的顺序没有改变，是稳定的。
///
/// 插入排序
///
public class InsertionSorter
{
public void Sort(int[] list)
{
for (int i = 1; i < list.Length; ++i)
{
int t = list[i];
int j = i;
while ((j > 0) && (list[j - 1] > t))
{
list[j] = list[j - 1];
--j;
}
list[j] = t;
}
}
}
