排序
1 基础知识
1. 异或运算
使用异或(^)运算交换数值
- 异或性质：
- 相同为0，不同为1
- 2进制下可理解为无进位相加
- 0 ^ x = x (0与任何数异或均为任何数)
- x ^ x = 0 (任何数与自己异或均为0)
- 异或满足交互率，结合律
- a ^ b ^ a = a ^ a ^ b = 0 ^ b = b
- 使用在交互数值上可节剩辅助空间
public static void swap(int[] arr, int i, int j){ if(i != j) { arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; } }
- 方法解释
int a = x; int b = y; a = a ^ b; //a = x ^ y b = a ^ b; //b = x ^ y ^ y = x ^ 0 = x a = a ^ b; //a = x ^ y ^ x = y ^ 0 = y
- 注意点：
- a , b 的数值可以相同但是不能是同一个内存空间，因为同一个内存空间会使得最后值为0
- 在操作数组时，要注意下标不能相同
- 例题：
- 在一个数组中只有一个数出现了奇数次，其余数是偶数次，求该数，要求时间复杂度为O(n)空间复杂度为O(1)
public void test(int[] arr){ int eor = 0; for (int cur : arr){ eor ^= cur; //偶数次异或为0，奇数次为保留其值 } System.out.println(eor); }
- 在一个数组中有俩个数出现了奇数次，其余数是偶数次，求该数，要求时间复杂度为O(n)空间复杂度为O(1)
public void test(int[] arr){ //假设计数次的俩个数位a, b int eor = 0; for (int cur : arr){ eor ^= cur; } //此时 eor = a ^ b // eor != 0 // eor上必有一个位置是1 // 这个1的位置便是区分 a,b 的关键 int rightOne = eor & (~eor + 1); //提取出最右侧的1 //rightOne只有一位为1，其余位均为0，便于区分 a,b int a = 0; for (int cur : arr){ if ((cur & rightOne) == 0){ //此时假设b的rightOne位置为1，便可排除b,留下a a ^= cur; } } int b = eor ^ a; System.out.println(a + b); }
- 小结：
- 异或运算可以用于交互数值
- 在统计数值时，也可通过异或运算查找奇数次出现的数值
- eor & (~eor + 1) 找到eor最右侧的1的方法
2. 时间复杂度
- 时间复杂度：在最坏情况下的时间复杂度
- 选择，冒泡，插入在时间复杂度上都是O(n²)，但在一些特殊情况下，插入的时间复杂度可以降低，故插入优于选择与冒泡
3. 局部最小
arr数组中，无序，相邻数一定不相等，找其局部最小，要求时间复杂度小于O(n)
思路：局部最小首先考虑数组中的第一位与最后一位，若：第一位必第二位小，则第一位便是局部最小；若：最后一位比倒数第二位小，则最后一位是局部最小。然后，便可使用二分发进行快速判断，去中点mid，比较mid-1，mid，mid+1，若mid是三者中最小值则，mid便是局部最小，否则，继续进行二分。
心得：二分法，不一定必须在有序数组中使用，可根据实际问题具体分析，二分法在很多情况下可以优化时间复杂度。
4. 对数器
- 概念：
1 有一个想要测试的方法 a
2 实现复杂度不好，但是容易实现的方法b
3 实现一个随机样本产生器
4 把方法a，b跑相同的随机样本，测试得到的结果是否一样
5 如果有随机样本使得比对结果不一致，打印样本进行人工干预，修改a
6 当样本数量很多比对测试依然正确，可以确定a的正确性 - 例：测试排序方法：
public static void aSort(int[] arr){ //待测试的排序方法a } public static void bSort(int[] arr){ //方法b采用系统提供的排序 Arrays.sort(arr); } public static int[] generateRandomArray(int maxSize, int maxValue){ //随机数的产生 //Math.random() -> [0, 1) 的所有小数，等概率返回 //Math.random() * N -> [0, N) 的所有小数 //（int)(Math.random() * N) -> [0, N-1]所有整数 int[] arr = new int[(int)((maxSize + 1) * Math.random())]; //随机长度 for (int i = 0; i < arr.length; i++){ arr[i] = (int)((maxValue + 1) * Math.random()); } return arr; } 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; } public static boolean isEqual(int[] arr1, int[] arr2){ //判断俩数组是否相同 for (int i = 0; i < arr1.length; i++){ if (arr1[i] != arr2[i]){ return false; } } return true; } //for test public static void main(String[] args) { int testTime = 5000; //测试次数 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); aSort(arr1); //方法a排序 bSort(arr2); //方法b排序 if(!isEqual(arr1, arr2)){ //比较a, b排序方法产生结果是否相同 succeed = false; break; } } System.out.println(succeed); }
- 心得：对数器方法可以脱离平台实现代码正确性的判断
5. 比较器（重载运算符）
- 概念：自己去定义比较运算的运算规则
- 比较决策：（参数1，参数2）
（1）返回负数时，参数1在前
（2）返回正数时，参数2在前
（3）返回 0时，无所谓 - 应用：在某些特殊的比较时，提前使用比较器制定比较策略，优化代码。也可以制定复杂的比较器，在多种参数的比较下进行比较区分
- 例：比较器在堆中的应用：例如在大根堆中，使用数组下标作为参数
（1）返回负数时，参数1放在堆的上面
（2）返回正数时，参数2放在堆的上面
（3）返回 0时，1，2无所谓谁都可以
6. 递归时间复杂度(master公式)
- 例：数组中查询最大值，递归实现
思路：折半每次寻找左右两边的最大值，再将其进行比较
public static int max(int[] arr, int L, int R){ //在arr[L, R]范围上求最大值 if (L == R){ return arr[L]; } int mid = L + ((R - L) >> 1); // 为了防止 R + L 的数值溢出，采用 L + （R - L) / 2 // x>>1 右移一位相当于除以2，其速度比 / 2 快 int leftMax = max(arr, L, mid); //左边的最大值 int rightMax = max(arr, mid + 1, R); //右边最大值 return Math.max(leftMax, rightMax); }
分析：通过系统栈实现递归，递归过程是一颗多叉树，计算树结点的过程就是利用栈实现树的后序遍历，栈的空间就是多叉树的高度
- master公式
1 特征：T(N) = a * T(N/b) + O(n^d)
T(N):母问题的问题规模，T(N/b)子问题的问题规模（ 要求子规模的问题等量），a子问题的调用次数，O(n^d)除去调用只外剩余过程的时间复杂度（决策过程）
2 例题分析：T(N) = 2 * T(N/2) + O(1)
例：若将数组分为3份进行找最大值，在将数组遍历打印，此时T(N) = 3 * T(N/3) + O(n)
3 注意点，子问题的划分规模一定要相同
4 取值情况：
其中，log以b位底的a次，就是递归的多叉树高度
2 重要排序
1. 归并排序
- 思路：左右侧划分，每次都使得左右两侧先分别有序，在通过辅助空间进行左右的合并，递归进行操作，从单一个数到俩个数有序……直至整体有序
public static void progress(int[] arr, int L, int R){ //递归调用归并排序 if (L == R){ return; } int mid = L + ((R - L) >> 1); //防止R + L越界 progress(arr, L, mid); //左侧排序 progress(arr, mid + 1, R); //右侧排序 merge(arr, L, mid, R); //排序函数 } public static void merge(int[] arr, int L, int M, int R){ //一次归并，左右已经有序 int[] temp = new int[R - L + 1]; //临时空间用于归并 int tempNum = 0; //temp计数 int LNum = L; //左侧计数 int RNum = M + 1; //右侧计数 while (LNum <= M && RNum <= R){ //左右的合并 temp[tempNum++] = arr[LNum] <= arr[RNum] ? arr[LNum++] : arr[RNum++]; } while (LNum <= M){ //左侧还有剩余 temp[tempNum++] = arr[LNum++]; } while (RNum <= R){ //右侧还有剩余 temp[tempNum] = arr[RNum++]; } for (int i = 0; i < temp.length; i++){ //将临时空间整合到原数组中 arr[L + i] = temp[i]; } }
- 时间复杂度分析：
采用master公式：分析递归 progress()是递归函数，母问题的初始规模为N，解决方法就是将数组一分为二，左右分别有序，故子问题的规模为N/2，merge()函数是决策函数其时间复杂度为O(n)
则可分析出：T(N) = 2 * T(N/2) + O (N) 即 a = 2, b = 2, d = 1:
由此可知归并的时间复杂度为：O(N * logN) - 深入分析merge(归并):
1 普通排序时间复杂度为O(n^2)的原因：大量的时间浪费在比较上，一次比较只能找到其中一个最大值，下一次比较并没有借鉴上一次比较的数据，造成大量比较行为的浪费
2 归并时间复杂度降低的原因：每一次是一组有序的部分与另一组有序的部分进行比较，不会浪费上一次比较的结果
3 排序的方法是外排序：利用外部空间(temp临时数组)进行排序，空间复杂度为O(N) - 归并排序的扩展
小和问题
在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。例：[1,3,4,2,5] 1的左边没有比1小的数；3的左边是1；4的左边是1，2；2的左边是1；5的左边是1，3，4，2。所以小和数是1+1+3+1+1+3+4+2 = 16
（1）解题思路：暴力解题法：去直接遍历每一个数字左边比它小的数，这样时间复杂度一定是O(n^2)。逆向思维：去寻找一个数的右边有几个数比它大，则该数就要加几次。
（2）要点：结合归并排序，在左右侧内部不要进行计数，而是每次进行合并时直接比较，因为左右都是有序的，便可减少比较次数，将时间复杂度降低到O(N*logN)
（3） 注意点：在左右有相同数的时候，不产生小和且要先拷贝右组数。不能省略排序过程，因为要保证右边数的部分无需遍历，就可提供与该数比较有几个数大。
public static int smallSum(int[] arr, int L, int R){ //递归调用归并排序，并求小和 if (L == R || arr == null){ return 0; } int mid = L + ((R - L) >> 1); //防止R + L越界 //求小和，就是递归的左右小和的和 return smallSum(arr, L, mid) + smallSum(arr, mid + 1, R) + merge(arr, L, mid, R); } public static int merge(int[] arr, int L, int M, int R){ //一次归并，左右已经有序 int[] temp = new int[R - L + 1]; //临时空间用于归并 int tempNum = 0; //temp计数 int LNum = L; //左侧计数 int RNum = M + 1; //右侧计数 int sum = 0; //小和数的记录 while (LNum <= M && RNum <= R){ //小和的计算，若左侧的小，则该数*其右侧比起大的数的个数为其小和 //若右侧小，或者相等不加入小和 sum += arr[LNum] < arr[RNum] ? arr[LNum] * (R - RNum + 1) : 0; //左右的合并，在等于的情况下，先拷贝右组，将小于等于的判断改为等于 temp[tempNum++] = arr[LNum] < arr[RNum] ? arr[LNum++] : arr[RNum++]; } while (LNum <= M){ //左侧还有剩余 temp[tempNum++] = arr[LNum++]; } while (RNum <= R){ //右侧还有剩余 temp[tempNum] = arr[RNum++]; } for (int i = 0; i < temp.length; i++){ //将临时空间整合到原数组中 arr[L + i] = temp[i]; } return sum; }
逆序对问题
在一个数组中，左边的数如果比右边的数大，则这两个数构成一组逆序对统计逆序对的数量。
（1）此题与小和问题类似只需改变merge函数即可
（2）在小和问题中我们去寻找一个数的右边有几个数比它大，逆序对问题中我们只需要找左边的几个数比他大就行，因为左边时顺序的，所以若左边的一个比右边的大，则左部分的右边均比其大
public static int number(int[] arr, int L, int R){ //递归调用归并排序，并求逆序数的个数 if (L == R || arr == null){ return 0; } int mid = L + ((R - L) >> 1); //防止R + L越界 // return number(arr, L, mid) + number(arr, mid + 1, R) + merge(arr, L, mid, R); } public static int merge(int[] arr, int L, int M, int R){ //一次归并，左右已经有序 int[] temp = new int[R - L + 1]; //临时空间用于归并 int tempNum = 0; //temp计数 int LNum = L; //左侧计数 int RNum = M + 1; //右侧计数 int num = 0; //逆序数计数 while (LNum <= M && RNum <= R){ //若左侧的第一个值都比右侧的某一个值大，则加上左侧的剩余都是逆序数 num += arr[LNum] > arr[RNum] ? (M - LNum + 1) : 0; //左右的合并 temp[tempNum++] = arr[LNum] <= arr[RNum] ? arr[LNum++] : arr[RNum++]; } while (LNum <= M){ //左侧还有剩余 temp[tempNum++] = arr[LNum++]; } while (RNum <= R){ //右侧还有剩余 temp[tempNum] = arr[RNum++]; } for (int i = 0; i < temp.length; i++){ //将临时空间整合到原数组中 arr[L + i] = temp[i]; } return num; }
- 总结
1 归并的merge()函数本质就是：将两个有序数组合并成一个有序数组，为了提高时间效率采用外排序，即生成的数组为新数组。充分利用其有序性，减少比较次数，单次时间复杂度为O(N)。
2 将整个数组有序就是logN次的merge()调用，即整体的复杂度为O(N*logN)
3 归并的应用：目地就是要利用其合并时，左右已经有序的性质，极致的去减少比较次数，便可优化时间复杂度。例如：若左部分的其中比右部分的某个值大，则可说明，左面的剩余部分也都比该数值大。便无需再遍历左边的剩余部分，减少时间复杂度。
2. 快速排序
- 思路：选择划分数，左侧均比划分数小，右侧均比划分数大，递归左右侧
- 时间复杂度分析：快速排序的时间复杂度与划分数的选择密不可分，若每次划分数恰好选到中间值，则时间复杂度可以达到最好情况O(NlogN)，若划分数选取较差，则快速排序会退化成冒泡排序，时间复杂度达到O(n^2)。
- 空间复杂度分析：最好情况，划分可以分成类似二叉树O(logN)，最差O(N)，且此空间的复杂度不可能进行优化到O(1)，采用随机数法，只能达到O(logN)
- 改进思路：划分数的选取至关重要，采用从数组中抽取随机数定为划分数，便可将时间复杂度的控制在O(N*logN)
- 算法实现：实现划分的不同方法，每次先将划分数，放到数组的尾位置
（1）思路一：将整个数组分为三个区域：小于划分数；等于划分数；大于划分数
若 [ i ] < num , [ i ] 与小于区的下一个数交换(便可划分出等于区)，小于区右扩，i++
若 [ i ] = num , i++
若 [ i ] > num , [ i ]与大于区的上一个数交换，大于区左扩，（注意不要进行 i++，因为交换后 [ i ]位置的数字仍需进行判断
当 i 的下标到达大于区的下标时停止，最后将大于区的第一个，与最后一个（划分数交换），大于区右缩
（2）思路二：双指针实现，设置low，high指针
第一步：移动high指针，若[high] > num，high- -，否则记录high的位置
第二步：移动low指针，若[low] < num，low++，交换low，high的数交换
重复一二步骤，直至low > high，最后将low的位置，与最后一个（划分数交换）
思路一： public static void quickSort(int[] arr, int L, int R){ if(L < R){ //选取随机数作为划分数 //将划分数与最后一个数位置 swap(arr, L + (int)(Math.random() * (R - L + 1)), R); //调用划分函数，并且在划分函数中返回下一次划分的位置 int[] flag = partition(arr, L, R); quickSort(arr, L, flag[0]); //左侧划分区域 quickSort(arr, flag[1], R); //右侧划分区域 } } public static int[] partition(int[] arr, int L, int R){ //因为每次划分后的左右位置不确定，所以需要函数返回记录的值 //注意在方法一中是划分了三个区域，所以要记录俩个值 int left = L - 1; //左侧小于区，初始没有数值 int right = R; //右侧大于区 int i = L; //表示当前划分的位置 while (i < right){ if (arr[i] < arr[R]){ //当前位置 < 划分数 //当前位置与小于区的下一个位置交换，小于区右扩 //移动当前位置，无需判断，因为小于区的下一个位置一定是小于等于的 swap(arr, i++, ++left); } else if (arr[i] > arr[R]){ //当前位置 > 划分数 //当前位置与大于区的上一个位置交换，大于区左扩 //当前位置不能移动，因为跨度较大，需要判断交互后的数的情况 swap(arr, i, --right); } else { //相等情况，只移动当前位置即可 i++; } } //最后大于区的第一个与数组最后一个（划分数位置）交换 //大于区右缩 swap(arr, right++, R); return new int[]{left, right}; } public static void swap(int[] arr, int i, int j){ //交互数组中a, b位置的数值 if (i != j){ //在i，j不相同的前提下，使用异或运算实现数值的交换 arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; } }
思路二： public static void quickSort(int[] arr, int L, int R){ if(L < R){ //选取随机数作为划分数 //将划分数与最后一个数位置 swap(arr, L + (int)(Math.random() * (R - L + 1)), R); //调用划分函数，并且在划分函数中返回下一次划分的位置 int flag = partition(arr, L, R); quickSort(arr, L, flag - 1); //左侧划分区域 quickSort(arr, flag + 1, R); //右侧划分区域 } } public static int partition(int[] arr, int L, int R){ int low = L; //小于区 int high = R; //大于区 int base = arr[R]; //存划分数 while (low < high){ //时刻保证low < high while (arr[low] <= base && low < high){ //满足小于区，移动下标 //找到小于区中，大于基准数的 low++; } //直接赋值，无需交换，因为base存了划分数 arr[high] =arr[low]; while(arr[high] >= base && low < high){ //满足大于区，移动下标 //找到大于区中，小于基准数的 high--; } arr[low] = arr[high]; } arr[low] = base; return low; } public static void swap(int[] arr, int i, int j){ //交互数组中a, b位置的数值 if (i != j){ //在i，j不相同的前提下，使用异或运算实现数值的交换 arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; } }
- 总结：
快排的partition是一种划分标准（ 0，1标准），由此可以解决很多问题：例如：正负数分别放到左右两边；奇偶数分别放在两边……但是不能保持稳定行，且空间复杂度是O(logN)
3. 堆排序
堆结构
- 堆的思想：使用数组的数据结构模拟堆（完全二叉树），通过下标关系确定左右子树，以及父节点
- 注意点：数组下标是0还是1开始（确定左右子树，父节点的下标表示方法），大根堆还是小跟堆
以下代码中：数组从0开始，构造大根堆，使用heapSize规定数组中堆的大 - 方法heapInsert()：堆中某个数出现在index位置后的上移操作
public static void heapInsert(int[] arr, int index){ //某个数出现在index位置后的上移操作 while (arr[index] > arr[(index - 1) / 2]){ //当index的位置，比父位置的数大 swap(arr, index, (index - 1) / 2); //交换位置，使其满足大根堆 index = (index - 1) / 2; //index移动 } }
- 方法heapify()：堆中某个数出现在index位置后的下移操作
public static void heapify(int[] arr, int index, int heapSize){ //某个数出现在index位置后的下移操作 //因为是下移，就要判断，在数组中的操作是否会超越堆的范围，需要heapSize int lchild = index * 2 + 1; //左子树 while (lchild <= heapSize){ //当左子树存在时 int rchild = lchild + 1; //右子树; int largest; //在一个小堆中记录较大数的下标 if (rchild <= heapSize){ //当右子树也存在 largest = arr[lchild] > arr[rchild] ? lchild : rchild; //左右子树中较大的 largest = arr[largest] > arr[index] ? largest : index; //与index比较 } else { //右子树不存在 largest = arr[lchild] > arr[index] ? lchild : index; } if (largest == index){ //当index的位置就是最大值时 break; } swap(arr, index, largest); //交换使其满足堆 index = largest; //index更新 lchild = index * 2 + 1; //对应的左子树更新 } }
- 当堆中的index位置的元素发生了修改后，修改后的元素与原来的元素进行比较，若变小则执行heapify()操作，若变大执行heapInsert()操作
- 在一个规模为N的堆中新增，或改变一个堆的数据时间复杂度均为O(logN)
堆排序的实现
- 建立大根堆：
初始的heapSize为0，表示堆中只有一个元素，重复：heapSize++，加入一个元素执行heapInsert()方法，进行位置调整。 - 有序数组的形成：
重复：堆的数组中第一个位置（最大元素的位置）与heapSize的位置交换，heapSize–（将最大数移出堆的范围），对第一个元素执行heapify()重新构建大根堆
public static void heapSort(int[] arr){ //堆排序的实现 if (arr == null || arr.length < 2){ return; } int heapSize; for (heapSize = 0; heapSize < arr.length; heapSize++){ //构造大根堆 heapInsert(arr, heapSize); } for (heapSize = arr.length - 1; heapSize >= 0;){ //每次使heapSize的位置与第一个位置交换 swap(arr, 0, heapSize); heapSize--; heapify(arr, 0, heapSize); } } public static void heapInsert(int[] arr, int index){ //某个数出现在index位置后的上移操作 while (arr[index] > arr[(index - 1) / 2]){ //当index的位置，比父位置的数大 swap(arr, index, (index - 1) / 2); //交换位置，使其满足大根堆 index = (index - 1) / 2; //index移动 } } public static void heapify(int[] arr, int index, int heapSize){ //某个数出现在index位置后的下移操作 //因为是下移，就要判断，在数组中的操作是否会超越堆的范围，需要heapSize int lchild = index * 2 + 1; //左子树 while (lchild <= heapSize){ //当左子树存在时 int rchild = lchild + 1; //右子树; int largest; //在一个小堆中记录较大数的下标 if (rchild <= heapSize){ //当右子树也存在 largest = arr[lchild] > arr[rchild] ? lchild : rchild; //左右子树中较大的 largest = arr[largest] > arr[index] ? largest : index; //与index比较 } else { //右子树不存在 largest = arr[lchild] > arr[index] ? lchild : index; } if (largest == index){ //当index的位置就是最大值时 break; } swap(arr, index, largest); //交换使其满足堆 index = largest; //index更新 lchild = index * 2 + 1; //对应的左子树更新 } } public static void swap(int[] arr, int i, int j){ //交互数组中a, b位置的数值 if (i != j){ //在i，j不相同的前提下，使用异或运算实现数值的交换 arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; } }
- 时间复杂度：构造堆，实现堆排序都是O(nlogn)
- 空间复杂度：O(1)
- 代码优化：在构造堆时不是一个数一个数的添加维持大根堆的性质，而是直接一个数组的直接全部变为大根堆，从数组下标的N / 2处开始到1的位置进行heapify()操作。则在构造堆时，将时间复杂度优化到O(N)，但是不能最终优化堆排序的时间复杂度
使用： for (int i = arr.length / 2; i >= 0; i--){ //heapify方法构造堆 heapify(arr, i, arr.length - 1); } 代替： for (heapSize = 0; heapSize < arr.length; heapSize++){ //构造大根堆 heapInsert(arr, heapSize); }
优先级队列(堆结构)
1 思路：建立大小为k的小根堆，第一次存入0到k - 1的元素，构造小根堆，弹出小根堆中最小的元素，放到0位置，加入k位置的数组，再次弹出最小放到1位置重复弹出即可
2 时间复杂度：O(N*logk)，当k足够小时，近似为O(N)
3 方法：使用Java中的优先级队列（PriorityQueue)类创建小根堆对象，add()方法向小根堆中加入数据，poll()方法弹出小根堆中的堆顶（最小元素）。其优先级队列内部有自身的堆结构进行维护，方便操作。双下标实现，index下标记录将要进入堆的数组位置，flag下标记录经过堆排序后出来元素的位置。
public static void priorityQueue(int[] arr, int k){ //小根堆的创建 PriorityQueue<Integer> heap = new PriorityQueue<>(); int index; //记录将要进入堆的数组位置 for (index = 0; index < Math.min(arr.length, k); index++){ //小根堆的构建，大小为k heap.add(arr[index]);//往小根堆中加入元素 } int flag;//记录经过堆排序后出来元素的位置 for (flag = 0; index < arr.length; index++, flag++){ //最小元素的弹出，以及新元素的入堆 arr[flag] = heap.poll(); heap.add(arr[index]); } while (!heap.isEmpty()){ //当堆不为空时,已经没有新元素入堆 arr[flag++] = heap.poll();//将堆中剩余元素全部出堆 } }
- 总结：系统提供的优先队列，本质上就是小根堆，可以通过调用实现堆的应用，但是：系统提供的优先队列在对堆中的任意元素进行修改时，效率较低。故在某些问题中，仍需自己创建堆结构。
4. 基数排序（桶排序）
- 概念：不基于比较，通过数据的状况进行统计，再实现排序
- 优点：时间复杂度较低O(N)
- 缺点：需要数据的情况进行不同的分析，空间复杂度较高O(N)，使用范围受限制
- 例题：整数的排序：
（1）先寻找最大的数字（目地是要知道排序的位数）
（2）十个“桶”的备用（可以说栈，队列，数组……）在此问题中使用队列实现
（3）依次按照个位将数组遍历放入对应的桶
（4）从左往右依次按照队列的顺序（先进先出）重新进入数组
（5）按照十位，百位……重复（3），（4）步骤，直至最高位完成
思路：个位，十位，百位……之间存在优先级，优先级低的先排序，同时使用队列的数据结构也保持了优先级低的排序结果，便可实现全部排序
优化：使用前缀计数器 count[] 代替队列的数据结构，在构造前缀计数器时从左往右遍历数组，例：count[i]：当前位置是(0-i)的数字有多少个，使用count[i]时从右往左遍历数组在通过前缀计数器对应词频减一就是其排序后的位置
public static void radixSort(int[] arr){ if (arr == null || arr.length < 2){ return; } //radixSort方法的重写 radixSort(arr, 0, arr.length - 1, maxbits(arr)); } //radixSort方法的重写 public static void radixSort(int[] arr, int L, int R, int res){ //在数组arr，L到R上进行基数排序，res表示最大位数 int i = 0, j = 0; //辅助变量 int[] bucket = new int[R - L + 1]; //与要排序数组同规模的辅助数组，便于收集 for (int d = 1; d <= res; d++){ //最大有几位数就进行几次循环 int[] count = new int[10]; //前缀计数器 //count[0]：当前位置（d位）是0的数字有多少个 //count[1]：当前位置（d位）是0和1的数字有多少个 //count[2]：当前位置（d位）是0，1和2的数字有多少个 //count[i]：当前位置（d位）是(0-i)的数字有多少个 for (i = L; i <= R; i++){ //词频的统计 j = getDigit(arr[i], d);//得到d位置的数字 count[j]++; } for (i = 1; i < count.length; i++){ //前缀计数器的构造 count[i] = count[i] + count[i - 1]; } for (i = R; i >= L; i--){ //从右向左排序d位置的数值 j = getDigit(arr[i], d); //辅助数组对排好序的数临时存储 //前缀计数器对应词频减一就是其排序后的位置 bucket[count[j] - 1] = arr[i]; count[j]--; //计数器的跟新 } for (i = L, j = 0; i <= R; i++, j++){ //将临时数组传给原数组 //使得本次以d位置数值大小的排序生效 arr[i] = bucket[j]; } } } public static int maxbits(int[] arr){ //用来求该数组中最大值的位数 int max = 0; //存最大值 for (int i = 0; i < arr.length; i++){ max = Math.max(max, arr[i]); } int res = 0; //用来存位数 while (max != 0){ res++; max /= 10; } return res; } public static int getDigit(int x, int d){ //返回数字x的d位的数值 //x除以10的 d-1 次方，再对10取模 return ((x / ((int)Math.pow(10, d - 1))) % 10); }
3. 总结
- 目前没有找到时间复杂度O(N*longN)，空间复杂度O(1)，又稳定的排序
- 基于比较的排序，时间复杂度目前最快O(N*longN)
- 稳定性，在有多种参数进行比较的情况下，稳定性很重要
| 时间复杂度 | 空间复杂度 | 稳定性 | |
| 选择 | O(N^2) | O(1) | × |
| 冒泡 | O(N^2) | O(1) | √ |
| 插入 | O(N^2) | O(1) | √ |
| 归并 | O(N*logN) | O(N) | √ |
| 快排 | O(N*logN) | O(logN) | × |
| 堆排 | O(N*logN) | O(1) | × |
| 基数 | O(d*(n+k)) | O(n+k) | √ |
- 排序方法的优先级：通常情况下选择快排（在实验种快排的速度是最快的），若对空间复杂度有要求则选择堆排，若对稳定性有要求选择归并排序
- 常见的坑：
（1）归并排序的空间复杂度能变成O(1)，但是非常难，需要掌握：归并排序内部缓存法，使用此方法后， 稳定性会丧失。不如直接使用堆排序
（2）原地归并排序 = 垃圾，该方法会使得时间复杂度变成O(N^2)
（3） 快速排序可以做到稳定性，但是非常难，方法：01stable sort"，该方法会使得空间复杂度变成O(N)，不如直接使用归并
（4）目前对一些基本排序的改进没有太大的成就，在改进的同时会使原排序算法丧失某些优势。即时间复杂度，空间复杂度，稳定性，不能同时追求完美 - 工程上对排序的改进
（1）充分利用O(N*logN)和O(N^2)排序的优势，综合排序：在样本量较大时使用（快速或归并）的排序方法进行划分，当大样本被划分成小样本后在使用插入排序（因为在样本值较小时，插入的速度特别快）
（2）稳定性的考虑：在使用计算机内部的排序时，对于基础数据类型，计算机会使用快速排序，而对于非基础类型，会选择归并排序。原因：对于基础数据类型，计算机会忽略其稳定型，但是非基础类型就需要考虑稳定型对其的影响，所以会选择归并
