|
|
# 算法的5个特点
|
|
|
|
|
|
1.有穷性
|
|
|
2.确定性(确定的执行流程或者确定的尝试流程)
|
|
|
3.可行性
|
|
|
4.输入
|
|
|
5.输出
|
|
|
|
|
|
# 选择排序
|
|
|
|
|
|
双层循环，内层循环完成后获取最小值，内层循环每次将最小值放到i位置。
|
|
|
0-i之间认为是有序，i-n之间是原始数据，从i-n之间选择最小的元素放到index为i的地方。
|
|
|
|
|
|
不稳定的排序
|
|
|
|
|
|
```Java
|
|
|
private static void selectionSort(int[] arr) {
|
|
|
if (arr == null || arr.length < 2) {
|
|
|
return;
|
|
|
}
|
|
|
|
|
|
int length = arr.length;
|
|
|
int tmp;
|
|
|
for (int i = 0; i < length; i++) {
|
|
|
int index = i;
|
|
|
for (int j = i; j < length; j++) {
|
|
|
// 小于号避免位置交换
|
|
|
index = arr[j] < arr[index] ? j : index;
|
|
|
}
|
|
|
if (index == i) {
|
|
|
continue;
|
|
|
}
|
|
|
tmp = arr[i];
|
|
|
arr[i] = arr[index];
|
|
|
arr[index] = tmp;
|
|
|
}
|
|
|
}
|
|
|
```
|
|
|
|
|
|
# 冒泡排序
|
|
|
|
|
|
双层循环，内层循环两两交换，内层循环完成后将最大值冒泡到最右边。
|
|
|
外层循环index从大到小，内层循环index从小到大。
|
|
|
|
|
|
稳定排序
|
|
|
|
|
|
```Java
|
|
|
private static void bubbleSort(int[] arr){
|
|
|
int length = arr.length;
|
|
|
if (arr == null || length < 2) {
|
|
|
return;
|
|
|
}
|
|
|
|
|
|
int tmp;
|
|
|
for (int i = length - 1; i >= 0; i--) {
|
|
|
for (int j = 0; j < i; j++) {
|
|
|
if (arr[j + 1] < arr[j]) {
|
|
|
tmp = arr[j];
|
|
|
arr[j] = arr[j + 1];
|
|
|
arr[j + 1] = tmp;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
```
|
|
|
|
|
|
# 插入排序
|
|
|
|
|
|
每次获取原始数据最前面的那个元素交换到左侧已经有序的数组。
|
|
|
双层循环，外层循环每次递增并获取i，内层循环使用i挨个和0-1的数据比较并交换。如果i比i-1大或者内层循环到了最左侧则终止循环。
|
|
|
|
|
|
稳定排序
|
|
|
|
|
|
```Java
|
|
|
private static void insertSort(int[] arr){
|
|
|
int length = arr.length;
|
|
|
if (arr == null || length < 2) {
|
|
|
return;
|
|
|
}
|
|
|
int tmp;
|
|
|
for (int i = 0; i < length; i++) {
|
|
|
for (int j = i; j > 0; j--) {
|
|
|
if (arr[j - 1] > arr[j]) {
|
|
|
tmp = arr[j - 1];
|
|
|
arr[j - 1] = arr[j];
|
|
|
arr[j] = tmp;
|
|
|
} else {
|
|
|
break;
|
|
|
}
|
|
|
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
```
|
|
|
|
|
|
不基于比较的排序，也叫桶排序。对数据样本有要求，但是特定场景可以做到O(N)时间复杂度，基于比较的排序最好能做到O(N*logN)
|
|
|
计数排序 需要指定上下限
|
|
|
基数排序 非负、能用十进制理解的样本
|
|
|
|
|
|
排序的稳定性
|
|
|
稳定排序 冒泡、插入、归并
|
|
|
不稳定排序 选择、快排、堆排序、希尔
|
|
|
|
|
|
|序号|名称 |时间复杂度 |额外空间复杂度|稳定性|
|
|
|
|:----- |:----- |:-----|:-----|:-----|:-----| :-----| ----: | :----: |
|
|
|
|1|选择排序 |O(N^2^) |O(1) |无|
|
|
|
|2|冒泡排序 |O(N^2^) |O(1) |有|
|
|
|
|3|插入排序 |O(N^2^) |O(1) |有|
|
|
|
|4|归并排序 |O(N$\times$ $\log$N) |O(N) |有|
|
|
|
|5|随机快排 |O(N$\times$ $\log$N) |O($\log$N) |无|
|
|
|
|6|堆排序 |O(N$\times$ $\log$N) |O(1) |无|
|
|
|
|7|计数排序 |O(N) |O(M) |有|
|
|
|
|8|基数排序 |O(N) |O(N) |有|
|
|
|
|9|希尔排序 | | ||
|
|
|
|
|
|
* 不基于比较的排序，对样本数据有严格要求，不容易改写
|
|
|
* 基于比较的排序，只要规定好两个样本怎么比较大小就可以直接复用
|
|
|
* 基于比较的排序，时间复杂度的极限是O(N$\times$ $\log$N)
|
|
|
* 时间复杂度O(N$\times$ $\log$N)、额外空间复杂度低于O(N)、且稳定的基于比较的排序是不存在的
|
|
|
* 为了绝对的速度选择快排、为了省空间选堆排序、为了稳定性选归并
|
|
|
|
|
|
工程上的改进
|
|
|
|
|
|
* 考虑稳定性，Arrays.sort，基础类型使用快排，有比较器使用归并排序。
|
|
|
* 充分利用O(N$\times$ $\log$N)和O(N^2^)排序各自的优势，O(N^2^)排序的常数项小，在数据样本不大(比如小于60)的时候是比O(N$\times$ $\log$N)要快的。
|
|
|
|
|
|
单链表回文
|
|
|
L1、L2、L3、L4、L5、L6、L7、R1、R2、R3、R4、R5、R6、R7变成L1、R7、L2、R6、L3、R5、L4、R4、L5、R3、L6、R2、L7、R1
|
|
|
|
|
|
单链表找中间节点
|
|
|
单链表荷兰国旗问题
|
|
|
给定表头，将节点数据按照小于、等于、大于K连接
|
