目的
程序 = 数据结构 + 算法
了解数据结构、算法思想、优缺点、合理运用到项目中， 常见算法：
时间复杂度：
O(1) -> HashMap
O(logn)-> 二叉树、二分法
O(n) -> for 循环
O(nlogn) -> for循环嵌套二叉树 、 Arrays.sort、快排
O(n2) -> for循环嵌套
…
时间复杂度由小 到大为：
O(1) < O(log2n) < O(n) < O(n log2n) <O(n2)<O(n3) …<O(2n)<O(n!)
一、算法之排序
1. 冒泡、选择、插入排序
时间复杂度： 冒泡 < 选择 < 插入
/**
* （量级过10W时非常慢）
* 冒泡排序（相邻数据比较）
*
* @param nums
*/
public static void bubbleSort(int[] nums) {
int length = nums.length;
for (int i = 0; i < nums.length; i++) {
for (int j = 1; j < length; j++) {
if (nums[j - 1] > nums[j]) {
int temp = nums[j - 1];
nums[j - 1] = nums[j];
nums[j] = temp;
}
}
}
}
/**
* 插入数据排序 （一轮可能会换多个） 从左到右再到左排序，再遍历... 一直到截止。
* <p>
* 核心： 指定节点（用插入节点与节点以前的数据进行排序）
*
* @param nums 集合
*/
public static void insertSort(int[] nums) {
int insertNode;
int j;
for (int i = 1; i < nums.length; i++) {
insertNode = nums[i];
j = i - 1;
while (j >= 0 && insertNode < nums[j]) {
nums[j + 1] = nums[j];
j--;
}
nums[j + 1] = insertNode;
}
}
/**
* 选择排序 (一轮只换一个）
* <p>
* 核心： 确定当前节点，然后索引++节点后面排序，然后替换。
*
* @param nums 集合
*/
public static void selectSort(int[] nums) {
for (int i = 0; i < nums.length; i++) {
int pos = i;
for (int j = i + 1; j < nums.length; j++) {
if (nums[pos] > nums[j]) {
pos = j;
}
}
if (pos != i) {
int temp = nums[i];
nums[i] = nums[pos];
nums[pos] = temp;
}
}
}
2.快速排序
- 速度快 （百万、千万数据很快） 有点类似二分查找中的双指针
public class QuickSort {
public static void main(String[] args) {
int[] nums = new int[1000000];
long start = System.currentTimeMillis();
for (int k = 0; k < 10; k++) {
for (int j = 0; j < nums.length; j++) {
nums[j] = (int) (Math.random() * 1000);
}
quickSort(nums);
}
System.out.println("quick sort cost ：" + (System.currentTimeMillis() - start));
}
public static void quickSort(int[] nums) {
if (nums == null || nums.length == 0) {
return;
}
qSort(nums, 0, nums.length - 1);
// for(int i =0;i<nums.length;i++) {
// System.out.println(nums[i]);
// }
}
private static void qSort(int[] nums, int start, int end) {
if (start >= end) {
return;
}
//获取第一个数据（排序区分左右两部分数据：左边小于，右边大于该数）
int pivot = nums[start];
int left = start;
int right = end;
while (left <= right) {
while (left <= right && nums[left] < pivot) {
left++;
}
while (left <= right && nums[right] > pivot) {
right--;
}
if (left <= right) {
int tmp = nums[right];
nums[right] = nums[left];
nums[left] = tmp;
left++;
right--;
}
}
//想象图形（移动过程） 递归左排、右排
qSort(nums, start, right);//为什么是right
qSort(nums, left, end);
}
}
3.合并排序
D&C 分而治之的思想，欧几里德算法（辗转相除法） 递归的思想
基线条件：数组为空或者只有一个元素时 （类似与初中时给函数并找规律）
实例：农场主分地问题 1680 X 640 --> 640 X 400 --> 240 X 400 --> 240 X 160 --> ..
将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
//合并排序
public class MergeSort {
public static void main(String[] args) {
int[] nums = new int[100000];
long start = System.currentTimeMillis();
for (int k = 0; k < 10; k++) {
for (int j = 0; j < nums.length; j++) {
nums[j] = (int) (Math.random() * 1000);
}
mergeSort(nums);
}
System.out.println("merge sort cost ：" + (System.currentTimeMillis() - start));
}
//merge Sort
public static void mergeSort(int[] nums) {
int[] temp = new int[nums.length];
mergeSortDetail(nums, 0, nums.length - 1, temp);
}
public static void mergeSortDetail(int[] nums, int start, int end, int[] temp) {
if (start >= end) {
return;
}
int mid = (start + end) / 2;
mergeSortDetail(nums, start, mid, temp);
mergeSortDetail(nums, mid + 1, end, temp);
//思考：递归到最小维度时；分治思想 （最底层是两个数字比较大小或单个数字；然后再想上合并排序！2 6 7 /3 4）
merge(nums, start, mid, end, temp);
}
public static void merge(int[] nums, int start, int mid, int end, int[] temp) {
int left = start;
int right = mid + 1;
int index = start;
while (left <= mid && right <= end) {
if (nums[left] < nums[right]) {
temp[index++] = nums[left++]; // temp[index] =nums[left]; index++; left++;
} else {
temp[index++] = nums[right++];
}
}
//左边单个
while (left <= mid) {
temp[index++] = nums[left++];
}
//右边单个
while (right <= end) {
temp[index++] = nums[right++];
}
//替换 （将有序集合重新插入nums集合中）
for (index = start; index <= end; index++) {
nums[index]= temp[index];
}
}
}
4.深度优先搜索
树（由上到下） —> 栈结构遍历
5.广度优先搜索
用图的查找算法，主要解决两类问题：
<1.从节点A出发，有前往节点B的路径吗？
<2.从节点A出发，前往节点B的哪条路径最短？（段数/边最少的路径）
实例：在人际圈中查找水果经销商 –你的人际圈（一度关系）、你朋友的人际圈（二度关系）、朋友的朋友的人际圈（三度关系）
6.狄克斯特拉
找出最快到达目的地的路径。（所用时间最少的路径）
区别广度优先搜索：找出段数最少的路径（尽量少转车而达到目的地的路径）
狄克斯特拉算法用于每条边都有关联数字的图，这些数字称为权重（weight）。
带权重的图称为加权图（weighted graph），不带权重的图称为非加权图（unweighted graph）。
**负权边** 时，该算法不使用，可采用[贝尔曼-福德算法（Bellman-Fordalgorithm）]
实例： 换钢琴
总结：
要计算非加权图中的最短路径，可使用广度优先搜索。
要计算加权图中的最短路径，可使用狄克斯特拉算法(只适应有向无环图)。
7.贪婪算法
选择每个最优，则全最优。（排课表、背包问题、集合覆盖问题、近似完全问题） 近似算法（NP完全问题）
这是一种近似最优的算法（背包问题：最多拿10千克重的物品，请选择价值最大的。 10kg 6000元的音响、4kg 5000元的笔记本电脑、6kg 2000元的手提琴，通过贪婪算法，结果会选出10kg 6000元的音响，而 后面两者之后大于6000元的音响的价值。）
8.动态规划
将问题分成各个小问题，先解决小问题，再逐步解决大问题。
（背包问题、最长公共子串）
9.K最近邻算法
1.创建推荐系统（特征抽取、回归<期望值>、挑选合适的特征)
2.机器学习（OCR<图像识别文字>、创建垃圾邮件过滤器<贝叶斯分类器>、股票市场预测<影响因数多>)
10.总结/扩展
1.二叉树
2.反向索引
3.傅里叶变换（分类、DNA分析、音乐识别）
4.并行计算
5.MapReduce
<1.分布式算法
<2.映射函数
<3.归并函数
6.布隆过滤器和HyperLogLog
7.SHA算法
8.局部敏感的散列算法
9.Diffie-Hellman密钥交换
10.线性规划
参考
«算法图解»
- ”程序员小灰“ 公众号 (推荐)
- 示例 ：https://gitee.com/xushj/algorithm.git