慕课网《算法与数据结构》 Java 代码，虽然讲师已经给出最佳代码，仍然自己写一遍，帮助记忆。 同时放在了自己的博客上
O(n²) 时间复杂度 虽然时间复杂度相对较高，但是同样也有好处
- 编码相对简单
- 在某些情况下，这些算法反而更有效
- 可以从简单的方法中衍生出复杂的算法
- 作为子过程，经过修改变为复杂的算法
重要的**：
逆序数：排序的过程就是消除逆序数的过程，所以逆序数的个数影响排序的性能(也可以从这个角度来思考排序的性能) - N个互异数的数组的平均逆序数是
$N(N-1)/4$ (数对的一半) - 通过交换相邻元素进行排序的任何算法平均都需要
$Ω(N^2)$ - 对于归并排序，归并过程中，可以一次消除多个逆序数，提高算法效率。
从未排序的数组中逐一选择最小的元素进行排序
KEY：寻找数组中最小的元素
大约需要
可以考虑对算法进行升级，不仅仅对整型进行排序，对浮点型甚至对对象进行排序（采用Comparable接口，然后通过compareto进行比较）
特点：
- 运行时间和输入无关(这样对于最开始就基本有序的数组就没有优势了)
- 数据移动最少
public class SelectionSort{
public static void SelectionSort(Comparable[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
int minindex = i;
//注意是从i+1开始的
for (int j = i + 1; j < n; j++) {
if(arr[j].compareTo(arr[minindxe]) < 0){
minindex = j;
}
}
swap(arr,minindex,i);
}
}
public static void swap(Object[] arr, int i, int j){
Object e = arr[i];
arr[i] = arr[j];
arr[j] = e;
}
}优化前，一次遍历仅仅可以找到最小的排好序，优化后，一次遍历可以找到最小的以及最大的两个元素排好序
选择排序优化
插入排序由N-1趟排序组成。对于p到N-1趟，插入排序保证从位置0到位置p上的元素为已排状态。
KEY:比前面一个小就进行交换，否则结束这一次插入(比选择排序优秀的地方，可以提前结束)
- 平均情况下，插入排序需要$\frac{N^2}{4}$次比较与$\frac{N^2}{4}$次交换
- 逆序数思考维度，每一次交换都是在减少一个逆序数，那么就需要逆序数次交换。
- 对插入排序进行优化：之前的插入排序每一次插入都要进行很多次交换，然而每次交换都是三次赋值的时间，所以很浪费时间，这样可以牺牲一个时间复杂度，将要插入的元素跟之前的元素进行比较，但是先不交换，等到找到要交换的元素，再进行一次交换，这样每一次插入都只进行一次交换。
插入排序为$O(n^2)$,如果输入数组时反序的时候，复杂度为$\Theta(N^2)$,如果输入已经预先排序，那么复杂度为$O(N^2)$。正因如此如果输入几乎被排序，那么插入排序将运行的更快。
它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
冒泡排序
- 希尔排序通过比较一定间隔的元素来工作，，各趟比较所用的距离随着算法的进行而减小，知道只比较相邻元素的最后一趟排序为止。
-
$h_k$ 排序的一般做法是，对于$h_k$，$h_{k+1}$，···$N-1$中的每一个位置i,把其上的元素放到i，$i-h_k$,$i-2h_k$,···中的正确位置上。
- 希尔排序的一个重要性质就是一个$h_k$排序的文件保持它的$h_k$排序性(我的理解就是，经过$h_k$排序后，逆序对不会再增加)
- 使用希尔增量时希尔排序的最坏情形运行时间为$\Theta(N^2)$
O(nlgn)复杂度的排序算法
分治算法的**(分而治之)
归并排序 重点在合(如何合)
快速排序 重点在分(如何分)
KEY：将两个有序的数组合并为一个有序的数组
牺牲了存储空间，获得了时间上的减少。
首先进行分层，然后对每一层使用归并排序
归并排序的逻辑 递归的**，这也是递归的一个很好的例子。对于递归的效率分析也是一个很好的技巧(叠缩求和与带入法)
优化：
- 对近乎有序的数组进行优化要判断要不要进行归并
- 由于对于小数据量的元素使用插入排序更加迅速， 所及可以考虑分层进行到一部分的时候改用插入排序(一部分是怎么确定的？)
不使用递归，只用迭代性能相对来说要差一点点
并没有使用到数组的特性(通过下标寻找元素)，所以对于链表很适用。
对于数组要思考到越界的问题
自底向上归并排序
key:如何将数组分为大小两个(Partition)
递归**，分别使用快速排序
围绕着枢纽元进行大小分离，不进行排序，只区分大小
性能测试 针对两种数组，快速排序的表现
- 对递归的理解很关键，通过运用归并排序的方法，使得求逆序数的复杂度变为
$O(nlogn$ )
求逆序数个数 归并排序 - 如果利用先排序再找到第n个最大值，那么这个算法的复杂度为$O(nlogn)$,但是利用快速排序的**可以很好的解决这个问题，使得复杂度变为$O(n)$
取出数组中第n大的元素 快速排序
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent