算法笔记——左神初级（3）排序稳定性、桶排序

排序的稳定性

即在排序过程中，相同的值，它们的相对位置是否会被打乱。

例如：

具有排序稳定性：冒泡排序、插入排序、归并排序

不具有排序稳定性：选择排序、快速排序、堆排序

排序稳定性的价值：可以保留原始排序中的有用信息，例如几个人先按身高排序，然后再按年龄排序，第二次排完序后同年龄的人也是按身高排序的。

工程中的综合排序方法

如果数据很长：

1.首先做判断，如果数据都是int、long、char、float等基础类型，它会采用快排；

因为基础类型相同值无差异，

2.如果类型是自己定义的，如student，则会使用归并排序；

因为相同值得个体可能是不一样的，是有差别的，需要排序稳定性

如果数据很短：（数组长度小于60）

不管什么类型都使用插入排序！ 原因在于插排的常数项极低，虽然插排复杂度为O（N^2），但小样本情况下劣势体现不出来。

综上，工程中的综合排序是先用快排和归并分解，当分解的的区间小于60时，则用插排。

上面这个题可以理解为快排的类比。因为快排实际是做一个大小判断，奇偶也是做一个判断，而快排是无法保证排序稳定性的，除非去研究那个《01_stable_sort》论文 hhh

比较器

Java里对自定义类型的数据进行排序时，需要引入比较器

这里重写的方法需要返回值，如果return负数，则第一个数应在前面；如果正数，则第二个应在前面；return的是0，则两个一样大

public static class IdAscendingComparator implements Comparator<Student> {

		@Override
		public int compare(Student o1, Student o2) {
			return o1.id - o2.id;
		}

	}
           

Java里有专门的堆类型PriorityQueue——优先级队列 其实就是堆结构

在创建堆结构时，如果数据是自定义类型，需要添加一个比较器，也即是优先级队列的比较优先级的方法。

基本类型则按顺序。

PriorityQueue<Student> heap = new PriorityQueue<>(new IdAscendingComparator());

		heap.add(student3);
		heap.add(student2);
		heap.add(student1);

		while (!heap.isEmpty()){
			Student student = heap.poll();
			System.out.println("Name : " + student.name + ", Id : " 
			+ student.id + ", Age : " + student.age);
		}
	
	//基本类型
	PriorityQueue<Integer> heap = new PriorityQueue<>();

		heap.add(5);
		heap.add(7);
		heap.add(1);

		while (!heap.isEmpty()){
			System.out.println(heap.poll());
		}
           

桶排序

基础的桶排序算法过程

1.根据待排序集合中最大元素和最小元素的差值范围和映射规则，确定申请的桶个数；比如要对一组正整数排序，就可以申请最大值+1个桶。

2.遍历待排序集合，将每一个元素移动到对应的桶中；

3.更新桶的计数器或者别的相应记录。

4.从大到小或从小到大遍历桶，按计数或其他标志将桶内数据输出。

代码如下：（说实话这个方法感觉有点土啊，额外空间复杂度太大了！！！！）

// only for 0~200 value
public static void bucketSort(int[] arr) {
    //增加算法的完备性和效率
    if (arr == null || arr.length < 2) {
        return;
    }
    int max = Integer.MIN_VALUE; //比较前先设为最小值
    for (int i = 0; i < arr.length; i++) {  //遍历找到最大值
        max = Math.max(max, arr[i]);
    }
    int[] bucket = new int[max + 1]; //因为考虑正整数，所以需要max+1个桶
    
    for (int i = 0; i < arr.length; i++) { // 放数入桶的操作
        bucket[arr[i]]++;
    }

    int i = 0;
    for (int j = 0; j < bucket.length; j++) {  //按序遍历桶即可，桶的计数就是对应数字出现的次数
    	
        while (bucket[j]-- > 0) { //此while循环输出的是第j个桶存放的数字个j
            arr[i++] = j;
        }
    }
}
           

例题

桶排序思路：

1.有N个数，则准备N+1个桶；

2.遍历数组得到最小值和最大值；

3.如果最小值与最大值相等，则返回0；

4.最小值放在0号桶，最大值放在N号桶，把最小值到最大值的范围等分为N+1份，一个数属于哪个范围就放进去。

5.中间必存在一个空桶，空桶需要记录是否写入数和写入的最大最小值，其作用是排除相邻两数最大差值来源于同一个桶的可能性；

6.然后再比较所有给空桶之间的相邻两数差值，求得最大值。

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 = maxs[i];
			}
		}
		return res;
	}

	public static int bucket(long num, long len, long min, long max) {
		return (int) ((num - min) * len / (max - min));
	} //判断这个数该去几号桶