排序算法
常用的五种排序算法
- 插入排序
- 选择排序
- 快速排序
- 合并排序
- 桶排序
插入排序
Insertion Sort.
最直观的排序, 像抓牌, 在一堆乱序的牌中, 每抓一张就进行排序, 内层循环加一, 稳定的算法.
步进: 无序到有序的过程.
public void sort(int[] arr) {
// i 变量分隔有序, 无序集合, 从左开始
for (int i = 0; i < arr.length; i++) {
// 将 A[i] 插入到卡片0到卡片i之间
// i 指向下一个要排序的元素
int c = arr[i];
// j代表抓到的牌, 先放到最右侧, 不断插入到对应的位置
int j = i;
// 如果下一张牌c小于前一张牌, 就插入前一个位置
for (; j > 0 && arr[j - 1] > c; j--) {
// 前一张牌插到后一张牌的位置
arr[j] = arr[j - 1];
}
arr[j] = c;
}
}
选择排序
Selection Sort.
另外两个加1法的典型代表, 就是冒泡排序(bubble sort)和选择排序（selection sort). 这两个排序的循环不变式, 非常的相似. 和插入排序是一样的. 每次排序一个元素. 有序集合加1, 无序集合减1. 因此仍然需要一个循环变量i.
倒序, 挑出 0~i 之间的最大元素, 然后放在最右的 arr[i] 中, 然后i--. 外层循环.
i 就是无序和有序的分界点. 每次循环的时候. 找到0到i位置中最大值. 然后将它放入位置A[i].
public void sort(int[] arr) {
for (int i = arr.length - 1; i >= 0; i--) {
// 0 - arr[i] 找到最大值的索引, 然后进行交换
int j = maxIndex(arr, 0, i + 1);
Helper.swap(arr, i, j);
}
}
private int maxIndex(int[] arr, int i, int j) {
int max = Integer.MIN_VALUE;
// 这种写法是不稳定的
// int maxIndex = i;
// for (int k = 0; k < j; k++) {
// if (max < arr[k]) {
// max = arr[k];
// maxIndex = k;
// }
// }
int maxIndex = j;
for (int k = j; k >= j; k--) {
if (max < arr[k]) {
max = arr[k];
maxIndex = k;
}
}
return maxIndex;
}
序列2 2 1 1 用选择排序2 2相对顺序是否会发生变化? 如果发生变化, 就不是稳定排序. 选择排序是不稳定的, 顺序会反.
稳定排序: 同值顺序在排序过程中不会调换.
冒泡排序
Bubble Sort.
倒序, 选出最大元素, 不断比较交换相邻元素, 所以天生就是稳定的.
public void sort(int[] arr) {
for (int i = arr.length - 1; i >= 0; i--) {
// 找到 0-i 间的最大元素放在 arr[i](右边)
bubble(arr, 0, i + 1);
}
}
private void bubble(int[] arr, int i, int j) {
// 内循环不断比较交换
for (int k = 0; k < j - 1; k++) {
if (arr[k] > arr[k + 1]) {
Helper.swap(arr, k, k + 1);
}
}
}
冒泡排序, 写太多了, 这样性能不好.
分治策略
Divide And Conquer.
拆分思维. 先向下拆分再向上合并.
合并排序(Merge Sort)和快速排序(Quick Sort)都是基于这种模型的.
solve(A, l, r){
if(l - r==1) return;
mid = (l + r + 1) / 2;
solve(A, l, mid);
solve(A, mid, r);
merge(A, l, r);
}
分治策略不一定是平分成两半. 有可能是平分成三份, 或者四份；另外, 还有的分治策略算法并不需要合并.
快速排序
Quick Sort.
快速排序对问题的拆分具有一定的随机性；快速排序要求在原问题中任取一个元素. 将大于这个元素的值放在这个元素左边, 将小于这个元素的值放在元素右边, 这样就构成了两个子问题. 数学归纳法.
期望上x平分原问题. 空间复杂度度低.
public List<Integer> sort(List<Integer> list) {
return this.quickSort(list);
}
private List<Integer> quickSort(List<Integer> A) {
if (A.size() <= 1) {
return A;
}
// |---left---| x | ---right ---||
var x = A.get(0);
// 把比 x 小的都筛选出来
var left = A.stream().filter(tmp -> tmp < x).collect(Collectors.toList());
var mid = A.stream().filter(tmp -> tmp == x).collect(Collectors.toList());
var right = A.stream().filter(tmp -> tmp > x).collect(Collectors.toList());
left = quickSort(left);
right = quickSort(right);
left.addAll(mid);
left.addAll(right);
return left;
}
合并排序
Merge Sort. 使用递归实现, 递归的本质就是树.
public void sort(int[] arr) {
// 左闭右开
mergeSort(arr, 0, arr.length);
}
private void mergeSort(int[] arr, int l, int r) {
// stack overflow
if (r - l <= 1) return;
// 结果会向下取整, +1, 所以中间偏右的
int mid = (l + r + 1) / 2;
// 排好左边
mergeSort(arr, l, mid);
// 排好右边
mergeSort(arr, mid, r);
// 合并
merge(arr, l, mid, r);
}
private void merge(int[] arr, int l, int mid, int r) {
// 拷贝2份 mid + 1 是为了设置一个 MAX 值 作为哨兵, 减少边界条件的判断
int[] B = Arrays.copyOfRange(arr, l, mid + 1);
// copyOfRange 超出会自动补零
int[] C = Arrays.copyOfRange(arr, mid, r + 1);
// 设置哨兵 减少边界条件判断
B[B.length - 1] = C[C.length - 1] = Integer.MAX_VALUE;
// i 是 B 中下一个需要选择的值
// j 是 C 中下一个需要选择的值
int i = 0, j = 0;
for (int k = l; k < r; k++) {
if (B[i] < C[j]) {
arr[k] = B[i++];
} else {
arr[k] = C[j++];
}
}
}
桶排序
基于哈希函数(是一种映射).
排序100万个0~99之间的数字（有重复数字）。
设计100个桶, 每个桶对应. 不同值的数字. 第一个桶对应0, 第100个同对应99。
/**
* 通用桶排序
*
* @param A 要排序的数据
* @param k 桶的数目
* @param max 数据的最大值
* @param min 数据的最小值
* @return 排序后的数据
*/
public List<Integer> sort(List<Integer> A, int k, int max, int min) {
var buckets = new ArrayList<LinkedList<Integer>>();
var list = new ArrayList<Integer>();
var D = max - min + 1;
var quickSort = new QuickSort();
// 初始化桶
for (int i = 0; i < k; i++) {
buckets.add(new LinkedList<>());
}
// 放入桶中
for (var item : A) {
// 计算桶的位置
var key = (item - min) * k / D;
buckets.get(key).add(item);
}
// 从桶中取出值
for (int i = 0; i < k; i++) {
list.addAll(quickSort.sort(buckets.get(i)));
}
return list;
}
排序算法总结
- 加1/减1法
- 分治策略
- 哈希函数
