选择排序

先从0~N上找出最小的交换到第一位 再从1~N上找出最小的交换到第二位 ……

  1. public void selectionSort(int[] arr) {
  2.     if (arr == null || arr.length < 2) {
  3.         return;
  4.     }
  5.     for (int i = 0; i < arr.length - 1; i++) {
  6.         int minIdx = i;
  7.         for (int j = i + 1; j < arr.length; j++) {
  8.             minIdx = arr[minIdx] > arr[j] ? j : minIdx;
  9.         }
  10.         swap(arr, i, minIdx);
  11.     }
  12. }

冒泡排序

从第一个开始遇到后一个比自己小就与后一个交换位置

  1. public void bubbleSort(int[] arr) {
  2.     if (arr == null || arr.length < 2) {
  3.         return;
  4.     }
  5.     for (int i = arr.length - 1; i > 0; i--) {
  6.         for (int j = 0; j < i; j++) {
  7.             if (arr[j] > arr[j + 1]) {
  8.                 ArrayUtils.swap(arr, j, j + 1);
  9.             }
  10.         }
  11.     }
  12. }

插入排序

从头开始，每往后移动一位，就往前（已经移动过的）看，如果有比之前的数小，就交换 做到0 - i上有序

  1. public void insertionSort(int[] arr) {
  2.     if (arr == null || arr.length < 2) {
  3.         return;
  4.     }
  6.     for (int i = 0; i < arr.length; i++) {
  7.         for (int j = i; j > 0; j--) {
  8.             if (arr[j] < arr[j - 1]) {
  9.                 ArrayUtils.swap(arr, j, j - 1);
  10.             }
  11.         }
  12.     }
  13. }

归并排序

将整个数组分为两块儿 使其在左侧区域有序 使其在右侧区域有序 最后将两块儿区域进行合并，使得合并的区域有序（左右两个区域如果值相等，则先处理左侧区域）

  1. public void mergeSort(int[] arr) {
  2.     if (arr == null || arr.length < 2) {
  3.         return;
  4.     }
  5.     process(arr, 0, arr.length - 1);
  6. }
  8. private void process(int[] arr, int l, int r) {
  9.     if (l >= r) {
  10.         return;
  11.     }
  12.     int mid = l + ((r - l) >> 1);
  13.     //让左侧范围（l - mid）上有序
  14.     process(arr, l, mid);
  15.     //让右侧范围（mid+1 - r）上有序
  16.     process(arr, mid + 1, r);
  17.     //合并左右区域，使其在范围（l - r）上有序
  18.     merge(arr, l, mid, r);
  19. }
  21. private void merge(int[] arr, int l, int mid, int r) {
  22.     int[] help = new int[r - l + 1];
  23.     //help数组的下标索引
  24.     int hIdx = 0;
  25.     //左侧区域的起始位置（结束位置为mid）
  26.     int idxL = l;
  27.     //右侧区域的起始位置（结束位置为r）
  28.     int idxR = mid + 1;
  29.     while (idxL <= mid && idxR <= r) {
  30.         help[hIdx++] = arr[idxL] <= arr[idxR] ? arr[idxL++] : arr[idxR++];
  31.     }
  33.     while (idxL <= mid) {
  34.         help[hIdx++] = arr[idxL++];
  35.     }
  36.     while (idxR <= r) {
  37.         help[hIdx++] = arr[idxR++];
  38.     }
  39.     //将有序数据刷回源数组
  40.     for (int i = 0; i < help.length; i++) {
  41.         arr[l++] = help[i];
  42.     }
  43. }

给定一个数组arr，求数组小和

在一个数组中，一个数左边比它小的数的总和，叫该数的小和，所有数的小和累加起来，叫数组小和 例子： [1,3,4,2,5] 1左边比1小的数：没有 3左边比3小的数：1 4左边比4小的数：1、3 2左边比2小的数：1 5左边比5小的数：1、3、4、 2 所以数组的小和为1+1+3+1+1+3+4+2=16 给定一个数组arr，求数组小和

