堆、桶排序、计数排序、基数排序
1、堆
堆排序流程
大根堆：
逻辑上为特殊的二叉树，根节点为最大的树
- 算法过程：
- 首先将待排序的数组构造成一个大根堆，此时，整个数组的最大值就是堆结构的顶端
- 将顶端的数与末尾的数交换，此时，末尾的数为最大值，剩余待排序数组个数为n-1
- 将剩余的n-1个数再构造成大根堆，再将顶端数与n-1位置的数交换，如此反复执行，便能得到有序数组
//堆排序
public static void heapSort(int[] arr) {
//构造大根堆
heapInsert(arr);
int size = arr.length;
while (size > 1) {
//固定最大值
swap(arr, 0, size - 1);
size--;
//构造大根堆
heapify(arr, 0, size);
}
}
//构造大根堆（通过新插入的数上升）
public static void heapInsert(int[] arr) {
for (int i = 0; i < arr.length; i++) {
//当前插入的索引
int currentIndex = i;
//父结点索引
int fatherIndex = (currentIndex - 1) / 2;
//如果当前插入的值大于其父结点的值,则交换值，并且将索引指向父结点
//然后继续和上面的父结点值比较，直到不大于父结点，则退出循环
while (arr[currentIndex] > arr[fatherIndex]) {
//交换当前结点与父结点的值
swap(arr, currentIndex, fatherIndex);
//将当前索引指向父索引
currentIndex = fatherIndex;
//重新计算当前索引的父索引
fatherIndex = (currentIndex - 1) / 2;
}
}
}
//将剩余的数构造成大根堆（通过顶端的数下降）
public static void heapify(int[] arr, int index, int size) {
int left = 2 * index + 1;
int right = 2 * index + 2;
while (left < size) {
int largestIndex;
//判断孩子中较大的值的索引（要确保右孩子在size范围之内）
if (arr[left] < arr[right] && right < size) {
largestIndex = right;
} else {
largestIndex = left;
}
//比较父结点的值与孩子中较大的值，并确定最大值的索引
if (arr[index] > arr[largestIndex]) {
largestIndex = index;
}
//如果父结点索引是最大值的索引，那已经是大根堆了，则退出循环
if (index == largestIndex) {
break;
}
//父结点不是最大值，与孩子中较大的值交换
swap(arr, largestIndex, index);
//将索引指向孩子中较大的值的索引
index = largestIndex;
//重新计算交换之后的孩子的索引
left = 2 * index + 1;
right = 2 * index + 2;
}
}
//交换数组中两个元素的值
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
堆排序的另一种代码实现
public class HeapSort{
//堆排序流程就是：构建大根堆，将大顶堆的顶和底交换，然后剩下的n-1个数继续前边的操作(后边的操作更多是一种寻找堆中最大值的操作)
public static void heapSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length; i++) {
heapInsert(arr, i);//构建大顶堆
}
int size = arr.length;
swap(arr, 0, --size);
while (size > 0) {
heapify(arr, 0, size);//后边的n-1次构建大根堆
swap(arr, 0, --size);//每次都要交换最大、最小值
}
}
public static void heapInsert(int[] arr, int index) {//堆或者是完全二叉树，这种结构有个显著的特点就是，总是先从左边的数开始排满的
while (arr[index] > arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;//不断地循环回去，直到顶的结点的时候，index为0，但是(index - 1) / 2也为0，所以循环到顶了就终止，构建堆或者完全二叉树这种结构的时候根本就不用考虑兄弟结点的，所以只考虑左结点就是对的
}
}
public static void heapify(int[] arr, int index, int size) {
int left = index * 2 + 1;
while (left < size) {
int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;//找出大值的索引，比较的是兄弟节点
largest = arr[largest] > arr[index] ? largest : index;//找出大值的索引，与父节点比较
if (largest == index) {//如果最大值的索引已经等于父索引，就不再继续循环了
break;
}
swap(arr, largest, index);
index = largest;
left = index * 2 + 1;
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void main(String[] args) {
int[] arr = {2,1,4,3,9,5,6};
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
}
堆题目1
已知一个几乎有序的数组。几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离一定不超过k， 并且k相对于数组长度来说是比较小的。
请选择一个合适的排序策略，对这个数组进行排序
建立小根堆，
将数组中前k+1个数放入小根堆，因为 0 位置上的数字，只可能在 0---k+1 的位置上，由此得到最小的数，将小根堆堆顶弹出，再将后面的数字依次放入，即可获得有序数列
每个数需要log k 的时间来调整，所以时间复杂度 N*Log k
2、比较器
PriorityQueue<Integer> heap = new PriorityQueue<>();
heap.add(3);
heap.add(1);
heap.add(4);
heap.add(6);
heap.add(2);
while (!heap.isEmpty()){
System.out.println(heap.poll());
}
//1 2 3 4 6 默认是小根堆
PriorityQueue<Integer> heap = new PriorityQueue<>();
heap.add(3);
heap.add(1);
heap.add(4);
heap.add(6);
heap.add(2);
while (!heap.isEmpty()){
System.out.println(heap.poll());
}
public static class MyComp implements Comparator<Integer>
{
@Override
public int compare(Integer o1,Integer o2)
{
return o2-o1;
}
}
// 大根堆, 从大到小排列
比较器：
public static class IdAscendingComparator implements Comparator<Student> {
@Override
public int compare(Student o1, Student o2) {
//return 负数;//表示o1应该放在前边
//return 正数;//表示o2应该放在前边
//return 0;//认为两个东西一样大
//if(o1.id < o2.id){
// return 负数;//表示o1应该放在前边
//}else if(o1.id > o2.id){
// return 正数;//表示o2应该放在前边
//}else {
// return 0;//表示一样大
//}//这几行代码和下边实现的功能是一样的
return o1.id - o2.id;
}
}
在堆结构或者红黑树当中如果需要使用排序的话，也可以使用比较器：
//在优先队列，也就是堆结构中，也可以使用比较器
PriorityQueue<Student> queue = new PriorityQueue<>(new IdComparactor());
queue.add(stu1);
queue.add(stu2);
queue.add(stu3);
while(!queue.isEmpty()){
Student student = queue.poll();
System.out.println("name:"+student.name+" , id:"+student.id+" ,age:"+student.age);
}
System.out.println("------------------------------");
//同样地，在红黑树中也可以使用比较器
TreeSet<Student> tree = new TreeSet<Student>(new IdComparactor());
tree.add(stu1);
tree.add(stu2);
tree.add(stu3);
while (!tree.isEmpty()){
Student student = tree.pollFirst();
System.out.println("name:"+student.name+" , id:"+student.id+" ,age:"+student.age);
}
进入堆之后的数据,再次进行修改,堆不能保证其有序性，也就是在构建堆之前就要整理好所有数据
java中底层排序
size 大于60时 使用 merge 和quick进行综合排序，如果小于60，系统默认使用插入排序以求最快速度完成。
自己定义的class类型排序时，会使用merge排序。
3 、 桶排序、计数排序、基数排序
- 非基于比较的排序，与被排序的样本的实际数据状况很有关系，所 以实际中并不经常使用
- 时间复杂度O(N)，额外空间复杂度O(N)
- 稳定的排序
时间复杂度、空间复杂度 均为O(N)，工程中不常用，但是笔试过程种可以使用这种办法来降低时间复杂度
对于给定的排序范围的数，进行排序。需要排序的数有n个。准备n+1个桶。
遍历每个数，将每个数装到对应的桶之后。再从第一个桶中取出，依次输出。
计数排序
每次统计当前数有多少个，然后给对应的元素位置中的数字+1，下次输出时按元素中的个数输出。
4. 补充问题（年年考）
给定一个数组，求如果排序之后，相邻两数的最大差值，要求时间复杂度O(N)且要求不能用非基于比较的排序
思路：
若是数组有N个数，则准备N+1个桶，然后找到数组中的最小值min与最大值max分别放入0号桶和N号桶，将min与max中间的值等分（N-1）份作为中间（N-1）个桶的范围；
由于一共N个数，有N+1和桶，故可以断定相邻数最大差值必定不在同一个桶内；
每个桶记录桶里的最大值与最小值，并给一个标志位flag来标记桶内是否有数值；
则可推断，相邻数最大差值必定为所有非空桶的最小值与前一非空桶的最大值的差值中的最大值。
假设原数组有9个元素，那么则设置9+1个桶，每个桶内装指定范围内的数。试想，因为只有9个数，但却有10个桶，所以必定有一个桶是空桶。
有空桶则说明这个序列的最大差值大于桶的跨度！
因此，最大差值不可能出现在同一个桶内，只可能出现在后一个桶的min-前一个桶的max
注：不一定隔着空桶的两个桶差值最大。
public class Code_11_MaxGap {
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);
//该桶的最小值与最大值发生更新，只有当该桶有数字时，才为true,将当前述与min、max进行对比，当该桶没有数字是，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 = maxs[i];
}
}
return res;
}
//确定当前数来自几号桶
public static int bucket(long num, long len, long min, long max) {
return (int) ((num - min) * len / (max - min));
}
// for test 对数器
public static int comparator(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}
Arrays.sort(nums);
int gap = Integer.MIN_VALUE;
for (int i = 1; i < nums.length; i++) {
gap = Math.max(nums[i] - nums[i - 1], gap);
}
return gap;
}
// for test
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}
return arr;
}
// for test
public static int[] copyArray(int[] arr) {
if (arr == null) {
return null;
}
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i] = arr[i];
}
return res;
}
// for test
public static void main(String[] args) {
int testTime = 500000;
int maxSize = 100;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
if (maxGap(arr1) != comparator(arr2)) {
succeed = false;
break;
}
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
}
}
参考1 ： https://blog.csdn.net/qq_43619459/article/details/108092246
总结
1)不基于比较的排序，对样本数据有严格要求，不易改写
2)基于比较的排序，只要规定好两个样本怎么比大小就可以直接复用
3)基于比较的排序，时间复杂度的极限是O(NlogN)
4)时间复杂度O(N*logN)、 额外空间复杂度低于O(N)、 且稳定的基于比较的
排序是不存在的。
5)为了绝对的速度选快排、为了省空间选堆排、为了稳定性选归并
a.归并排序的额外空间复杂度可以变成0(1);“归并排序内部缓存法”，但是将变得不再稳定。
b.“原地归并排序"是垃圾贴，会让时间复杂度变成O(N^2)
c. 快速排序稳定性改进，“01 stable sort"，但是会对样本数据要求更多。