unity C# 常用算法 和 算法复杂度-阿里云开发者社区

开发者社区> 二哈卖豆腐> 正文

unity C# 常用算法 和 算法复杂度

简介: 1、稳定性 归并排序、冒泡排序、插入排序。基数排序是稳定的 选择排序、快速排序、希尔排序、堆排序是不稳定的 2、时间复杂度 最基础的四个算法:冒泡、选择、插入、快排中,快排的时间复杂度最小O(n*log2n),其他都是O(n2) 3.排序算法的思想: (1)冒泡排序: 是相邻元素之间的比较和交换,两重循环O(n2);所以,如果两个相邻元素相等,是不会交换的。
+关注继续查看

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;

}

}

}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
算法学习之路|用C++刷算法会用到的STL(二)——set
用C++刷算法会用到的STL(二)——set
2374 0
算法题-Count and Say
题目来自 LeetCode The count-and-say sequence is the sequence of integers with the first five terms as following: 1 11 21 1211 111221 1 is read off as “one 1” or 11.
876 0
冰与火之歌:「时间」与「空间」复杂度 | 算法必看系列三十六
对于一个算法,其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时,可能会使空间复杂度的性能变差,即可能导致占用较多的存储空间; 反之,求一个较好的空间复杂度时,可能会使时间复杂度的性能变差,即可能导致占用较长的运行时间。另外,算法的所有性能之间都存在着或多或少的相互影响。因此,当设计一个算法(特别是大型算法)时,要综合考虑算法的各项性能,算法的使用频率,算法处理的数据量的大小,算法描述语言的特性,算法运行的机器系统环境等各方面因素,才能够设计出比较好的算法。
2200 0
闰年的算法
关于平年、闰年的算法,大家比较耳熟的可能就是“四年一闰”的说法,但实际上这个说法是不准确的。看看天文学上关于平年闰年的规定就很清楚了: 天文学上,把地球绕太阳一周称为一年。但实际上,地球绕太阳转一圈需要365天5时48分46秒,也就是365.2422天,为了方便,一年定为365天,叫做平年;这样每过四年差不多就要多出一天来,把这一天加在2月里,这一年就有366天,叫做闰年。
1075 0
常用的消息摘要算法小总结
今天偶然的学习了一下几种关于消息摘要算法的知识。个人觉得很好。应着老话“好记性不如烂笔头”,我就码了几行代码咯。 算法嘛,没什么好说的了。毕竟是设计者智慧与汗水的结晶,也是时代进步的推动力。
971 0
68
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载