大学里程序员必须掌握的核心算法

网上有关“大学里程序员必须掌握的核心算法
”话题很是火热
，小编也是针对大学里程序员必须掌握的核心算法寻找了一些与之相关的一些信息进行分析，如果能碰巧解决你现在面临的问题 ，希望能够帮助到您
。

程序员必须掌握的核心算法

十大排序算法

简单排序插入排序、

选择排序 、冒泡排序(必学)

分治排序:快速排序
、归并排序(必学
，快速排序还要关注中轴的选取方式)

分配排序桶排序、基数排序

树状排序:堆排序(必学)

其他:计数排序(必学) 、希尔排序

图论算法

图的表示:邻接矩阵和邻接表

遍历算法:深度搜索和广度搜索(必学)

最短路径算法:FLOYD,DIJKSTRA(必学)

最小生成树算法:PRIM，KRUSKAL(必学)

实际算法:关键路径
、拓抖排序(原理与应用)

二分图匹配:配对、匈牙利算法(原理与应用)

拓展:中心性算法 、社区发现算法(原理与应用）

搜索与回溯算法

贪心算法(必学)

信发式搜索算法:A*寻路算法(了解)

地图着色算法
、N皇后问题、最优加工顺序旅行商问题

动态规划

树形DP:01背包问题

线性DP:最长公共千序列 、最长公共子串

区间DP:矩阵最大值(和以及积)

数位DP:数字游戏

状态压缩DP:旅行商

字符匹配算法

正则表达式

模式匹配:KMP
、BOYER-MOORE

流相关算法

最大流:最短增广路、DINIC算法

最大流最小割:最大收盆问题 、方格取数问题

最小费用最大流:最小费用路、消遣

java十大算法

排序的算法有很多 ，对空间的要求及其时间效率也不尽相同。下面列出了一些常见的排序算法 。这里面插入排序和冒泡排序又被称作简单排序
，他们对空间的要求不高，但是时间效率却不稳定；而后面三种排序相对于简单排序对空间的要求稍高一点 ，但时间效率却能稳定在很高的水平
。基数排序是针对关键字在一个较小范围内的排序算法。

插入排序

冒泡排序

选择排序

快速排序

堆排序

归并排序

基数排序

希尔排序 插入排序是这样实现的：

1
、首先新建一个空列表
，用于保存已排序的有序数列（我们称之为有序列表） 。

2、从原数列中取出一个数，将其插入有序列表中 ，使其仍旧保持有序状态
。

3 、重复2号步骤
，直至原数列为空。

插入排序的平均时间复杂度为平方级的，效率不高 ，但是容易实现 。它借助了逐步扩大成果的思想，使有序列表的长度逐渐增加
，直至其长度等于原列表的长度
。

插入排序的基本思想是在遍历数组的过程中，假设在序号 i 之前的元素即 [0..i-1] 都已经排好序 ，本趟需要找到 i 对应的元素 x 的正确位置 k 
，并且在寻找这个位置 k 的过程中逐个将比较过的元素往后移一位，为元素 x “腾位置” ，最后将 k 对应的元素值赋为 x 
，一般情况下，插入排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1)。 冒泡排序是这样实现的：

1
、从列表的第一个数字到倒数第二个数字 ，逐个检查：若某一位上的数字大于他的下一位
，则将它与它的下一位交换 。

2、重复1号步骤，直至再也不能交换
。

冒泡排序的平均时间复杂度与插入排序相同 ，也是平方级的
，但冒泡排序是原地排序的，也就是说它不需要额外的存储空间。 选择排序是这样实现的：

1 、设数组内存放了n个待排数字 ，数组下标从1开始，到n结束 。

2
、初始化i=1

3、从数组的第i个元素开始到第n个元素
，寻找最小的元素。

4 、将上一步找到的最小元素和第i位元素交换
。

5
、i++,直到i=n－1算法结束，否则回到第3步

选择排序的平均时间复杂度也是O(n^2)的。

举例：

564

比如说这个 ，我想让它从小到大排序
，怎么做呢？

第一步：从第一位开始找最小的元素，564中4最小 ，与第一位交换 。结果为465

第二步：从第二位开始找最小的元素
，465中5最小，与第二位交换
。结果为456

第三步：i=2 ，n=3
，此时i=n-1，算法结束

完成 平均时间复杂度

插入排序 O(n^2）

冒泡排序 O(n^2）

选择排序 O(n^2）

快速排序 O(n log n)

堆排序 O(n log n)

归并排序 O(n log n)

基数排序 O(n)

希尔排序 O(n^1.25）

算法一：快速排序算法

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下 ，排序 n 个项目要Ο(n log n)次比较 。在最坏状况下则需要Ο(n2)次比较
，但这种状况并不常见
。事实上，快速排序通常明显比其他Ο(n log n) 算法更快 ，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists） 。

算法步骤：

1 从数列中挑出一个元素，称为 "基准"（pivot）
，

2 重新排序数列，所有元素比基准值小的摆放在基准前面 ，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）
。在这个分区退出之后
，该基准就处于数列的中间位置。这个称为分区（partition）操作 。

3 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序
。

递归的最底部情形，是数列的大小是零或一 ，也就是永远都已经被排序好了。虽然一直递归下去
，但是这个算法总会退出，因为在每次的迭代（iteration）中 ，它至少会把一个元素摆到它最后的位置去 。

算法二：堆排序算法

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构
，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点
。

堆排序的平均时间复杂度为Ο(nlogn) 。

算法步骤：

创建一个堆H[0..n-1]

把堆首（最大值）和堆尾互换

3. 把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置

4. 重复步骤2 ，直到堆的尺寸为1

算法三：归并排序

归并排序（Merge sort
，台湾译作：合并排序）是建立在归并操作上的一种有效的排序算法 。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用
。

算法步骤：

1. 申请空间，使其大小为两个已经排序序列之和 ，该空间用来存放合并后的序列

2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置

3. 比较两个指针所指向的元素
，选择相对小的元素放入到合并空间，并移动指针到下一位置

4. 重复步骤3直到某一指针达到序列尾

5. 将另一序列剩下的所有元素

关于“大学里程序员必须掌握的核心算法 ”这个话题的介绍 ，今天小编就给大家分享完了
，如果对你有所帮助请保持对本站的关注！