解题思路：
将左边有多少个数比我小，转换为右边有多少个数比我大 在归并排序merge方法的基础上， 当拷贝左组值是产生小和，拷贝右组值时不产生小和 当左组数和右组数相等时，先拷贝右组数

  1. public int smallSum(int[] arr) {
  2.     if (arr == null) {
  3.         return 0;
  4.     }
  5.     return process(arr, 0, arr.length - 1);
  6. }
  8. private int process(int[] arr, int l, int r) {
  9.     if (l >= r) {
  10.         return 0;
  11.     }
  12.     int mid = l + ((r - l) >> 1);
  13.     int leftMinSum = process(arr, l, mid);
  14.     int rightMinSum = process(arr, mid + 1, r);
  15.     int currMinSum = merge(arr, l, mid, r);
  16.     return leftMinSum + rightMinSum + currMinSum;
  17. }
  19. private int merge(int[] arr, int l, int mid, int r) {
  20.     int[] help = new int[r - l + 1];
  21.     int idx = 0;
  22.     int lIdx = l;
  23.     int rIdx = mid + 1;
  24.     int minSum = 0;
  25.     while (lIdx <= mid && rIdx <= r) {
  26.         //拷贝左组产生小和
  27.         minSum += arr[lIdx] < arr[rIdx] ? arr[lIdx] * (r - rIdx + 1) : 0;
  28.         //相等时先拷贝右组
  29.         help[idx++] = arr[lIdx] < arr[rIdx] ? arr[lIdx++] : arr[rIdx++];
  30.     }
  31.     while (lIdx <= mid) {
  32.         help[idx++] = arr[lIdx++];
  33.     }
  34.     while (rIdx <= r) {
  35.         help[idx++] = arr[rIdx++];
  36.     }
  37.     for (int i = 0; i < help.length; i++) {
  38.         arr[l++] = help[i];
  39.     }
  40.     return minSum;
  41. }

给定一个数组arr，求数组的降序对总数量

在一个数组中，任何一个前面的数a，和任何一个后面的数b，如果(a,b)是降序的，就称为降序对

解题思路：
将右边有多少个数比我小，转换为左边有多少个数比我大 在归并排序merge方法的基础上， 当拷贝右组值是产生逆序对，拷贝左组值时不产生逆序对 当左组数和右组数相等时，先拷贝左组数

  1. public int reverPairNumber(int[] arr) {
  2.     if (arr == null || arr.length < 2) {
  3.         return 0;
  4.     }
  5.     return process(arr, 0, arr.length - 1);
  6. }
  8. private int process(int[] arr, int l, int r) {
  9.     if (l >= r) {
  10.         return 0;
  11.     }
  12.     int mid = l + ((r - l) >> 1);
  13.     int lCount = process(arr, l, mid);
  14.     int rCount = process(arr, mid + 1, r);
  15.     int currCount = merge(arr, l, mid, r);
  16.     return lCount + rCount + currCount;
  17. }
  19. private int merge(int[] arr, int l, int mid, int r) {
  20.     int[] help = new int[r - l + 1];
  21.     int idx = 0;
  22.     int lIdx = l;
  23.     int rIdx = mid + 1;
  24.     int count = 0;
  25.     while (lIdx <= mid && rIdx <= r) {
  26.         //当移动右组数据时产生逆序对
  27.         count += arr[lIdx] > arr[rIdx] ? (mid - lIdx + 1) : 0;
  28.         //当左组和右组数据相等时先移动左组
  29.         help[idx++] = arr[lIdx] <= arr[rIdx] ? arr[lIdx++] : arr[rIdx++];
  30.     }
  31.     while (lIdx <= mid) {
  32.         help[idx++] = arr[lIdx++];
  33.     }
  34.     while (rIdx <= r) {
  35.         help[idx++] = arr[rIdx++];
  36.     }
  37.     for (int i = 0; i < help.length; i++) {
  38.         arr[l++] = help[i];
  39.     }
  40.     return count;
  41. }

在一个数组中，对于任何一个数num，求有多少个(后面的数*2)依然<num，返回总个数

比如：[3,1,7,0,2] 3的后面有：1，0 1的后面有：0 7的后面有：0，2 0的后面没有 2的后面没有 所以总共有5个

