主要讨论：荷兰国旗问题、随机快速排序、堆排序、稳定性、比较器、桶排序、相邻两数的最大差值问题和简单介绍工程中的综合排序算法
题目一
给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。
要求额外空间复杂度O(1)，时间复杂度O(N)
参考下面的代码即可
问题二（荷兰国旗问题）
给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。
要求额外空间复杂度O(1)，时间复杂度O(N)
public static int[] partition(int[] arr, int l, int r, int p) { int less = l - 1; int more = r + 1; while (l < more) { if (arr[l] < p) { swap(arr, ++less, l++); } else if (arr[l] > p) { swap(arr, --more, l); } else { l++; } } return new int[] { less + 1, more - 1 }; } // for test public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }
题目二
随机快速排序的细节和复杂度分析
可以用荷兰国旗问题来改进快速排序
时间复杂度O(N*logN)，额外空间复杂度O(logN)
public static void quickSort(int[] arr) { if (arr == null || arr.length < 2) { return; } quickSort(arr, 0, arr.length - 1); } public static void quickSort(int[] arr, int l, int r) { if (l < 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 static int[] partition(int[] arr, int l, int r) { int less = l - 1; int more = r; while (l < more) { if (arr[l] < arr[r]) { swap(arr, ++less, l++); } else if (arr[l] > arr[r]) { swap(arr, --more, l); } else { l++; } } swap(arr, more, r); return new int[] { less + 1, more }; } public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }
题目三
堆排序的细节和复杂度分析
时间复杂度O(N*logN)，额外空间复杂度O(1)
堆结构非常重要
1，堆结构的heapInsert与heapify
2，堆结构的增大和减少
3，如果只是建立堆的过程，时间复杂度为O(N)
4，优先级队列结构，就是堆结构
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); 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; } } 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; }
题目四
排序算法的稳定性及其汇总
冒泡、插入、归并稳定。
选择、快速、堆排序不稳定。
稳定性的含义？
值相等的情况下，相对次序得到保持。
为什么要稳定性？
由现实的例子决定，例如默认序列是按照身高排序的，再按照年龄排序的时候，希望可以保留原始身高的信息，再进行年龄排序。
题目五
有关排序问题的补充：
1，归并排序的额外空间复杂度可以变成O(1)，但是非常难，不需要掌握，可以搜“归并排序 内部缓存法”
2，快速排序可以做到稳定性问题，但是非常难，不需要掌握，可以搜“01 stable sort”
3，有一道题目，是奇数放在数组左边，偶数放在数组右边，还要求原始的相对次序不变，碰到这个问题，可以怼面试官。面试官非良人。
题目六
认识比较器的使用
1 public class Code_09_Comparator { 2 3 public static class Student { 4 public String name; 5 public int id; 6 public int age; 7 8 public Student(String name, int id, int age) { 9 this.name = name; 10 this.id = id; 11 this.age = age; 12 } 13 } 14 15 public static class IdAscendingComparator implements Comparator<Student> { 16 17 @Override 18 public int compare(Student o1, Student o2) { 19 return o1.id - o2.id; 20 } 21 22 } 23 24 public static class IdDescendingComparator implements Comparator<Student> { 25 26 @Override 27 public int compare(Student o1, Student o2) { 28 return o2.id - o1.id; 29 } 30 31 } 32 33 public static class AgeAscendingComparator implements Comparator<Student> { 34 35 @Override 36 public int compare(Student o1, Student o2) { 37 return o1.age - o2.age; 38 } 39 40 } 41 42 public static class AgeDescendingComparator implements Comparator<Student> { 43 44 @Override 45 public int compare(Student o1, Student o2) { 46 return o2.age - o1.age; 47 } 48 49 } 50 51 public static void printStudents(Student[] students) { 52 for (Student student : students) { 53 System.out.println("Name : " + student.name + ", Id : " + student.id + ", Age : " + student.age); 54 } 55 System.out.println("==========================="); 56 } 57 58 public static void main(String[] args) { 59 Student student1 = new Student("A", 1, 23); 60 Student student2 = new Student("B", 2, 21); 61 Student student3 = new Student("C", 3, 22); 62 63 Student[] students = new Student[] { student3, student2, student1 }; 64 printStudents(students); 65 66 Arrays.sort(students, new IdAscendingComparator()); 67 printStudents(students); 68 69 Arrays.sort(students, new IdDescendingComparator()); 70 printStudents(students); 71 72 Arrays.sort(students, new AgeAscendingComparator()); 73 printStudents(students); 74 75 Arrays.sort(students, new AgeDescendingComparator()); 76 printStudents(students); 77 78 } 79 80 }
题目七
桶排序、计数排序、基数排序的介绍
1，非基于比较的排序，与被排序的样本的实际数据状况很有关系，所以实际中并不经常使用
2，时间复杂度O(N)，额外空间复杂度O(N)
3，稳定的排序
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]; 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) { arr[i++] = j; } } }
题目八
补充问题
给定一个数组，求如果排序之后，相邻两数的最大差值，要求时间复杂度O(N)，且要求不能用非基于比较的排序。
解题思路：
1、准备N+1个桶，遍历数组找到最小最大值
2、Min放在第一个桶，max放在最大的桶，然后把最小到最大的这个范围等分为N+1份
3、那么两边放入最大和最小，必然中间会有一个空桶。桶内部的差值肯定没有桶范围的大。
4、所以流程为：N个数准备N+1个桶，0~N，当一个数进入桶，每个桶只记录出现的最小值和最大值，还有一个bool记录这个桶有没有进入过数。
5、遍历完成后，计算费控桶直接的差值，用min和max计算，如果是空桶就跳过。
6、设置一个空桶的原因是，用于否定最大差值一定不来自一个桶内部，因为有空桶的存在，那空桶两侧的非空桶差值，肯定大于或者等于任意桶内容最大和最小值的差值。
7、上面的式子就是右边先计算出，每个桶放多少个数，再把num-min为分子，可以看当前数占用在哪个位置上。例如有10个数，最大最小范围为1~100那就是说10/100=1/10，当前数要在放以10为分母的中，去计算他该去哪个桶。
题目九
介绍一下工程中的综合排序算法
少于60个数的直接用插入排序。（前期用递归分一半一半的，变小了再按照其他排序方法来排序，综合利用各排序的优点）
基础类型用快速排序，因为基础类型相同分数无差异。
自定义类型用归并排序，因为关乎多类数据，需要保持原始排序。