排序的穩定性
即在排序過程中，相同的值，它們的相對位置是否會被打亂。
例如：
具有排序穩定性：冒泡排序、插入排序、歸并排序
不具有排序穩定性：選擇排序、快速排序、堆排序
排序穩定性的價值：可以保留原始排序中的有用資訊，例如幾個人先按身高排序，然後再按年齡排序，第二次排完序後同年齡的人也是按身高排序的。
工程中的綜合排序方法
如果資料很長：
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));
} //判斷這個數該去幾号桶