解题思路： 原有的归并排序不改变 在merge之前，先通过滑动索引计算右边有多少个数*2小于左边的数

  1. public int reversePairs(int[] arr) {
  2.     if (arr == null || arr.length < 2) {
  3.         return 0;
  4.     }
  5.     return process(arr, 0, arr.length - 1);
  6. }
  8. private int process(int[] arr, int l, int r) {
  9.     if (l >= r) {
  10.         return 0;
  11.     }
  12.     int mid = l + ((r - l) >> 1);
  13.     int lCount = process(arr, l, mid);
  14.     int rCount = process(arr, mid + 1, r);
  15.     int currCount = merge(arr, l, mid, r);
  16.     return lCount + rCount + currCount;
  17. }
  19. private int merge(int[] arr, int l, int mid, int r) {
  20.     int count = 0;
  21.     // [L....M] [M+1....R]
  22.     // 目前囊括进来的数，是从[M+1, windowR)
  23.     int windowR = mid + 1;
  24.     for (int i = l; i <= mid; i++) {
  25.         while (windowR <= r && (long) arr[i] > (long) arr[windowR] * 2) {
  26.             windowR++;
  27.         }
  28.         count += windowR - mid - 1;
  29.     }
  31.     int[] help = new int[r - l + 1];
  32.     int idx = 0;
  33.     int lIdx = l;
  34.     int rIdx = mid + 1;
  35.     while (lIdx <= mid && rIdx <= r) {
  36.         help[idx++] = arr[lIdx] <= arr[rIdx] ? arr[lIdx++] : arr[rIdx++];
  37.     }
  38.     while (lIdx <= mid) {
  39.         help[idx++] = arr[lIdx++];
  40.     }
  41.     while (rIdx <= r) {
  42.         help[idx++] = arr[rIdx++];
  43.     }
  44.     for (int i = 0; i < help.length; i++) {
  45.         arr[l++] = help[i];
  46.     }
  47.     return count;
  48. }

给定一个数组arr，两个整数lower和upper，返回arr中有多少个子数组的累加和在[lower,upper]范围上

leetcode：https://leetcode-cn.com/problems/count-of-range-sum/ 1）利用前缀和 2）原数组[lower,upper]这个问题 转换为 在前缀和数组中求新指标问题，前缀和数组中每个数X新指标为[x-upper,x-lower] 3）前缀数组的每一个x，在x之前有多少个数是在新指标[x-upper,x-lower]上

  1. public int countRangeSum(int[] arr, int lower, int upper) {
  2.     long[] sum = new long[arr.length];
  3.     sum[0] = arr[0];
  4.     //求前缀和
  5.     for (int i = 1; i < arr.length; i++) {
  6.         sum[i] = sum[i - 1] + arr[i];
  7.     }
  8.     return process(sum, 0, sum.length - 1, lower, upper);
  9. }
  11. private int process(long[] arr, int l, int r, long lower, long upper) {
  12.     if (l == r) {
  13.         //arr[l] 表示区间[0,l]的区间和
  14.         return arr[l] >= lower && arr[l] <= upper ? 1 : 0;
  15.     }
  16.     int mid = l + ((r - l) >> 1);
  17.     int lCount = process(arr, l, mid, lower, upper);
  18.     int rCount = process(arr, mid + 1, r, lower, upper);
  19.     int mergeCount = merge(arr, l, mid, r, lower, upper);
  20.     return lCount + rCount + mergeCount;
  21. }
  23. private int merge(long[] arr, int l, int mid, int r, long lower, long upper) {
  24.     int mergeCount = 0;
  25.     int windowL = l;
  26.     int windowR = l;
  27.     //将问题转换为针对右组任意数x，左组中有多少个数在区间[x-upper,x-lower]上
  28.     //指针不回退，时间复杂度O(N)
  29.     for (int i = mid + 1; i <= r; i++) {
  30.         long min = arr[i] - upper;
  31.         long max = arr[i] - lower;
  32.         while (windowL <= mid && arr[windowL] < min) {
  33.             windowL++;
  34.         }
  35.         while (windowR <= mid && arr[windowR] <= max) {
  36.             windowR++;
  37.         }
  38.         mergeCount += windowR - windowL;
  39.     }
  41.     long[] help = new long[r - l + 1];
  42.     int idx = 0;
  43.     int lIdx = l;
  44.     int rIdx = mid + 1;
  45.     while (lIdx <= mid && rIdx <= r) {
  46.         help[idx++] = arr[lIdx] <= arr[rIdx] ? arr[lIdx++] : arr[rIdx++];
  47.     }
  48.     while (lIdx <= mid) {
  49.         help[idx++] = arr[lIdx++];
  50.     }
  51.     while (rIdx <= r) {
  52.         help[idx++] = arr[rIdx++];
  53.     }
  54.     for (int i = 0; i < help.length; i++) {
  55.         arr[l++] = help[i];
  56.     }
  57.     return mergeCount;
  58. }

