- 排序的比较器，返回负数表示第一个参数在前
- 稳定的有排序：插入、选择、冒泡、归并
- 综合排序的考虑点：基数小使用插入排序， 排基本数据用快排，包装数据用归并（稳定性）
1、荷兰国旗问题（快排的前导）
题意：把数组分成左边小于num，右边大于num，中间等于num，不需要有序
解法：
假设区间为[L , R] 维护一个左边小于区间，[L - less] ，维护一个右边大于区间 [more - R]， 设当前下标为cur，不断把arr[ cur ]交换到左区间或者右区间即可。
这里的while写的很巧妙，每次只针对cur进行判断，把后面的换过来之后，cur不动，下一轮会针对缓过来的数进行交换。
public int[] partition(int[] arr, int L, int R, int num) {
int less = L-1;
int more = R+1;
int cur = L;
while (cur < more) {
if (arr[cur] < num) {
swap(arr,++less,cur++);
}else if(arr[cur] > num){
swap(arr, --more, cur); // 遇到比num大的，丢到后面去，并且把后面的换到cur
// 假设后面的这个数仍然比num大，那么也再次进入这个分支
}else{
cur++;
}
}
return new int[]{less + 1, more - 1};
}
void swap(int[] arr, int l, int r) {
int temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
}
2、快排
package zcy;
import org.junit.Test;
public class Main {
void quickSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
quickSort(arr, 0, arr.length - 1);
}
void quickSort(int[] arr, int L, int R) {
if (L < R) {
// 随机打乱一下, 把num用arr[R]去替代
swap(arr,L + (int)(Math.random() * (R-L+1)),R);
int[] p = partition(arr, L, R);
quickSort(arr, L, p[0] - 1);
quickSort(arr, p[1] + 1, R);
}
}
public int[] partition(int[] arr, int L, int R) {
int less = L-1;
int more = R;
int cur = L;
while (cur < more) {
if (arr[cur] < arr[R]) {
swap(arr,++less,cur++);
}else if(arr[cur] > arr[R]){
swap(arr, --more, cur); // 遇到比num大的，丢到后面去，并且把后面的换到cur
// 假设后面的这个数仍然比num大，那么也再次进入这个分支
}else{
cur++;
}
}
// 此时的more 是用来比较的中间值， 需要放到排序后的恰当位置上
swap(arr,R,more);
// 把左区间的 后一个位置 和右区间的 前一个位置 的下标
// 一起返回
return new int[] { less + 1, more - 1 };
}
void swap(int[] arr, int l, int r) {
int temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
}
@Test
public void test() {
int[] arr = {3,1,4,1,4,2,1,3};
quickSort(arr);
for (int i:arr
) {
System.out.println(i);
}
}
public static void main(String[] args) {
}
}
写了个非递归版
void quickSortNotRecursion(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
Stack<Integer> stack = new Stack<>();
stack.push(0);
stack.push(arr.length - 1);
//int[] arr = {3,1,4,1,4,2,1,3};
while (!stack.empty()) {
int r = stack.peek();
stack.pop();
int l = stack.peek();
stack.pop();
System.out.println(l + " " + r);
if(l>=r)continue;
int[] p = partition(arr, l, r);
if (p[0] > l) {
stack.push(l);
stack.push(p[0]-1);
}
if (p[1] < r) {
stack.push(p[1]+1);
stack.push(r);
}
}
}
3、堆排序
以下针对大根堆
堆是一个完全二叉树的结构，每一个子树的根节点是该子树中的最大值。我们暂且用数组表示，但逻辑上是一个二叉树，可以通过下标找到父节点和子节点
子：2n+1 2n+2
父: (n-1)/2
3.1 必备的方法
- insert：向数组的末尾插入一个数，那么需和父节点比较，如果这个数大于父节点，那么交换位置。 并且不断地向上比较。
void heapInsert(int[] arr, int index) {
while (arr[index] > arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
- heapify：调整一棵树。 如果大根堆上的一个数变小了，为了保证根节点是树上的最大值，那么这个数需要下沉，找到一个位置，使得这个数在该子树上是最大值。
// 大根堆中，一个数变小了，那么就要向下沉
void heapify(int[] arr, int index, int heapSize) {
int left = index*2+1;
while (left < heapSize) {
int largst = left + 1 < heapSize && arr[left + 1] < arr[left] ?
left + 1 : left;
if (largst == heapSize) {
break;
}
swap(arr, index, largst);
index = largst;
left = index * 2 + 1;
}
}
- pop() ：取出堆顶元素。先把堆顶位置（0） 和 末尾位置（heapSize-1）的元素交换。 接着取出末尾位置（此时交换完毕，是最大值），并且heapSize – 。 然后调用heapify，进行下沉。
3.2 堆的应用
java提供了PriorityQueue<>堆
// 需要自己实现比较器
PriorityQueue<Student> heap = new PriorityQueue<>(new MyCompare());
3.2.1 堆排序
把一个数组做成大根堆，每次弹出堆顶（放到末尾），再调整堆成大根堆。 反反复复最后得到的就是有序的序列。
void heapSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 构造堆
for (int i = 0; i < arr.length; i++) {
heapInsert(arr,i);
}
// 此时形成堆，0位置是最大值
int heapSize = arr.length;
swap(arr,0,--heapSize);
while (heapSize > 0) {
heapify(arr, 0, heapSize);
swap(arr,0,--heapSize);
}
}
// 大根堆中，一个数变小了，那么就要向下沉
void heapify(int[] arr, int index, int heapSize) {
int left = index*2+1;
while (left < heapSize) {
int largst = left + 1 < heapSize && arr[left + 1] > arr[left] ?
left + 1 : left;
if (largst == heapSize) {
break;
}
swap(arr, index, largst);
index = largst;
left = index * 2 + 1;
}
}
void heapInsert(int[] arr, int index) {
while (arr[index] > arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
void swap(int[] arr, int l, int r) {
int temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
}
3.2.2 输出流的中位数
题意：
一个流不断的吐出数，吐出的过程会询问中位数的值。
解法：
维护大根堆，里面放的是吐出来偏小的数。
维护小根堆，里面是偏大的数。
每次询问就查询两个堆顶即可。
维护策略：
一个数如果比大根堆（里面是小的数）的堆顶小，那么insert到这个堆。另一个堆同理。
当两个堆的size相差>1 ，就把size大的堆的堆顶弹出，加入到另一个堆中。
4、综合排序
数据量长度<=60，使用插入排序，因为常数量小，而且n小，o(n^2)劣势体现不出来
基础类型(int,float)使用快排、自定义类型使用归并排序。处于稳定性角度考虑
5、比较器
public int compare(Student s1, Student s2){
// 如果返回负数 表示认为前面那个数 在前面 s1-s2
// 返回正数，则后面的s2 在前面
// 返回0 ，表示他俩一样大
}
6、 桶排序
时间复杂度o(n) ，空间复杂度o(n)。
相当于利用treeMap的排序，例如 6 3 2 则执行 int[] arr = new int[7] ; arr[6] ++;
6.1 拓展应用
给定一个序列，求排序后相邻两数间的最大值。要求时间复杂度o(n)
解法：
o(n)就要想到桶排序，这个解法桶排序变形，按照最大值和最小值的差，和数组个数n 进行划分桶（具体看bucket方法），n个数按bucket方法找到适合的桶，维护每个桶的最大值和最小值， 最后查找一下即可。
public static int maxGap(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}
int len = nums.length;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = 0; i < len; i++) {
min = Math.min(min, nums[i]);
max = Math.max(max, nums[i]);
}
if (min == max) {
return 0;
}
boolean[] hasNum = new boolean[len + 1];
int[] maxs = new int[len + 1];
int[] mins = new int[len + 1];
int bid = 0;
for (int i = 0; i < len; i++) {
bid = bucket(nums[i], len, min, max);
mins[bid] = hasNum[bid] ? Math.min(mins[bid], nums[i]) : nums[i];
maxs[bid] = hasNum[bid] ? Math.max(maxs[bid], nums[i]) : nums[i];
hasNum[bid] = true;
}
int res = 0;
int lastMax = maxs[0];
int i = 1;
for (; i <= len; i++) {
if (hasNum[i]) {
res = Math.max(res, mins[i] - lastMax);
// lastMax 很巧妙， 如果中间遇到空桶，那么保留的是上一个非空桶的最大值
lastMax = maxs[i];
}
}
return res;
}
// 8 9 7 31 2
// max 31 min 2 gap = 29
//14 -- 2 8 -- 1 , 31-2 == 29 / 5 大概相差6位，一个桶。
public static int bucket(long num, long len, long min, long max) {
//哪个数应该进几号桶
return (int) ((num - min) * len / (max - min));
}
版权声明：本文为qq_37591656原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。