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;

}

}

}