荷兰国旗问题引出快排

给定一个数组，小于数组最后一个数的值放左边，等于数组最后一个数的值放中间，大于数组最后一个数的值放右边

  1. public int[] partition(int[] arr) {
  2.     return process(arr, 0, arr.length - 1);
  3. }
  5. public int[] process(int[] arr, int l, int r) {
  6.     if (l > r) {
  7.         return new int[]{-1, -1};
  8.     }
  9.     int idx = l;
  10.     int lessIdx = l - 1;
  11.     int ratherThanIdx = r;
  12.     while (idx < ratherThanIdx) {
  13.         if (arr[idx] == arr[r]) {
  14.             idx++;
  15.         } else if (arr[idx] < arr[r]) {
  16.             swap(arr, idx++, ++lessIdx);
  17.         } else {
  18.             swap(arr, idx, --ratherThanIdx);
  19.         }
  20.     }
  21.     swap(arr, ratherThanIdx, r);
  22.     return new int[]{lessIdx + 1, ratherThanIdx};
  23. }

快排（递归版本）

时间复杂度最好：O(N*logN)，最差：O(N2） 额外空间复杂度最好：O(logN)，最差：O(N)

  1. public void quickSort(int[] arr) {
  2.     if (arr == null || arr.length < 2) {
  3.         return;
  4.     }
  5.     partition(arr, 0, arr.length - 1);
  6. }
  8. public void partition(int[] arr, int l, int r) {
  9.     if (l >= r) {
  10.         return;
  11.     }
  12.     //随机一个数与范围上的最后一个数交换
  13.     int randomIdx = (int) (Math.random() * (r - l + 1)) + l;
  14.     swap(arr, randomIdx, r);
  15.     int[] process = process(arr, l, r);
  16.     partition(arr, l, process[0] - 1);
  17.     partition(arr, process[1] + 1, r);
  18. }
  20. public int[] process(int[] arr, int l, int r) {
  21.     if (l > r) {
  22.         return new int[]{-1, -1};
  23.     }
  24.     if (l == r) {
  25.         return new int[]{l, r};
  26.     }
  27.     int idx = l;
  28.     //小于区域
  29.     int lessIdx = l - 1;
  30.     //大于区域
  31.     int ratherThanIdx = r;
  32.     while (idx < ratherThanIdx) {
  33.         if (arr[idx] == arr[r]) {
  34.             idx++;
  35.         } else if (arr[idx] < arr[r]) {
  36.             swap(arr, idx++, ++lessIdx);
  37.         } else {
  38.             swap(arr, idx, --ratherThanIdx);
  39.         }
  40.     }
  41.     swap(arr, ratherThanIdx, r);
  42.     return new int[]{lessIdx + 1, ratherThanIdx};
  43. }

快排（栈实现版本）

  1. private static class Op {
  2.     private int l;
  3.     private int r;
  5.     public Op(int l, int r) {
  6.         this.l = l;
  7.         this.r = r;
  8.     }
  9. }
  11. public void quickSort2(int[] arr) {
  12.     if (arr == null || arr.length < 2) {
  13.         return;
  14.     }
  15.     Stack<Op> stack = new Stack<>();
  16.     int random = (int) (Math.random() * (arr.length));
  17.     swap(arr, random, arr.length - 1);
  18.     int[] partition = partition(arr, 0, arr.length - 1);
  19.     stack.push(new Op(0, partition[0] - 1));
  20.     stack.push(new Op(partition[1] + 1, arr.length - 1));
  21.     while (!stack.isEmpty()) {
  22.         Op op = stack.pop();
  23.         if (op.l < op.r) {
  24.             random = op.l + (int) (Math.random() * (op.r - op.l + 1));
  25.             swap(arr, random, op.r);
  26.             partition = partition(arr, op.l, op.r);
  27.             stack.push(new Op(op.l, partition[0] - 1));
  28.             stack.push(new Op(partition[1] + 1, op.r));
  29.         }
  30.     }
  31. }
  33. private int[] partition(int[] arr, int l, int r) {
  34.     if (l > r) {
  35.         return new int[]{-1, -1};
  36.     }
  37.     if (l == r) {
  38.         return new int[]{l, r};
  39.     }
  40.     int lIdx = l - 1;
  41.     int rIdx = r;
  42.     int idx = l;
  43.     while (idx < rIdx) {
  44.         if (arr[idx] < arr[r]) {
  45.             swap(arr, idx++, ++lIdx);
  46.         } else if (arr[idx] > arr[r]) {
  47.             swap(arr, idx, --rIdx);
  48.         } else {
  49.             idx++;
  50.         }
  51.     }
  52.     swap(arr, rIdx, r);
  53.     return new int[]{lIdx + 1, rIdx};
  54. }
  56. private void swap(int[] arr, int i, int j) {
  57.     int temp = arr[i];
  58.     arr[i] = arr[j];
  59.     arr[j] = temp;
  60. }

快排（队列实现版本）

  1. private static class Op {
  2.     private int l;
  3.     private int r;
  5.     public Op(int l, int r) {
  6.         this.l = l;
  7.         this.r = r;
  8.     }
  9. }
  11. public static void quickSort3(int[] arr) {
  12.     if (arr == null || arr.length < 2) {
  13.         return;
  14.     }
  15.     Queue<Op> queue = new LinkedList<>();
  16.     int random = (int) (Math.random() * (arr.length));
  17.     swap(arr, random, arr.length - 1);
  18.     int[] partition = partition(arr, 0, arr.length - 1);
  19.     queue.offer(new Op(0, partition[0] - 1));
  20.     queue.offer(new Op(partition[1] + 1, arr.length - 1));
  21.     while (!queue.isEmpty()) {
  22.         Op op = queue.poll();
  23.         if (op.l < op.r) {
  24.             random = op.l + (int) (Math.random() * (op.r - op.l + 1));
  25.             swap(arr, random, op.r);
  26.             partition = partition(arr, op.l, op.r);
  27.             queue.offer(new Op(op.l, partition[0] - 1));
  28.             queue.offer(new Op(partition[1] + 1, op.r));
  29.         }
  30.     }
  31. }
  33. private int[] partition(int[] arr, int l, int r) {
  34.     if (l > r) {
  35.         return new int[]{-1, -1};
  36.     }
  37.     if (l == r) {
  38.         return new int[]{l, r};
  39.     }
  40.     int lIdx = l - 1;
  41.     int rIdx = r;
  42.     int idx = l;
  43.     while (idx < rIdx) {
  44.         if (arr[idx] < arr[r]) {
  45.             swap(arr, idx++, ++lIdx);
  46.         } else if (arr[idx] > arr[r]) {
  47.             swap(arr, idx, --rIdx);
  48.         } else {
  49.             idx++;
  50.         }
  51.     }
  52.     swap(arr, rIdx, r);
  53.     return new int[]{lIdx + 1, rIdx};
  54. }
  56. private void swap(int[] arr, int i, int j) {
  57.     int temp = arr[i];
  58.     arr[i] = arr[j];
  59.     arr[j] = temp;
  60. }

堆排序

  1. // 堆排序额外空间复杂度O(1)
  2. public static void heapSort(int[] arr) {
  3.     if (arr == null || arr.length < 2) {
  4.         return;
  5.     }
  6.     // O(N*logN)
  7. //    for (int i = 0; i < arr.length; i++) { // O(N)
  8. //        heapInsert(arr, i); // O(logN)
  9. //    }
  10.     // O(N)
  11.     for (int i = arr.length - 1; i >= 0; i--) {
  12.         heapify(arr, i, arr.length);
  13.     }
  14.     int heapSize = arr.length;
  15.     // O(N*logN)
  16.     while (heapSize > 0) { // O(N)
  17.         swap(arr, 0, --heapSize); // O(1)
  18.         heapify(arr, 0, heapSize); // O(logN)
  19.     }
  20. }
  22. // arr[index]刚来的数，往上
  23. public void heapInsert(int[] arr, int index) {
  24.     while (arr[index] > arr[(index - 1) / 2]) {
  25.         swap(arr, index, (index - 1) / 2);
  26.         index = (index - 1) / 2;
  27.     }
  28. }
  30. // arr[index]位置的数，能否往下移动
  31. public void heapify(int[] arr, int index, int heapSize) {
  32.     int left = index * 2 + 1; // 左孩子的下标
  33.     while (left < heapSize) { // 下方还有孩子的时候
  34.         // 两个孩子中，谁的值大，把下标给largest
  35.         // 1）只有左孩子，left -> largest
  36.         // 2) 同时有左孩子和右孩子，右孩子的值<= 左孩子的值，left -> largest
  37.         // 3) 同时有左孩子和右孩子并且右孩子的值> 左孩子的值， right -> largest
  38.         int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
  39.         // 父和较大的孩子之间，谁的值大，把下标给largest
  40.         largest = arr[largest] > arr[index] ? largest : index;
  41.         if (largest == index) {
  42.             break;
  43.         }
  44.         swap(arr, largest, index);
  45.         index = largest;
  46.         left = index * 2 + 1;
  47.     }
  48. }
  50. public void swap(int[] arr, int i, int j) {
  51.     int tmp = arr[i];
  52.     arr[i] = arr[j];
  53.     arr[j] = tmp;
  54. }

已知一个几乎有序的数组，请选择一个合适的排序策略，对这个数组进行排序

几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离一定不超过k，k相对于数组长度来说是比较小的

解题思路：时间复杂度O(N*logk) 建立一个大小为k+1 的小根堆，并将堆填充满 然后依次弹出一个再增加一个 没有多余的数添加后依次弹出堆里的数

给定很多线段，每个线段都有两个数[start, end]，表示线段开始位置和结束位置，左右都是闭区间，返回线段最多重合区域中，包含了几条线段

规定： 1）线段的开始和结束位置一定都是整数值 2）线段重合区域的长度必须>=1

解题思路：

  1. 方案一
    • 找出所有线段中开始位置的最小值，结束位置的最大值
    • 从最小值开始依次遍历到最大值，将当前数加0.5，再依次看所有线段有多少经过该点
    • 记录经过点最大的次数就是答案
  2. 方案二
    • 将线段开始位置进行升序排列
    • 准备小根堆，遍历排完序的所有线段
    • 将堆中小于等于当前线段开始位置的数从堆中全部弹出
    • 将当前线段结束位置加入堆中
    • 此时堆中的元素个数就是与当前线段重合的线段数
  1. public int maxCover(int[][] m) {
  2.     Line[] lines = new Line[m.length];
  3.     for (int i = 0; i < m.length; i++) {
  4.         lines[i] = new Line(m[i][0], m[i][1]);
  5.     }
  6.     //先按照每条线段的开始位置进行升序排序
  7.     Arrays.sort(lines, new StartComparator());
  8.     // 小根堆，每一条线段的结尾数值，使用默认的
  9.     PriorityQueue<Integer> heap = new PriorityQueue<>();
  10.     int max = 0;
  11.     //小于等于线段开始位置的数都从堆中弹出，最后将自己结束位置加入堆
  12.     for (int i = 0; i < lines.length; i++) {
  13.         // lines[i] -> cur 在黑盒中，把<=cur.start 东西都弹出
  14.         while (!heap.isEmpty() && heap.peek() <= lines[i].start) {
  15.             heap.poll();
  16.         }
  17.         heap.add(lines[i].end);
  18.         //此时堆中数据的多少就代表该线段与多少线段重合
  19.         max = Math.max(max, heap.size());
  20.     }
  21.     return max;
  22. }
  24. public class Line {
  25.     public int start;
  26.     public int end;
  28.     public Line(int s, int e) {
  29.         start = s;
  30.         end = e;
  31.     }
  32. }
  34. public class StartComparator implements Comparator<Line> {
  35.     @Override
  36.     public int compare(Line o1, Line o2) {
  37.         return o1.start - o2.start;
  38.     }
  39. }

桶排序（计数排序）

一般要求样本是整数，且范围比较窄； 要求有改变，则改动很大

  1. // only for 0~200 value
  2. public static void countSort(int[] arr) {
  3.     if (arr == null || arr.length < 2) {
  4.         return;
  5.     }
  6.     int max = Integer.MIN_VALUE;
  7.     for (int i = 0; i < arr.length; i++) {
  8.         max = Math.max(max, arr[i]);
  9.     }
  10.     int[] bucket = new int[max + 1];
  11.     for (int i = 0; i < arr.length; i++) {
  12.         bucket[arr[i]]++;
  13.     }
  14.     int i = 0;
  15.     for (int j = 0; j < bucket.length; j++) {
  16.         while (bucket[j]-- > 0) {
  17.             arr[i++] = j;
  18.         }
  19.     }
  20. }

基数排序

一般要求样本是10进制的正整数 要求有改变，则改动很大 步骤：

  1. 找出数组中最大的元素，并计算有多少位；如{12, 3, 45, 103, 265}，最大值为265，最大位数3位
  2. 准备10个桶0-9，然后遍历源数组，并取出元素个位数字，然后将数据放入个位数字对应的桶中；如12，个位数为2，则12放入2号桶
  3. 将所有元素都放入桶之后，从0-9遍历10个桶，从每个桶中取出第二步放进去的数据（先进先出）
  4. 然后使用相同的方法（重复2、3步）处理十位、百位、千位……直到处理完最大位数，如果一个数在当前处理的位上没值，则记为0
  1. // only for no-negative value
  2. public static void radixSort(int[] arr) {
  3.     if (arr == null || arr.length < 2) {
  4.         return;
  5.     }
  6.     radixSort(arr, 0, arr.length - 1, maxbits(arr));
  7. }
  9. public static int maxbits(int[] arr) {
  10.     int max = Integer.MIN_VALUE;
  11.     for (int i = 0; i < arr.length; i++) {
  12.         max = Math.max(max, arr[i]);
  13.     }
  14.     int res = 0;
  15.     while (max != 0) {
  16.         res++;
  17.         max /= 10;
  18.     }
  19.     return res;
  20. }
  22. // arr[L..R]排序  ,  最大值的十进制位数digit
  23. public static void radixSort(int[] arr, int L, int R, int digit) {
  24.     final int radix = 10;
  25.     int i = 0, j = 0;
  26.     // 有多少个数准备多少个辅助空间
  27.     int[] help = new int[R - L + 1];
  28.     for (int d = 1; d <= digit; d++) { // 有多少位就进出几次
  29.         // 10个空间
  30.         // count[0] 当前位(d位)是0的数字有多少个
  31.         // count[1] 当前位(d位)是(0和1)的数字有多少个
  32.         // count[2] 当前位(d位)是(0、1和2)的数字有多少个
  33.         // count[i] 当前位(d位)是(0~i)的数字有多少个
  34.         int[] count = new int[radix]; // count[0..9]
  35.         for (i = L; i <= R; i++) {
  36.             // 103  1   3
  37.             // 209  1   9
  38.             j = getDigit(arr[i], d);
  39.             count[j]++;
  40.         }
  41.         for (i = 1; i < radix; i++) {
  42.             count[i] = count[i] + count[i - 1];
  43.         }
  44.         for (i = R; i >= L; i--) {
  45.             j = getDigit(arr[i], d);
  46.             help[count[j] - 1] = arr[i];
  47.             count[j]--;
  48.         }
  49.         for (i = L, j = 0; i <= R; i++, j++) {
  50.             arr[i] = help[j];
  51.         }
  52.     }
  53. }
  55. public static int getDigit(int x, int d) {
  56.     return ((x / ((int) Math.pow(10, d - 1))) % 10);
  57. }