devbox
我家自动化
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构与算法 - 排序算法

作者：我家自动化 | 2024-08-16 22:06:22

赞

踩

数据结构与算法 - 排序算法

一、概述

1. 基于比较的排序算法

算法最好最坏平均空间稳定思想注意事项
冒泡O(n)O(n^2)O(n^2)O(1)Y比较最好情况需要额外判断
选择O(n^2)O(n^2)O(n^2)O(1)N比较交换次数一般少于冒泡
堆O(nlogn)O(nlogn)O(nlogn)O(1)N选择堆排序的辅助性较强，理解前先理解堆的数据结构
插入O(n)O(n^2)O(n^2)O(1)Y比较插入排序对于近乎有序的数据处理速度比较快，复杂度有所下降，可以提前结束
希尔O(nlogn)O(n^2)O(nlogn)O(1)N插入gap序列的构造有多种方式，不同方式处理的数据复杂度可能不同
归并O(nlogn)O(nlogn)O(nlogn)O(n)Y分治需要额外的O(n)的存储空间
快速O(nlogn)O(n^2)O(nlogn)O(logn)N分治快排可能存在最坏情况，需要把枢轴值选取得尽量随机化来缓解最坏情况下的时间复杂度

2. 非比较排序算法

非比较排序算法时间复杂度空间复杂度稳定性
计数排序O(n+k)O(n+k)稳定
桶排序O(n+k)O(n+k)稳定
基数排序O(d*(n+k))O(n+k)稳定

其中，n是数组长度，k是桶长度，d是基数位数。

3. 稳定 vs 不稳定

4. Java中的排序

Arrays.sort

JDK 7 ~ 13中的排序实现

排序目标条件采用算法
int[] long[] float[] double[]size < 47混合插入排序 (pair)
size < 286双基准点快排
有序度低双基准点快排
有序度高归并排序
byte[]size <= 29插入排序
size > 29计数排序
char[] short[]size < 47插入排序
size < 286双基准点快排
有序度低双基准点快排
有序度高归并排序
size > 3200计数排序
Object[]-Djava.util.Arrays.useLegacyMergeSort=true传统归并排序
TimSort(归并 + 插入)

JDK 14~20中的排序实现

排序目标条件采用算法
int[] long[] float[] double[]size < 44 并位于最左侧插入排序
size < 65 并不是最左侧混合插入排序 (pin)
有序度低双基准点快排
递归次数超过 384堆排序
对于整个数组或非最左侧 size > 4096，有序度高归并排序
byte[]size <= 64插入排序
size > 64计数排序
char[] short[]size < 44插入排序
再大双基准点快排
递归次数超过 384计数排序
size > 1750计数排序
Object[]-Djava.util.Arrays.useLegacyMergeSort=true传统归并排序
TimSort
  • 其中，TimSort是用归并 + 二分插入的混合排序算法
  • 值得注意的是从Java 8 开始支持Arrays.parallelSort并行排序
  • 根据最新的提交记录来看JDK 21可能会引入基数排序等优化

二、外部排序

1. 冒泡排序

要点：

  • 每轮冒泡不断地比较相邻的两个元素，如果它们是逆序的，则交换它们的位置
  • 下一轮冒泡，可以调整未排序的右边界，减少不必要的比较

以数组3、2、1的冒泡排序为例，第一轮冒泡

第二轮冒泡

未排序区域内就剩一个元素，结束

优化手段：每次循环时，若能确定更合适的右边界，则可以减少冒泡轮数（x记录最后一次交换的位置）

以数组3、2、1、4、5为例，第一轮结束后记录的x，即为右边界

递归实现

  1. package com.itheima.algorithms.sort;
  2.  
  3. import java.util.Arrays;
  4.  
  5. public class BubbleSort {
  6.  
  7.     private static void bubble(int[] a) {
  8.         helper(a, a.length - 1);
  9.     }
  10.  
  11.     private static void helper(int[] a, int j) {
  12.         if(j == 0) {
  13.             return;
  14.         }
  15.  
  16.         int x = 0;  // 记录最后一次交换的位置
  17.         for(int i = 0; i < j; i++) {
  18.             if(a[i] > a[i + 1]) {
  19.                 int t = a[i];
  20.                 a[i] = a[i + 1];
  21.                 a[i + 1] = t;
  22.                 x = i;
  23.             }
  24.         }
  25.         helper(a, x);
  26.     }
  27.  
  28.     public static void main(String[] args) {
  29.         int[] a = {6, 5, 4, 3, 2, 1};
  30.         System.out.println(Arrays.toString(a));
  31.         bubble(a);
  32.         System.out.println(Arrays.toString(a));
  33.     }
  34. }

非递归实现

  1. package com.itheima.algorithms.sort;
  2.  
  3. import java.util.Arrays;
  4.  
  5. public class BubbleSort {
  6.  
  7.     private static void bubble(int[] a) {
  8.         int j = a.length - 1;
  9.         while(true) {
  10.             int x = 0;
  11.             for(int i = 0; i < j; i++) {
  12.                 if(a[i] > a[i + 1]) {
  13.                     int t = a[i];
  14.                     a[i] = a[i + 1];
  15.                     a[i + 1] = t;
  16.                     x = i;
  17.                 }
  18.             }
  19.             j = x;  // 更新右边界
  20.             if(j == 0) {
  21.                 // 没有发生交换，已经有序
  22.                 break;
  23.             }
  24.         }
  25.     }
  26.  
  27.     public static void main(String[] args) {
  28.         int[] a = {6, 5, 4, 3, 2, 1};
  29.         System.out.println(Arrays.toString(a));
  30.         bubble(a);
  31.         System.out.println(Arrays.toString(a));
  32.     }
  33. }

2. 选择排序

要点：

  • 每一轮选择，找出最大（最小）的元素，并把它交换到合适的位置

以下面的数组选择最大值为例

非递归实现

  1. package com.itheima.algorithms.sort;
  2.  
  3. import java.util.Arrays;
  4.  
  5. public class SelectionSort {
  6.  
  7.     public static void sort(int[] a) {
  8.         // 1. 选择轮数 a.length - 1
  9.         // 2. 交换的索引位置 初始a.length - 1，每次递减
  10.         for(int right = a.length - 1; right >= 0; right--) {
  11.             int max = right;
  12.             for(int i = 0; i < right; i++) {
  13.                 if(a[i] > a[max]) {
  14.                     max = i;
  15.                 }
  16.             }
  17.             if(max != right) {
  18.                 int t = a[max];
  19.                 a[max] = a[right];
  20.                 a[right] = t;
  21.             }
  22.         }
  23.     }
  24.  
  25.     public static void main(String[] args) {
  26.         int[] a = {6, 5, 4, 3, 2, 1};
  27.         System.out.println(Arrays.toString(a));
  28.         sort(a);
  29.         System.out.println(Arrays.toString(a));
  30.     }
  31. }

3. 堆排序

要点：

  • 建立大顶堆
  • 每次将堆顶元素（最大值）交换到末尾，调整堆顶元素，让它重新符合大顶堆特性

建堆

交换，下潜调整

代码实现

  1. package com.itheima.algorithms.sort;
  2.  
  3. import java.util.Arrays;
  4.  
  5. public class HeapSort {
  6.     public static void sort(int[] a) {
  7.         // 建堆
  8.         heapify(a, a.length);
  9.         // 交换，下潜调整
  10.         for (int right = a.length - 1; right > 0; right--) {
  11.             swap(a, 0, right);
  12.             down(a, 0, right);
  13.         }
  14.     }
  15.  
  16.     // 建堆 O(n)
  17.     private static void heapify(int[] array, int size) {
  18.         // 如何找到最后这个非叶子节点  size / 2 - 1
  19.         for (int i = size / 2 - 1; i >= 0; i--) {
  20.             down(array, i, size);
  21.         }
  22.     }
  23.  
  24.     // 下潜
  25.     // leetcode 上数组排序题目用堆排序求解，非递归实现比递归实现大约快 6ms
  26.     // 将 parent 索引处的元素下潜: 与两个孩子较大者交换, 直至没孩子或孩子没它大
  27.     private static void down(int[] array, int parent, int size) {
  28.         while (true) {
  29.             int left = parent * 2 + 1;
  30.             int right = left + 1;
  31.             int max = parent;
  32.             if (left < size && array[left] > array[max]) {
  33.                 max = left;
  34.             }
  35.             if (right < size && array[right] > array[max]) {
  36.                 max = right;
  37.             }
  38.             if (max == parent) { // 没找到更大的孩子
  39.                 break;
  40.             }
  41.             swap(array, max, parent);
  42.             parent = max;
  43.         }
  44.     }
  45.  
  46.     // 交换
  47.     private static void swap(int[] a, int i, int j) {
  48.         int t = a[i];
  49.         a[i] = a[j];
  50.         a[j] = t;
  51.     }
  52.  
  53.     public static void main(String[] args) {
  54.         int[] a = {2, 3, 1, 7, 6, 4, 5};
  55.         System.out.println(Arrays.toString(a));
  56.         sort(a);
  57.         System.out.println(Arrays.toString(a));
  58.     }
  59. }

4. 插入排序

要点：

将数组分为两部分 [0 .. low - 1] [low .. a.length - 1]

  • 左边[0 .. low - 1]是已排序部分
  • 右边[low .. a.length - 1]是未排序部分

每次从未排序区域取出 low 位置的元素，插入到已排序区域

例如，

递归实现

  1. package com.itheima.algorithms.sort;
  2.  
  3. import org.checkerframework.checker.units.qual.A;
  4.  
  5. import java.util.Arrays;
  6.  
  7. public class InsertionSort {
  8.     private static void insertion(int[] a, int low, int high) {
  9.         if(low > high) {
  10.             return;
  11.         }
  12.         int i = low - 1;
  13.         int t = a[low];
  14.         while(i >= 0 && a[i] > t) {  // 没有找到插入位置
  15.             a[i + 1] = a[i];  // 空出插入位置
  16.             i--;
  17.         }
  18.  
  19.         if(i + 1 != low) {
  20.             a[i + 1] = t;
  21.         }
  22.         insertion(a, low + 1, high);
  23.     }
  24.  
  25.     public static void main(String[] args) {
  26.         int[] a = {9, 3, 7, 6, 2, 5, 8, 1, 4};
  27.         System.out.println(Arrays.toString(a));
  28.         insertion(a, 1, a.length - 1);
  29.         System.out.println(Arrays.toString(a));
  30.     }
  31. }

非递归实现

  1. package com.itheima.algorithms.sort;
  2.  
  3. import java.util.Arrays;
  4.  
  5. public class InsertionSort {
  6.  
  7.     public static void sort(int[] a) {
  8.         for(int low = 1; low < a.length; low++) {
  9.             // 将low位置的元素插入到[0 .. low - 1]的已排序区域
  10.             int t = a[low];
  11.             int i = low - 1;
  12.  
  13.             while(i >= 0 && t < a[i]) {
  14.                 a[i + 1] = a[i];
  15.                 i--;
  16.             }
  17.             if(i != low - 1) {
  18.                 a[i + 1] = t;
  19.             }
  20.         }
  21.     }
  22.  
  23.     public static void main(String[] args) {
  24.         int[] a = {9, 3, 7, 6, 2, 5, 8, 1, 4};
  25.         System.out.println(Arrays.toString(a));
  26.         sort(a);
  27.         System.out.println(Arrays.toString(a));
  28.     }
  29. }

5. 希尔排序

要点：

  • 简单的说，就是分组实现插入，每组元素间隙称为gap
  • 每轮排序后gap逐渐变小，直至gap为1完成排序
  • 对插入排序的优化，让元素更快速地交换到最终位置
  • gap初始时通常取数组长度的一半，逐渐减小为之前的一半

下图演示了gap = 4，gap =2，gap = 1的三轮排序前后对比

代码

  1. package com.itheima.algorithms.sort;
  2.  
  3. import java.util.Arrays;
  4.  
  5. public class MergeSortTopDown {
  6.  
  7.     /**
  8.      * 合并有序数组
  9.      * @param a1
  10.      */
  11.     public static void sort(int[] a1) {
  12.         int[] a2 = new int[a1.length];
  13.         split(a1, 0, a1.length - 1, a2);
  14.     }
  15.  
  16.     /**
  17.      * 划分数据
  18.      * @param a1
  19.      * @param left
  20.      * @param right
  21.      */
  22.     private static void split(int[] a1, int left, int right, int[] a2) {
  23.         // 2. 治
  24.         if(left == right) {
  25.             return;
  26.         }
  27.         // 1. 分
  28.         int m = (left + right) >>> 1;
  29.         split(a1, left, m, a2);
  30.         split(a1, m + 1, right, a2);
  31.         // 3. 合
  32.         merge(a1, left, m, m + 1, right, a2);
  33.         System.arraycopy(a2, left, a1, left, right - left + 1);
  34.     }
  35.  
  36.     /**
  37.      *
  38.      * @param a1 原始数组
  39.      * @param i 第一个有序范围
  40.      * @param iEnd
  41.      * @param j 第二个有序范围
  42.      * @param jEnd
  43.      * @param a2 临时数组
  44.      */
  45.     public static void merge(int[] a1, int i, int iEnd, int j, int jEnd, int[] a2) {
  46.         int k = i;
  47.         while(i <= iEnd && j <= jEnd) {
  48.             if(a1[i] < a1[j]) {
  49.                 a2[k] = a1[i];
  50.                 i++;
  51.             } else {
  52.                 a2[k] = a1[j];
  53.                 j++;
  54.             }
  55.             k++;
  56.         }
  57.         // 第二个有序数组的剩余元素
  58.         if(i > iEnd) {
  59.             System.arraycopy(a1, j, a2, k, jEnd -j + 1);
  60.         }
  61.         // 第一个有序数组的剩余元素
  62.         if(j > jEnd) {
  63.             System.arraycopy(a1, i, a2, k, iEnd - i + 1);
  64.         }
  65.     }
  66.  
  67.     public static void main(String[] args) {
  68.         int[] a = {9, 3, 7, 6, 2, 5, 8, 1, 4};
  69.         System.out.println(Arrays.toString(a));
  70.         sort(a);
  71.         System.out.println(Arrays.toString(a));
  72.     }
  73. }

6. 归并排序

6.1 递归实现（自上而下）

要点：

  • 分 - 每次从中间切一刀，处理的数据少一半
  • 治 - 当数据仅剩一个时可以认为有序
  • 合 - 两个有序的结果，可以进行合并排序

代码

  1. package com.itheima.algorithms.sort;
  2.  
  3. import java.util.Arrays;
  4.  
  5. public class MergeSort {
  6.  
  7.     /**
  8.      * 合并有序数组
  9.      * @param a1
  10.      */
  11.     public static void sort(int[] a1) {
  12.         int[] a2 = new int[a1.length];
  13.         split(a1, 0, a1.length - 1, a2);
  14.     }
  15.  
  16.     /**
  17.      * 划分数据
  18.      * @param a1
  19.      * @param left
  20.      * @param right
  21.      */
  22.     private static void split(int[] a1, int left, int right, int[] a2) {
  23.         // 2. 治
  24.         if(left == right) {
  25.             return;
  26.         }
  27.         // 1. 分
  28.         int m = (left + right) >>> 1;
  29.         split(a1, left, m, a2);
  30.         split(a1, m + 1, right, a2);
  31.         // 3. 合
  32.         merge(a1, left, m, m + 1, right, a2);
  33.         System.arraycopy(a2, left, a1, left, right - left + 1);
  34.     }
  35.  
  36.     /**
  37.      *
  38.      * @param a1 原始数组
  39.      * @param i 第一个有序范围
  40.      * @param iEnd
  41.      * @param j 第二个有序范围
  42.      * @param jEnd
  43.      * @param a2 临时数组
  44.      */
  45.     public static void merge(int[] a1, int i, int iEnd, int j, int jEnd, int[] a2) {
  46.         int k = i;
  47.         while(i <= iEnd && j <= jEnd) {
  48.             if(a1[i] < a1[j]) {
  49.                 a2[k] = a1[i];
  50.                 i++;
  51.             } else {
  52.                 a2[k] = a1[j];
  53.                 j++;
  54.             }
  55.             k++;
  56.         }
  57.         // 第二个有序数组的剩余元素
  58.         if(i > iEnd) {
  59.             System.arraycopy(a1, j, a2, k, jEnd -j + 1);
  60.         }
  61.         // 第一个有序数组的剩余元素
  62.         if(j > jEnd) {
  63.             System.arraycopy(a1, i, a2, k, iEnd - i + 1);
  64.         }
  65.     }
  66.  
  67.     public static void main(String[] args) {
  68.         int[] a = {9, 3, 7, 6, 2, 5, 8, 1, 4};
  69.         System.out.println(Arrays.toString(a));
  70.         sort(a);
  71.         System.out.println(Arrays.toString(a));
  72.     }
  73. }

6.2 时间复杂度

两个长度为m和n的链表合并，时间复杂度是m + n

归并，时间复杂度：f(n) = 2f(n / 2) + n， f(1) = c，等价解 f(n) = nlog_2(n) + cn

6.3 非递归排序

  1. package com.itheima.algorithms.sort;
  2.  
  3. import java.util.Arrays;
  4.  
  5. public class MergeSortBottomUp {
  6.     /**
  7.      *
  8.      * @param a1 原始数组
  9.      * @param i 第一个有序范围
  10.      * @param iEnd
  11.      * @param j 第二个有序范围
  12.      * @param jEnd
  13.      * @param a2 临时数组
  14.      */
  15.     public static void merge(int[] a1, int i, int iEnd, int j, int jEnd, int[] a2) {
  16.         int k = i;
  17.         while(i <= iEnd && j <= jEnd) {
  18.             if(a1[i] < a1[j]) {
  19.                 a2[k] = a1[i];
  20.                 i++;
  21.             } else {
  22.                 a2[k] = a1[j];
  23.                 j++;
  24.             }
  25.             k++;
  26.         }
  27.         // 第二个有序数组的剩余元素
  28.         if(i > iEnd) {
  29.             System.arraycopy(a1, j, a2, k, jEnd -j + 1);
  30.         }
  31.         // 第一个有序数组的剩余元素
  32.         if(j > jEnd) {
  33.             System.arraycopy(a1, i, a2, k, iEnd - i + 1);
  34.         }
  35.     }
  36.  
  37.     public static void sort(int[] a1) {
  38.         int n= a1.length;
  39.         int[] a2 = new int[n];
  40.         // width代表有序区间的宽度，取值依次为1、2、4、...
  41.         for(int width = 1; width < n; width *= 2) {
  42.             // [left, right]分别代表待合并区间的左右边界
  43.             for (int left = 0; left < n ; left += 2 * width) {
  44.                 int right = Math.min(left + 2 * width - 1, n - 1);
  45.                 // System.out.printf("width %d [%d, %d] %n", width, left, right);
  46.                 int mid = Math.min(left + width - 1, n - 1);
  47.                 merge(a1, left, mid, mid + 1, right, a2);
  48.             }
  49.             // 从a2复制到a1
  50.             System.arraycopy(a2, 0, a1,0, n);
  51.         }
  52.     }
  53.  
  54.     public static void main(String[] args) {
  55.         int[] a = {8, 3, 6, 2, 5, 7, 1, 4};
  56.         System.out.println(Arrays.toString(a));
  57.         sort(a);
  58.         System.out.println(Arrays.toString(a));
  59.     }
  60. }

7. 归并 + 插入

基本思路：

1. 选择阈值：设定一个阈值（如，32等），当子数组的大小小于该阈值时，使用插入排序进行排序；否则，使用归并排序。

2. 实现过程：

  • 在归并排序的分解阶段，将数组分割为较小的子数组
  • 当子数组的大小达到设定的阈值时，停止递归，使用插入排序对该子数组进行排序
  • 在较大的子数组上继续使用归并排序

3. 优势：

  • 小规模数据使用插入排序速度更快
  • 归并排序保证了整体的O(n log n)性能，但通过在小规模时切换到插入排序可以减少常数因子，提升性能。
  1. package com.itheima.algorithms.sort;
  2.  
  3. import java.util.Arrays;
  4.  
  5. public class MergeInsertionSort {
  6.  
  7.     /**
  8.      * 插入排序
  9.      * @param a
  10.      * @param left
  11.      * @param right
  12.      */
  13.     public static void insertionSort(int[] a, int left, int right) {
  14.         for(int low = left + 1; low <= right; low++) {
  15.             // 将low位置的元素插入到[0 .. low - 1]的已排序区域
  16.             int t = a[low];
  17.             int i = low - 1;
  18.  
  19.             while(i >= left && t < a[i]) {
  20.                 a[i + 1] = a[i];
  21.                 i--;
  22.             }
  23.             if(i != low - 1) {
  24.                 a[i + 1] = t;
  25.             }
  26.         }
  27.     }
  28.  
  29.  
  30.     /**
  31.      * 归并排序
  32.      * @param a1
  33.      */
  34.     public static void sort(int[] a1) {
  35.         int[] a2 = new int[a1.length];
  36.         split(a1, 0, a1.length - 1, a2);
  37.     }
  38.  
  39.     /**
  40.      * 划分数据
  41.      * @param a1
  42.      * @param left
  43.      * @param right
  44.      */
  45.     private static void split(int[] a1, int left, int right, int[] a2) {
  46.         // 2. 治
  47.         // 当子数组的大小小于阈值时，使用插入排序，否则使用归并排序
  48.         if(right - left <= 32) {
  49.             // 插入排序
  50.             insertionSort(a1, left, right);
  51.             return;
  52.         }
  53.         // 1. 分
  54.         int m = (left + right) >>> 1;
  55.         split(a1, left, m, a2);
  56.         split(a1, m + 1, right, a2);
  57.         // 3. 合
  58.         merge(a1, left, m, m + 1, right, a2);
  59.         System.arraycopy(a2, left, a1, left, right - left + 1);
  60.     }
  61.  
  62.     /**
  63.      * 合并有序数组
  64.      * @param a1 原始数组
  65.      * @param i 第一个有序范围
  66.      * @param iEnd
  67.      * @param j 第二个有序范围
  68.      * @param jEnd
  69.      * @param a2 临时数组
  70.      */
  71.     public static void merge(int[] a1, int i, int iEnd, int j, int jEnd, int[] a2) {
  72.         int k = i;
  73.         while(i <= iEnd && j <= jEnd) {
  74.             if(a1[i] < a1[j]) {
  75.                 a2[k] = a1[i];
  76.                 i++;
  77.             } else {
  78.                 a2[k] = a1[j];
  79.                 j++;
  80.             }
  81.             k++;
  82.         }
  83.         // 第二个有序数组的剩余元素
  84.         if(i > iEnd) {
  85.             System.arraycopy(a1, j, a2, k, jEnd -j + 1);
  86.         }
  87.         // 第一个有序数组的剩余元素
  88.         if(j > jEnd) {
  89.             System.arraycopy(a1, i, a2, k, iEnd - i + 1);
  90.         }
  91.     }
  92.  
  93.     public static void main(String[] args) {
  94.         int[] a = {9, 3, 7, 6, 2, 5, 8, 1, 4};
  95.         System.out.println(Arrays.toString(a));
  96.         sort(a);
  97.         System.out.println(Arrays.toString(a));
  98.     }
  99. }

8. 快速排序

单边循环（lomuto分区）要点：

  • 选择最右侧元素作为基准点

  • j 找比基准点小的，i 找比基准点大的，一旦找到，二者进行交换

    • 交换时机：j 找到小的，且与 i 不相等

    • i 找到 >= 基准点元素后，不应自增

  • 最后基准点与 i 交换，i 即为基准点最终索引

例：

i和j都从左边出发向右查找，i找到比基准点4大的5，j找到比基准点小的2，停下来交换

i找到了比基准点大的5，j找到比基准点小的3，停下来交换

j到达right处结束，right与i交换，一轮分区结束

代码：

  1. package com.itheima.algorithms.sort;
  2.  
  3. import java.util.Arrays;
  4.  
  5. /**
  6.  * 单边循环快排（lomuto洛穆托分区方案）
  7.  * 核心思想：每轮找到一个基准点元素，把比他小的放在它左边，比它大的放在它右边，这称为分区
  8.  * 1. 选择最右边的元素作为基准点元素
  9.  * 2. j指针负责找到比基准点小的元素，一旦找到则将j位置的元素与i位置的元素交换
  10.  * 3. i指针指向大于基准点元素的左边界，也是每次交换的目标索引
  11.  * 4. 最后基准点与i位置的元素交换，i即为分区位置
  12.  */
  13. public class QuickSortLomuto {
  14.  
  15.     public static void sort(int[] a) {
  16.         quick(a, 0, a.length - 1);
  17.     }
  18.  
  19.     private static void quick(int[] a, int left, int right) {
  20.         if(left < right) {
  21.             // 进行分区并获取基准元素的最终位置
  22.             int pivotIndex = partition(a, left, right);
  23.             // 递归排序基准元素左边的子数组
  24.             quick(a, left, pivotIndex - 1);
  25.             // 递归排序基准元素右边的子数组
  26.             quick(a, pivotIndex + 1, right);
  27.         }
  28.     }
  29.  
  30.     /**
  31.      * 分区
  32.      * @param a
  33.      * @param left
  34.      * @param right
  35.      */
  36.     private static int partition(int[] a, int left, int right) {
  37.         // 1. 选择最右边的元素作为基准点
  38.         int pivot = a[right];
  39.         // 2. 初始化i指针
  40.         int i = left;
  41.         for(int j = left; j < right; j++) {
  42.             // 3. j 找到比基准元素小的了，交换i和j位置的元素
  43.             if(a[j] < pivot) {
  44.                 if(i != j) {
  45.                     swap(a, i, j);
  46.                 }
  47.                 i++;
  48.             }
  49.         }
  50.         swap(a, i, right);
  51.         return i;
  52.     }
  53.  
  54.     private static void swap(int[] a, int i, int j) {
  55.         int t = a[i];
  56.         a[i] = a[j];
  57.         a[j] = t;
  58.     }
  59.  
  60.  
  61.     public static void main(String[] args) {
  62.         int[] a = {2, 3, 1, 7, 6, 4, 5};
  63.         System.out.println(Arrays.toString(a));
  64.         sort(a);
  65.         System.out.println(Arrays.toString(a));
  66.     }
  67. }

双边循环要点：

  • 选择最左侧元素作为基准点
  • j 找比基准点小的，i 找比基准点大的，一旦找到，二者进行交换
  • i从左到右
  • j从右到左
  • 最后基准点与i交互，i即为基准点最终索引

例：

选择最左侧的4作为基准点，i找到比基准点大的5停下来，j找到比基准点小的1停下来（包含等于），二者交互

i找到8，j找到3，二者交互；i找到7，j找到2，二者交互

i == j，则退出循环，基准点与i位置的元素交互

代码

  1. package com.itheima.algorithms.sort;
  2.  
  3. import java.util.Arrays;
  4.  
  5. public class QuickSortHoare {
  6.  
  7.     public static void sort(int[] a) {
  8.         quick(a, 0, a.length - 1);
  9.     }
  10.  
  11.     private static void quick(int[] a, int left, int right) {
  12.         if (left >= right) {
  13.             return;
  14.         }
  15.         int p = partition(a, left, right);
  16.         quick(a, left, p - 1);
  17.         quick(a, p + 1, right);
  18.     }
  19.  
  20.     /**
  21.      *
  22.      * @param a
  23.      * @param left
  24.      * @param right
  25.      * @return
  26.      */
  27.     private static int partition(int[] a, int left, int right) {
  28.         // i找比基准点大的，j找比基准点小的
  29.         int i = left, j = right;
  30.         int pivot = a[left];
  31.         while(i < j) {
  32.             // 先右侧扫描
  33.             while(i < j && a[j] > pivot) {
  34.                 j--;
  35.             }
  36.             // 后左侧扫描（顺序不能调换）
  37.             while(i < j && pivot >= a[i]) {
  38.                 i++;
  39.             }
  40.             // 一旦找到，二者进行交换
  41.             swap(a, i, j);
  42.         }
  43.         // 最后基准点与i交换，i即为基准点最终索引
  44.         swap(a, left, i);
  45.         return i;
  46.     }
  47.  
  48.     private static void swap(int[] a, int i, int j) {
  49.         int t = a[i];
  50.         a[i] = a[j];
  51.         a[j] = t;
  52.     }
  53.  
  54.     public static void main(String[] args) {
  55.         int[] a = {2, 3, 1, 7, 6, 4, 5};
  56.         System.out.println(Arrays.toString(a));
  57.         sort(a);
  58.         System.out.println(Arrays.toString(a));
  59.     }
  60. }

8.1 随机基准点

使用随机数作为基准点，避免万一最大值或最小值作为基准点导致的分区不平衡

例

改进代码

  1.         // 随机基准点
  2.         int idx = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
  3.         // 将left与idx位置的元素交换
  4.         swap(a, idx, left);

8.2 处理重复值

如果重复值较多，则原来算法中分区效果也不好，如下图中左侧所示，需要想办法改为右侧的分区效果。

改进代码

  1. package com.itheima.algorithms.sort;
  2.  
  3. import java.util.Arrays;
  4. import java.util.concurrent.ThreadLocalRandom;
  5.  
  6. public class QuickSortHandleDuplicate {
  7.  
  8.  
  9.     public static void sort(int[] a) {
  10.         quick(a, 0, a.length - 1);
  11.     }
  12.  
  13.     private static void quick(int[] a, int left, int right) {
  14.         if (left >= right) {
  15.             return;
  16.         }
  17.         int p = partition(a, left, right);
  18.         quick(a, left, p - 1);
  19.         quick(a, p + 1, right);
  20.     }
  21.  
  22.     /**
  23.      * 循环内
  24.      *     i从left + 1开始，从左向右找大的或相等的
  25.      *     j从right开始，从右向左找小的或相等的
  26.      *     交换， i++ j--
  27.      * 循环外，j和基准点交换，j即为分区位置
  28.      * @param a
  29.      * @param left
  30.      * @param right
  31.      * @return
  32.      */
  33.     private static int partition(int[] a, int left, int right) {
  34.         // 随机基准点
  35.         int idx = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
  36.         // 将left与idx位置的元素交换
  37.         swap(a, idx, left);
  38.         // 从left + 1开始
  39.         int i = left + 1, j = right;
  40.         int pivot = a[left];
  41.         while(i <= j) {
  42.             // i从左到右找大的或相等的
  43.             while(i <= j && a[i] < pivot) {
  44.                 i++;
  45.             }
  46.             // j从右到左找小的或者相等的
  47.             while(i <= j && a[j] > pivot) {
  48.                 j--;
  49.             }
  50.  
  51.             if(i <= j) {
  52.                 swap(a, i, j);;
  53.                 i++;
  54.                 j--;
  55.             }
  56.         }
  57.         // 最后基准点与i交换，i即为基准点最终索引
  58.         swap(a, j, left);
  59.         return j;
  60.     }
  61.  
  62.     private static void swap(int[] a, int i, int j) {
  63.         int t = a[i];
  64.         a[i] = a[j];
  65.         a[j] = t;
  66.     }
  67.  
  68.     public static void main(String[] args) {
  69.         int[] a = {2, 3, 1, 7, 6, 4, 5};
  70.         System.out.println(Arrays.toString(a));
  71.         sort(a);
  72.         System.out.println(Arrays.toString(a));
  73.     }
  74. }

8.3 快速排序 + 插入排序

  1. package com.itheima.algorithms.sort;
  2.  
  3. import java.util.Arrays;
  4. import java.util.concurrent.ThreadLocalRandom;
  5.  
  6. public class QuickSortHandleDuplicate {
  7.  
  8.     /**
  9.      * 插入排序
  10.      * @param a
  11.      * @param left
  12.      * @param right
  13.      */
  14.     public static void insertionSort(int[] a, int left, int right) {
  15.         for(int low = left + 1; low <= right; low++) {
  16.             // 将low位置的元素插入到[0 .. low - 1]的已排序区域
  17.             int t = a[low];
  18.             int i = low - 1;
  19.  
  20.             while(i >= left && t < a[i]) {
  21.                 a[i + 1] = a[i];
  22.                 i--;
  23.             }
  24.             if(i != low - 1) {
  25.                 a[i + 1] = t;
  26.             }
  27.         }
  28.     }
  29.  
  30.     /**
  31.      * 快速排序
  32.      * @param a
  33.      */
  34.     public static void sort(int[] a) {
  35.         quick(a, 0, a.length - 1);
  36.     }
  37.  
  38.     private static void quick(int[] a, int left, int right) {
  39.         if (right - left <= 32) {
  40.             insertionSort(a, left, right);
  41.             return;
  42.         }
  43.         int p = partition(a, left, right);
  44.         quick(a, left, p - 1);
  45.         quick(a, p + 1, right);
  46.     }
  47.  
  48.     /**
  49.      * 循环内
  50.      *     i从left + 1开始，从左向右找大的或相等的
  51.      *     j从right开始，从右向左找小的或相等的
  52.      *     交换， i++ j--
  53.      * 循环外，j和基准点交换，j即为分区位置
  54.      * @param a
  55.      * @param left
  56.      * @param right
  57.      * @return
  58.      */
  59.     private static int partition(int[] a, int left, int right) {
  60.         // 随机基准点
  61.         int idx = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
  62.         // 将left与idx位置的元素交换
  63.         swap(a, idx, left);
  64.         // 从left + 1开始
  65.         int i = left + 1, j = right;
  66.         int pivot = a[left];
  67.         while(i <= j) {
  68.             // i从左到右找大的或相等的
  69.             while(i <= j && a[i] < pivot) {
  70.                 i++;
  71.             }
  72.             // j从右到左找小的或者相等的
  73.             while(i <= j && a[j] > pivot) {
  74.                 j--;
  75.             }
  76.  
  77.             if(i <= j) {
  78.                 swap(a, i, j);;
  79.                 i++;
  80.                 j--;
  81.             }
  82.         }
  83.         // 最后基准点与i交换，i即为基准点最终索引
  84.         swap(a, j, left);
  85.         return j;
  86.     }
  87.  
  88.     private static void swap(int[] a, int i, int j) {
  89.         int t = a[i];
  90.         a[i] = a[j];
  91.         a[j] = t;
  92.     }
  93.  
  94.     public static void main(String[] args) {
  95.         int[] a = {2, 3, 1, 7, 6, 4, 5};
  96.         System.out.println(Arrays.toString(a));
  97.         sort(a);
  98.         System.out.println(Arrays.toString(a));
  99.     }
  100. }

性能对比

9. 计数排序

要点

  • 1. 找到最大值，创建一个大小为最大值+1的count数组
  • 2. count数组的索引对应原始数组的元素，用来统计该元素的出现次数
  • 3. 遍历count数组，根据count数组的索引（即原始数组的元素）以及出现次数，生成排序后的内容
  • count数组的索引是：已排序好的
  • 前提：最大值不能太大
  1. package com.itheima.algorithms.sort;
  2.  
  3. import java.util.Arrays;
  4.  
  5. /**
  6.  * 计数排序
  7.  */
  8. public class CountingSort {
  9.  
  10.     /*
  11.         要点
  12.         1. 让原始数组的最小值映射到 count[0] 最大值映射到 count 最右侧
  13.         2. 原始数组元素 - 最小值 = count 索引
  14.         3. count 索引 + 最小值 = 原始数组元素
  15.      */
  16.  
  17.     public static void main(String[] args) {
  18.         int[] a = {5, 1, 1, 3, 0, -1};
  19.         System.out.println(Arrays.toString(a));
  20.         sort(a);
  21.         System.out.println(Arrays.toString(a));
  22.     }
  23.  
  24.  
  25.     // 2N + K         n*log(n)
  26.     /*
  27.         {5, 1, 1, 3, 0, -1}  原始数组 a
  29.         [1   1   2   0   1   0   1 ] count
  30.          0   1   2   3   4   5   6
  31.          -1  0   1       3       5
  32.      */
  33.  
  34.     private static void sort(int[] a) {
  35.         int max = a[0];
  36.         int min = a[0];
  37.         for (int i = 1; i < a.length; i++) {
  38.             if(a[i] > max) {
  39.                 max = a[i];
  40.             }
  41.             if(a[i] < min) {
  42.                 min = a[i];
  43.             }
  44.         }
  45.         int[] count = new int[max - min + 1];
  46.  
  47.         // v原始数组元素 - 最小值 = count索引
  48.         for (int v : a) {
  49.             count[v - min]++;
  50.         }
  51.  
  52.         int k = 0;
  53.         for (int i = 0; i < count.length; i++) {
  54.             // i + min代表原始数组元素，count[i]出现次数
  55.             while(count[i] > 0) {
  56.                 a[k++] = i + min;
  57.                 count[i]--;
  58.             }
  59.         }
  60.     }
  61. }

性能对比

针对byte[]，因为数据范围已知，省去了求最大、最小值的过程，java中对char[]、short[]、byte[]的排序都可能采用counting排序。

  1.     public static void sort(byte[] a) {
  2.         int[] count = new int[256];
  3.         for (int i : a) {
  4.             // 记录每个字节值的出现次数
  5.             // i & 0xFF是为了将byte转换为int类型，这样可以有效地处理负值
  6.             // 因为字节的值范围是-128到127，而count数组的索引应该在0-255之间
  7.             count[i & 0xFF]++;
  8.         }
  9.         // 反向填充排序后的值
  10.         int k = a.length - 1;
  11.         for(int i = 128 + 256; k >= 0; ) {
  12.             // 找到一个计数大于0的字节值
  13.             while (count[--i & 0xFF] == 0);
  14.             int v = i & 0xFF;  // 当前处理的字节值
  15.             int c = count[i & 0xFF];  // 获取当前字节值的计数
  16.             for(int j = 0; j < c; j++) {
  17.                 a[k] = (byte) v;  // 将字节值填充到结果数组的后面
  18.                 k--;
  19.             }
  20.         }
  21.     }

稳定计数排序

  1.     /**
  2.      * 稳定版计数排序
  3.      * @param a
  4.      */
  5.     public static void sort2(int[] a) {
  6.         int min = a[0];
  7.         int max = a[0];
  8.         for (int i : a) {
  9.             if(i > max) {
  10.                 max = i;
  11.             } else if(i < min) {
  12.                 min = i;
  13.             }
  14.         }
  15.         int[] count = new int[max - min + 1];
  16.         for (int i : a) {
  17.             count[i - min]++;
  18.         }
  19.         
  20.         // 累加计数数组 如果count[i] = 5，则表示有5个元素会放在排序数组中i的位置之前
  21.         for (int i = 1; i < count.length; i++) {
  22.             count[i] = count[i] + count[i - 1];
  23.         }
  24.  
  25.         int[] b = new int[a.length];
  26.         for(int i = a.length - 1; i >= 0; i--) {
  27.             // 找到当前元素在计数数组中的索引
  28.             int j = a[i] - min;
  29.             // 减少计数，表示该元素已经放置过了
  30.             count[j]--;
  31.             // 将元素放入结果数组b的正确位置
  32.             b[count[j]] = a[i];
  33.         }
  34.         System.arraycopy(b, 0, a, 0, a.length);
  35.     }

10. 桶排序

初步实现

  1. package com.itheima.algorithms.sort;
  2.  
  3. import com.itheima.datastructure.Array.DynamicArray;
  4.  
  5. import java.util.Arrays;
  6.  
  7. public class BucketSort {
  8.     public static void main(String[] args) {
  9.         int[] ages = {20, 18, 28, 66, 25, 31, 67, 30};  // 假设年龄范围1~99
  10.         System.out.println(Arrays.toString(ages));
  11.         sort(ages);
  12.         System.out.println(Arrays.toString(ages));
  13.     }
  14.  
  15.     /**
  16.      * 桶排序
  17.      * @param ages
  18.      */
  19.     private static void sort(int[] ages) {
  20.         // 1. 准备桶
  21.         DynamicArray[] buckets = new DynamicArray[10];
  22.         for (int i = 0; i < buckets.length; i++) {
  23.             buckets[i] = new DynamicArray();
  24.         }
  25.         // 2. 放入年龄数据
  26.         for (int age : ages) {
  27.             buckets[age / 10].addLast(age);
  28.         }
  29.         int k = 0;
  30.         for (DynamicArray bucket : buckets) {
  31.             // 3. 对桶内元素进行排序
  32.             int[] array = bucket.stream().toArray();
  33.             InsertionSort.sort(array);
  34.             // 4. 把每个桶排序好的内容，依次放回原始数组
  35.             for (int i : array) {
  36.                 ages[k++] = i;
  37.             }
  38.         }
  39.     }
  40. }

通用

  1. package com.itheima.algorithms.sort;
  2.  
  3. import com.itheima.datastructure.Array.DynamicArray;
  4.  
  5. import java.util.Arrays;
  6.  
  7. public class BucketSortGeneric {
  8.  
  9.     public static void main(String[] args) {
  10.         int[] ages = {9, 0, 5, 1, 4, 7, 2, 8};  // 假设年龄范围1~99
  11.         System.out.println(Arrays.toString(ages));
  12.         sort(ages, 20);
  13.         System.out.println(Arrays.toString(ages));
  14.     }
  15.  
  16.     /**
  17.      * 桶排序通用版 - 参考计数排序
  18.      * @param ages
  19.      * @param range
  20.      */
  21.     private static void sort(int[] ages, int range) {
  22.         // 0. 找最大最小值
  23.         int max = ages[0];
  24.         int min = ages[0];
  25.         for (int i = 1; i < ages.length; i++) {
  26.             if (ages[i] > max) {
  27.                 max = ages[i];
  28.             }
  29.             if (ages[i] < min) {
  30.                 min = ages[i];
  31.             }
  32.         }
  33.  
  34.         // 1. 准备桶 c
  35.         // (max - min) / range + 1 减少桶的个数
  36.         DynamicArray[] buckets = new DynamicArray[(max - min) / range + 1];
  37.         for (int i = 0; i < buckets.length; i++) {
  38.             buckets[i] = new DynamicArray();
  39.         }
  40.         // 2. 放入年龄数据
  41.         for (int age : ages) {
  42.             buckets[(age - min) / range].addLast(age);
  43.         }
  44.         int k = 0;
  45.         for (DynamicArray bucket : buckets) {
  46.             // 3. 对桶内元素进行排序
  47.             int[] array = bucket.stream().toArray();
  48.             InsertionSort.sort(array);
  49.             // 4. 把每个桶排序好的内容，依次放回原始数组
  50.             for (int i : array) {
  51.                 ages[k++] = i;
  52.             }
  53.         }
  54.     }
  55. }

11. 基数排序

基数排序（Radix Sort）的核心思路是按位排序，即将数字按位（从最低位到最高位或从最高位到最低位）逐位排序。基数排序通常适用于整数和字符串排序。以下是基数排序的基本步骤和思路：

1. 确定最大位数

  • 首先，基数排序需要知道待排序的最大数字的位数，这可以通过遍历整个数组来完成。例如，对于数组中的最大数max，基数排序只需要处理max的位数。

2. 按位排序

  • 基数排序通过多次（位数个数）使用一个稳定的排序算法（通常是计数排序）来对数字进行排序，以下是逐步的过程：
  • 从最低位开始：首先对每个数字的最低位进行排序，得到的结果是基于该位的排序
  • 接着是次低位：然后对于每个数字的次低位进行排序，虽然这个排序会受到前一次排序结果的影响，但依然是基于该新的位进行的
  • 重复直到最高位：继续这个过程，直到处理到最高位

例如

代码：

  1. package com.itheima.algorithms.sort;
  2.  
  3. import java.util.ArrayList;
  4.  
  5. public class RadixSort {
  6.  
  7.     /**
  8.      * 基数排序
  9.      *
  10.      * @param a 待排序字符串数组
  11.      */
  12.     public static void radixSort(String[] a) {
  13.         // 1. 找出最长字符串的长度
  14.         int maxLength = 0;
  15.         for (String s : a) {
  16.             if (s.length() > maxLength) {
  17.                 maxLength = s.length();
  18.             }
  19.         }
  20.  
  21.         // 2. 准备桶
  22.         ArrayList<String>[] buckets = new ArrayList[128];
  23.         for (int i = 0; i < buckets.length; i++) {
  24.             buckets[i] = new ArrayList<>();
  25.         }
  26.  
  27.         // 3. 从字符串的低位到高位，进行多轮按位桶排序
  28.         for (int i = maxLength - 1; i >= 0; i--) {
  29.             // 根据某一个位的值放入到对应桶
  30.             for (String s : a) {
  31.                 int num = Integer.parseInt(s);
  32.                 if(s.length() < maxLength) {
  33.                     // 处理字符串长度不等的情况
  34.                     s = String.format("%0" + maxLength + "d", num);
  35.                 }
  36.                 buckets[s.charAt(i) - '0'].add(String.valueOf(num));
  37.             }
  38.             int k = 0;
  39.             for (ArrayList<String> bucket : buckets) {
  40.                 // 4. 重新取出排好序的字符串，依次放回原始数组
  41.                 for (String s : bucket) {
  42.                     a[k++] = s;
  43.                 }
  44.                 bucket.clear();
  45.             }
  46.         }
  47.     }
  48.  
  49.     public static void main(String[] args) {
  50.         /*String[] phoneNumbers = new String[10];
  51.         phoneNumbers[0] = "13812345678";
  52.         phoneNumbers[1] = "13912345678";
  53.         phoneNumbers[2] = "13612345678";
  54.         phoneNumbers[3] = "13712345678";
  55.         phoneNumbers[4] = "13512345678";
  56.         phoneNumbers[5] = "13412345678";
  57.         phoneNumbers[6] = "15012345678";
  58.         phoneNumbers[7] = "15112345678";
  59.         phoneNumbers[8] = "15212345678";
  60.         phoneNumbers[9] = "15712345678";*/
  61.  
  62.         String[] phoneNumbers = new String[10];
  63.         phoneNumbers[0] = "138";
  64.         phoneNumbers[1] = "139";
  65.         phoneNumbers[2] = "1068";
  66.         phoneNumbers[3] = "137";
  67.         phoneNumbers[4] = "135";
  68.         phoneNumbers[5] = "14";
  69.         phoneNumbers[6] = "150";
  70.         phoneNumbers[7] = "151";
  71.         phoneNumbers[8] = "162";
  72.         phoneNumbers[9] = "57";
  73.         RadixSort.radixSort(phoneNumbers);
  74.         for (String phoneNumber : phoneNumbers) {
  75.             System.out.print(phoneNumber + " ");
  76.         }
  77.     }
  78. }

三、习题

1. 数组的相对排序

给你两个数组，arr1 和 arr2，arr2 中的元素各不相同，arr2 中的每个元素都出现在 arr1 中。

对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

示例 1：

输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]

示例  2:

输入：arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
输出：[22,28,8,6,17,44]

提示：

  • 1 <= arr1.length, arr2.length <= 1000
  • 0 <= arr1[i], arr2[i] <= 1000
  • arr2 中的元素 arr2[i]  各不相同 
  • arr2 中的每个元素 arr2[i] 都出现在 arr1 中

解法一：计数排序

  1. class Solution {
  2.     public int[] relativeSortArray(int[] arr1, int[] arr2) {
  3.         // 1. 记录每个元素出现的次数
  4.         int[] count = new int[1001];
  5.         for (int i : arr1) {
  6.             count[i]++;
  7.         }
  8.         int[] result = new int[arr1.length];
  9.         int k = 0;
  10.         // 2. 如果元素有在arr2出现，添加到result中
  11.         for (int i : arr2) {
  12.             while (count[i] > 0) {
  13.                 result[k++] = i;
  14.                 count[i]--;
  15.             }
  16.         }
  17.         // 3. 处理不在arr2中的元素
  18.         for (int i = 0; i < count.length; i++) {
  19.             while (count[i] > 0) {
  20.                 result[k++] = i;
  21.                 count[i]--;
  22.             }
  23.         }
  24.         return result;
  25.     }
  26. }

2. 按出现频率排序

给你一个整数数组 nums ，请你将数组按照每个值的频率 升序 排序。如果有多个值的频率相同，请你按照数值本身将它们 降序 排序。 

请你返回排序后的数组。

示例 1：

输入：nums = [1,1,2,2,2,3]
输出：[3,1,1,2,2,2]
解释：'3' 频率为 1，'1' 频率为 2，'2' 频率为 3 。

示例 2：

输入：nums = [2,3,1,3,2]
输出：[1,3,3,2,2]
解释：'2' 和 '3' 频率都为 2 ，所以它们之间按照数值本身降序排序。

示例 3：

输入：nums = [-1,1,-6,4,5,-6,1,4,1]
输出：[5,-1,4,4,-6,-6,1,1,1]

提示：

  • 1 <= nums.length <= 100
  • -100 <= nums[i] <= 100

解法一：计数排序。执行耗时8ms

  1. class Solution {
  2.     public int[] frequencySort(int[] nums) {
  3.         // 1. 记录每个元素出现的次数
  4.         int[] count = new int[201];
  5.         for (int num : nums) {
  6.             // 加100是为了处理num为负数的情况
  7.             count[num + 100]++;
  8.         }
  9.  
  10.         return Arrays.stream(nums).boxed().sorted((a, b) -> {
  11.             int fa = count[a + 100];
  12.             int fb = count[b + 100];
  13.             if(fa == fb) {
  14.                 // 如果频率相同，按照数值本身将它们降序排序
  15.                 return Integer.compare(b, a);
  16.             } else {
  17.                 // 按照每个值的频率升序排序
  18.                 return fa - fb;
  19.             }
  20.         }).mapToInt(Integer::intValue).toArray();
  21.     }
  22. }

解法二：计数排序 + HashMap。执行耗时6ms

  • 使用Map代替固定大小数组
  • 减少计算频率的次数
  • 使用list和Comparator
  1. import java.util.*;  
  2.  
  3. class Solution {  
  4.     public int[] frequencySort(int[] nums) {  
  5.         // 1. 记录每个元素出现的次数  
  6.         Map<Integer, Integer> count = new HashMap<>();  
  7.         
  8.         for (int num : nums) {  
  9.             count.put(num, count.getOrDefault(num, 0) + 1);  
  10.         }  
  11.  
  12.         // 2. 使用 List 存储元素及其频率，方便排序  
  13.         List<Map.Entry<Integer, Integer>> entryList = new ArrayList<>(count.entrySet());  
  14.         
  15.         // 3. 按照频率升序，然后数值降序排序  
  16.         entryList.sort((a, b) -> {  
  17.             if (a.getValue().equals(b.getValue())) {  
  18.                 return Integer.compare(b.getKey(), a.getKey()); // 按数值降序  
  19.             }  
  20.             return Integer.compare(a.getValue(), b.getValue()); // 按频率升序  
  21.         });  
  22.  
  23.         // 4. 构造结果数组  
  24.         int index = 0;  
  25.         for (Map.Entry<Integer, Integer> entry : entryList) {  
  26.             int frequency = entry.getValue();  
  27.             for (int i = 0; i < frequency; i++) {  
  28.                 nums[index++] = entry.getKey();  
  29.             }  
  30.         }  
  31.  
  32.         return nums;  
  33.     }  
  34. }

3. 最大间距

给定一个无序的数组 nums，返回 数组在排序之后，相邻元素之间最大的差值 。如果数组元素个数小于 2，则返回 0 。

您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。(桶排序或基数排序)

示例 1:

输入: nums = [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。

示例 2:

输入: nums = [10]
输出: 0
解释: 数组元素个数小于 2，因此返回 0。

提示:

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^9

解法一：桶排序。超出内存限制

  1. class Solution {
  2.     public int maximumGap(int[] nums) {
  3.         int n = nums.length;
  4.         if (n < 2) {
  5.             return 0;
  6.         }
  7.  
  8.         sort(nums, 1);
  9.  
  10.         int ret = 0;
  11.         for (int i = 1; i < n; i++) {
  12.             ret = Math.max(ret, nums[i] - nums[i - 1]);
  13.         }
  14.         return ret;
  15.     }
  16.  
  17.     public static void sort(int[] nums, int range) {
  18.         int max = nums[0];
  19.         int min = nums[0];
  20.         for (int i = 1; i < nums.length; i++) {
  21.             if (nums[i] > max) {
  22.                 max = nums[i];
  23.             }
  24.             if (nums[i] < min) {
  25.                 min = nums[i];
  26.             }
  27.         }
  28.  
  29.         ArrayList[] buckets = new ArrayList[(max - min) / range + 1];
  30.         for (int i = 0; i < buckets.length; i++) {
  31.             buckets[i] = new ArrayList();
  32.         }
  33.         for (int num : nums) {
  34.             buckets[(num - min) / range].addLast(num);
  35.         }
  36.  
  37.         int k = 0;
  38.         for (ArrayList<Integer> bucket : buckets) {
  39.             // 创建一个新的int数组
  40.             int[] array = new int[bucket.size()];
  41.  
  42.             // 将ArrayList的元素复制到int数组
  43.             for (int i = 0; i < bucket.size(); i++) {
  44.                 array[i] = bucket.get(i);
  45.             }
  46.  
  47.             // 执行插入排序
  48.             insertionSort(array, 0, array.length - 1);
  49.  
  50.             // 将排序后的结果写回nums数组
  51.             for (int a : array) {
  52.                 nums[k++] = a;
  53.             }
  54.         }
  55.     }
  56.  
  57.     public static void insertionSort(int[] nums, int left, int right) {
  58.         for (int low = left + 1; low <= right; low++) {
  59.             int t = nums[low];
  60.             int i = low - 1;
  61.  
  62.             while (i >= left && t < nums[i]) {
  63.                 nums[i + 1] = nums[i];
  64.                 i--;
  65.             }
  66.             if (i != low - 1) {
  67.                 nums[i + 1] = t;
  68.             }
  69.         }
  70.     }
  71. }

解法二：桶排序 - 合理化桶的数量。执行耗时52ms

  1. class Solution {
  2.     public int maximumGap(int[] nums) {
  3.         int n = nums.length;
  4.         if (n < 2) {
  5.             return 0;
  6.         }
  7.  
  8.         sort(nums);
  9.  
  10.         int ret = 0;
  11.         for (int i = 1; i < n; i++) {
  12.             ret = Math.max(ret, nums[i] - nums[i - 1]);
  13.         }
  14.         return ret;
  15.     }
  16.  
  17.     public static void sort(int[] nums) {
  18.         int max = nums[0];
  19.         int min = nums[0];
  20.         for (int i = 1; i < nums.length; i++) {
  21.             if (nums[i] > max) {
  22.                 max = nums[i];
  23.             }
  24.             if (nums[i] < min) {
  25.                 min = nums[i];
  26.             }
  27.         }
  28.  
  29.         // ArrayList[] buckets = new ArrayList[(max - min) / range + 1];
  30.         int range = Math.max((max - min) / (nums.length - 1), 1);
  31.         ArrayList[] buckets = new ArrayList[(max - min) / range + 1];
  32.         for (int i = 0; i < buckets.length; i++) {
  33.             buckets[i] = new ArrayList();
  34.         }
  35.         for (int num : nums) {
  36.             buckets[(num - min) / range].addLast(num);
  37.         }
  38.  
  39.         int k = 0;
  40.         for (ArrayList<Integer> bucket : buckets) {
  41.             // 创建一个新的int数组
  42.             int[] array = new int[bucket.size()];
  43.  
  44.             // 将ArrayList的元素复制到int数组
  45.             for (int i = 0; i < bucket.size(); i++) {
  46.                 array[i] = bucket.get(i);
  47.             }
  48.  
  49.             // 执行插入排序
  50.             insertionSort(array, 0, array.length - 1);
  51.  
  52.             // 将排序后的结果写回nums数组
  53.             for (int a : array) {
  54.                 nums[k++] = a;
  55.             }
  56.         }
  57.     }
  58.  
  59.     public static void insertionSort(int[] nums, int left, int right) {
  60.         for (int low = left + 1; low <= right; low++) {
  61.             int t = nums[low];
  62.             int i = low - 1;
  63.  
  64.             while (i >= left && t < nums[i]) {
  65.                 nums[i + 1] = nums[i];
  66.                 i--;
  67.             }
  68.             if (i != low - 1) {
  69.                 nums[i + 1] = t;
  70.             }
  71.         }
  72.     }
  73. }

解法三：桶排序 - 只保留桶内最大最小值。执行耗时13ms

  1. class Solution {
  2.  
  3.     static class Pair {
  4.         int max = 0;
  5.         int min = 1000_000_000;
  6.  
  7.         public void add(int v) {
  8.             max = Math.max(max, v);
  9.             min = Math.min(min, v);
  10.         }
  11.  
  12.         @Override
  13.         public String toString() {
  14.             return "[" + min + "," + max + "]";
  15.         }
  16.     }
  17.  
  18.     public int maximumGap(int[] nums) {
  19.         // 1. 处理特殊情况
  20.         if (nums.length < 2) {
  21.             return 0;
  22.         }
  23.         // 2. 桶排序
  24.         // 桶个数 (max - min) / range + 1 期望桶个数 nums.length + 1
  25.         // range = (max - min) / nums.length
  26.         int max = nums[0];
  27.         int min = nums[0];
  28.         for (int i = 1; i < nums.length; i++) {
  29.             if (nums[i] > max) {
  30.                 max = nums[i];
  31.             }
  32.             if (nums[i] < min) {
  33.                 min = nums[i];
  34.             }
  35.         }
  36.         if (max == min) {
  37.             return 0;
  38.         }
  39.  
  40.         int range = Math.max(1, (max - min) / nums.length);
  41.         int size = (max - min) / range + 1;
  42.         Pair[] buckets = new Pair[size];
  43.  
  44.         // 2. 放入数据
  45.         for (int num : nums) {
  46.             int idx = (num - min) / range;
  47.             if (buckets[idx] == null) {
  48.                 buckets[idx] = new Pair();
  49.             }
  50.             buckets[idx].add(num);
  51.         }
  52.         // 3. 寻找最大差值
  53.         int r = 0;
  54.         int lastMax = buckets[0].max;
  55.         for (int i = 1; i < buckets.length; i++) {
  56.             Pair pair = buckets[i];
  57.             if (pair != null) {
  58.                 r = Math.max(r, pair.min - lastMax);
  59.                 lastMax = pair.max;
  60.             }
  61.         }
  62.         return r;
  63.     }
  64. }

解法四：基数排序。执行耗时68ms

  1.     public int maximumGap(int[] nums) {
  2.         // 0. 数组长度小于2，直接返回0
  3.         if(nums.length < 2) {
  4.             return 0;
  5.         }
  6.         // 1. 计算数组的最大值
  7.         int max = nums[0];
  8.         for (int num : nums) {
  9.             max = Math.max(num, max);
  10.         }
  11.  
  12.         // 2. 准备10个桶
  13.         ArrayList<Integer>[] buckets = new ArrayList[10];
  14.         for (int i = 0; i < buckets.length; i++) {
  15.             buckets[i] = new ArrayList<>();
  16.         }
  17.  
  18.         // 3. 没超过最大值
  19.         long exp = 1;
  20.         while(max >= exp) {
  21.             for (int num : nums) {
  22.                 buckets[(num / (int) exp % 10)].add(num);
  23.             }
  24.             int k = 0;
  25.             for (ArrayList<Integer> bucket : buckets) {
  26.                 for (Integer i : bucket) {
  27.                     nums[k++] = i;
  28.                 }
  29.                 bucket.clear();
  30.             }
  31.             exp *= 10;
  32.         }
  33.  
  34.         // 4. 求最大间距
  35.         int r = 0;
  36.         for (int i = 1; i < nums.length; i++) {
  37.             r = Math.max(r, nums[i] - nums[i - 1]);
  38.         }
  39.         return r;
  40.     }

4. 排序数组

给你一个整数数组 nums，请你将该数组升序排列。

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

提示：

  • 1 <= nums.length <= 5 * 10^4
  • -5 * 10^4 <= nums[i] <= 5 * 10^4

解法一：单边快排（随机轴值）。执行耗时1918ms

  1. class Solution {
  2.     public static int[] sortArray(int[] nums) {
  3.         quickSort(nums, 0, nums.length - 1);
  4.         return nums;
  5.     }
  6.  
  7.     private static void quickSort(int[] nums, int left, int right) {
  8.         if (left < right) {
  9.             int pivot = partition(nums, left, right);
  10.             quickSort(nums, left, pivot - 1);
  11.             quickSort(nums, pivot + 1, right);
  12.         }
  13.     }
  14.  
  15.     private static int partition(int[] nums, int left, int right) {
  16.         int idx = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
  17.         swap(nums, idx, right);
  18.         int pivot = nums[right];
  19.         int i = left;
  20.         for (int j = left; j < right; j++) {
  21.             if (nums[j] < pivot) {
  22.                 if (i != j) {
  23.                     swap(nums, i, j);
  24.                 }
  25.                 i++;
  26.             }
  27.         }
  28.         swap(nums, i, right);
  29.         return i;
  30.     }
  31.  
  32.     public static void swap(int[] a, int i, int j) {
  33.         int t = a[i];
  34.         a[i] = a[j];
  35.         a[j] = t;
  36.     }
  37. }

解法二：双边快排（随机）。执行耗时1643ms

  1. class Solution {
  2.     public static int[] sortArray(int[] nums) {
  3.         quickSort(nums, 0, nums.length - 1);
  4.         return nums;
  5.     }
  6.  
  7.     private static void quickSort(int[] nums, int left, int right) {
  8.         if (left < right) {
  9.             int pivot = partition(nums, left, right);
  10.             quickSort(nums, left, pivot - 1);
  11.             quickSort(nums, pivot + 1, right);
  12.         }
  13.     }
  14.  
  15.     private static int partition(int[] nums, int left, int right) {
  16.         int idx = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
  17.         swap(nums, idx, left);
  18.         int pivot = nums[left];
  19.         int i = left, j = right;
  20.         while (i < j) {
  21.             while (i < j && nums[j] > pivot) {
  22.                 j--;
  23.             }
  24.             while (i < j && nums[i] <= pivot) {
  25.                 i++;
  26.             }
  27.             swap(nums, i, j);
  28.         }
  29.         swap(nums, left, i);
  30.         return i;
  31.     }
  32.  
  33.     public static void swap(int[] a, int i, int j) {
  34.         int t = a[i];
  35.         a[i] = a[j];
  36.         a[j] = t;
  37.     }
  38. }

解法三：快排（随机 + 重复）。执行耗时26ms

  1. class Solution {
  2.     public static int[] sortArray(int[] nums) {
  3.         quickSort(nums, 0, nums.length - 1);
  4.         return nums;
  5.     }
  6.  
  7.     private static void quickSort(int[] nums, int left, int right) {
  8.         if (left < right) {
  9.             int pivot = partition(nums, left, right);
  10.             quickSort(nums, left, pivot - 1);
  11.             quickSort(nums, pivot + 1, right);
  12.         }
  13.     }
  14.  
  15.     private static int partition(int[] nums, int left, int right) {
  16.         int idx = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
  17.         swap(nums, idx, left);
  18.         int pivot = nums[left];
  19.         int i = left + 1, j = right;
  20.         while (i <= j) {
  21.             while (i <= j && nums[i] < pivot) {
  22.                 i++;
  23.             }
  24.             while (i <= j && nums[j] > pivot) {
  25.                 j--;
  26.             }
  27.             if (i <= j) {
  28.                 swap(nums, i, j);
  29.                 i++;
  30.                 j--;
  31.             }
  32.         }
  33.         swap(nums, j, left);
  34.         return j;
  35.     }
  36.  
  37.     public static void swap(int[] a, int i, int j) {
  38.         int t = a[i];
  39.         a[i] = a[j];
  40.         a[j] = t;
  41.     }
  42. }

解法四：快排（随机 + 重复 + 插入）。执行耗时18ms

  1. class Solution {
  2.     public static int[] sortArray(int[] nums) {
  3.         quickSort(nums, 0, nums.length - 1);
  4.         return nums;
  5.     }
  6.  
  7.     public static void insertionSort(int[] nums, int left, int right) {
  8.         for (int low = left + 1; low <= right; low++) {
  9.             int t = nums[low];
  10.             int i = low - 1;
  11.  
  12.             while (i >= left && t < nums[i]) {
  13.                 nums[i + 1] = nums[i];
  14.                 i--;
  15.             }
  16.             if (i != low - 1) {
  17.                 nums[i + 1] = t;
  18.             }
  19.         }
  20.     }
  21.  
  22.     private static void quickSort(int[] nums, int left, int right) {
  23.         if (right - left <= 32) {
  24.             insertionSort(nums, left, right);
  25.             return;
  26.         }
  27.         int pivot = partition(nums, left, right);
  28.         quickSort(nums, left, pivot - 1);
  29.         quickSort(nums, pivot + 1, right);
  30.     }
  31.  
  32.     private static int partition(int[] nums, int left, int right) {
  33.         int idx = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
  34.         swap(nums, idx, left);
  35.         int pivot = nums[left];
  36.         int i = left + 1, j = right;
  37.         while (i <= j) {
  38.             while (i <= j && nums[i] < pivot) {
  39.                 i++;
  40.             }
  41.             while (i <= j && nums[j] > pivot) {
  42.                 j--;
  43.             }
  44.             if (i <= j) {
  45.                 swap(nums, i, j);
  46.                 i++;
  47.                 j--;
  48.             }
  49.         }
  50.         swap(nums, j, left);
  51.         return j;
  52.     }
  53.  
  54.     public static void swap(int[] a, int i, int j) {
  55.         int t = a[i];
  56.         a[i] = a[j];
  57.         a[j] = t;
  58.     }
  59. }

解法五：计数排序。执行耗时3ms

  1. class Solution {
  2.     public static int[] sortArray(int[] nums) {
  3.         int max = nums[0];
  4.         int min = nums[0];
  5.         for (int i = 1; i < nums.length; i++) {
  6.             if (nums[i] > max) {
  7.                 max = nums[i];
  8.             }
  9.             if (nums[i] < min) {
  10.                 min = nums[i];
  11.             }
  12.         }
  13.         int[] count = new int[max - min + 1];
  14.  
  15.         for (int num : nums) {
  16.             count[num - min]++;
  17.         }
  18.  
  19.         int k = 0;
  20.         for (int i = 0; i < count.length; i++) {
  21.             while (count[i] > 0) {
  22.                 nums[k++] = i + min;
  23.                 count[i]--;
  24.             }
  25.         }
  26.         return nums;
  27.     }
  28. }

5. 排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]

提示：

  • 链表中节点的数目在范围 [0, 5 * 10^4] 内
  • -10^5 <= Node.val <= 10^5

进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

解法一：把链表中的值放入数组当中进行排序，再根据排序后的值创建新的链表返回

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  * int val;
  5.  * ListNode next;
  6.  * ListNode() {}
  7.  * ListNode(int val) { this.val = val; }
  8.  * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  9.  * }
  10.  */
  11. class Solution {
  12.     public ListNode sortList(ListNode head) {
  13.         if (head == null || head.next == null) {
  14.             return head;
  15.         }
  16.  
  17.         List<Integer> values = new ArrayList<>();
  18.         ListNode current = head;
  19.  
  20.         while (current != null) {
  21.             values.add(current.val);
  22.             current = current.next;
  23.         }
  24.         Collections.sort(values);
  25.  
  26.         ListNode newHead = new ListNode(values.get(0));
  27.         ListNode temp = newHead;
  28.  
  29.         for (int i = 1; i < values.size(); i++) {
  30.             temp.next = new ListNode(values.get(i));
  31.             temp = temp.next;
  32.         }
  33.  
  34.         return newHead;
  35.     }
  36. }

解法二：快慢指针 + 合并有序链表（归并）

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  * int val;
  5.  * ListNode next;
  6.  * ListNode() {}
  7.  * ListNode(int val) { this.val = val; }
  8.  * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  9.  * }
  10.  */
  11. class Solution {
  12.     public ListNode sortList(ListNode head) {
  13.         if (head == null || head.next == null) {
  14.             return head;
  15.         }
  16.  
  17.         ListNode mid = findMiddle(head);
  18.         ListNode secondHalf = mid.next;
  19.         mid.next = null;
  20.  
  21.         ListNode sortedFirstHalf = sortList(head);
  22.         ListNode sortedSecondHalf = sortList(secondHalf);
  23.  
  24.         return merge(sortedFirstHalf, sortedSecondHalf);
  25.  
  26.     }
  27.  
  28.     private ListNode merge(ListNode l1, ListNode l2) {
  29.         ListNode dummy = new ListNode(0);
  30.         ListNode current = dummy;
  31.  
  32.         while (l1 != null && l2 != null) {
  33.             if (l1.val < l2.val) {
  34.                 current.next = l1;
  35.                 l1 = l1.next;
  36.             } else {
  37.                 current.next = l2;
  38.                 l2 = l2.next;
  39.             }
  40.             current = current.next;
  41.         }
  42.         current.next = l1 != null ? l1 : l2;
  43.  
  44.         return dummy.next;
  45.     }
  46.  
  47.     private ListNode findMiddle(ListNode head) {
  48.         ListNode slow = head;
  49.         ListNode fast = head.next;
  50.         while (fast != null && fast.next != null) {
  51.             slow = slow.next;
  52.             fast = fast.next.next;
  53.         }
  54.         return slow;
  55.     }
  56. }

6. 数组的相对顺序

给你两个数组，arr1 和 arr2，arr2 中的元素各不相同，arr2 中的每个元素都出现在 arr1 中。

对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

示例 1：

输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]

示例  2:

输入：arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
输出：[22,28,8,6,17,44]

提示：

  • 1 <= arr1.length, arr2.length <= 1000
  • 0 <= arr1[i], arr2[i] <= 1000
  • arr2 中的元素 arr2[i]  各不相同 
  • arr2 中的每个元素 arr2[i] 都出现在 arr1 中

解法一：

  1. class Solution {
  2.     public int[] relativeSortArray(int[] arr1, int[] arr2) {
  3.         // 1. 记录每个元素出现的次数
  4.         int[] count = new int[1001];
  5.         for (int i : arr1) {
  6.             count[i]++;
  7.         }
  8.         int[] result = new int[arr1.length];
  9.         int k = 0;
  10.         // 2. 如果元素有在arr2出现，添加到result中
  11.         for (int i : arr2) {
  12.             while (count[i] > 0) {
  13.                 result[k++] = i;
  14.                 count[i]--;
  15.             }
  16.         }
  17.         // 3. 处理不在arr2中的元素
  18.         for (int i = 0; i < count.length; i++) {
  19.             while (count[i] > 0) {
  20.                 result[k++] = i;
  21.                 count[i]--;
  22.             }
  23.         }
  24.         return result;
  25.     }
  26. }

7. 按照频率将数组升序排序

给你一个整数数组 nums ，请你将数组按照每个值的频率 升序 排序。如果有多个值的频率相同，请你按照数值本身将它们 降序 排序。 

请你返回排序后的数组。

示例 1：

输入：nums = [1,1,2,2,2,3]
输出：[3,1,1,2,2,2]
解释：'3' 频率为 1，'1' 频率为 2，'2' 频率为 3 。

示例 2：

输入：nums = [2,3,1,3,2]
输出：[1,3,3,2,2]
解释：'2' 和 '3' 频率都为 2 ，所以它们之间按照数值本身降序排序。

示例 3：

输入：nums = [-1,1,-6,4,5,-6,1,4,1]
输出：[5,-1,4,4,-6,-6,1,1,1]

提示：

  • 1 <= nums.length <= 100
  • -100 <= nums[i] <= 100

解法一：计数排序

  1. class Solution {
  2.     public int[] frequencySort(int[] nums) {
  3.         // 1. 记录每个元素出现的次数
  4.         int[] count = new int[201];
  5.         for (int num : nums) {
  6.             // 加100是为了处理num为负数的情况
  7.             count[num + 100]++;
  8.         }
  9.  
  10.         return Arrays.stream(nums).boxed().sorted((a, b) -> {
  11.             int fa = count[a + 100];
  12.             int fb = count[b + 100];
  13.             if(fa == fb) {
  14.                 // 如果频率相同，按照数值本身将它们降序排序
  15.                 return Integer.compare(b, a);
  16.             } else {
  17.                 // 按照每个值的频率升序排序
  18.                 return fa - fb;
  19.             }
  20.         }).mapToInt(Integer::intValue).toArray();
  21.     }
  22. }

优化：

  1. import java.util.*;  
  2.  
  3. class Solution {  
  4.     public int[] frequencySort(int[] nums) {  
  5.         // 1. 记录每个元素出现的次数  
  6.         Map<Integer, Integer> count = new HashMap<>();  
  7.         
  8.         for (int num : nums) {  
  9.             count.put(num, count.getOrDefault(num, 0) + 1);  
  10.         }  
  11.  
  12.         // 2. 使用 List 存储元素及其频率，方便排序  
  13.         List<Map.Entry<Integer, Integer>> entryList = new ArrayList<>(count.entrySet());  
  14.         
  15.         // 3. 按照频率升序，然后数值降序排序  
  16.         entryList.sort((a, b) -> {  
  17.             if (a.getValue().equals(b.getValue())) {  
  18.                 return Integer.compare(b.getKey(), a.getKey()); // 按数值降序  
  19.             }  
  20.             return Integer.compare(a.getValue(), b.getValue()); // 按频率升序  
  21.         });  
  22.  
  23.         // 4. 构造结果数组  
  24.         int index = 0;  
  25.         for (Map.Entry<Integer, Integer> entry : entryList) {  
  26.             int frequency = entry.getValue();  
  27.             for (int i = 0; i < frequency; i++) {  
  28.                 nums[index++] = entry.getKey();  
  29.             }  
  30.         }  
  31.  
  32.         return nums;  
  33.     }  
  34. }

8. 计算右侧小于当前元素的个数

给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。

示例 1：

输入：nums = [5,2,6,1]
输出：[2,1,1,0] 
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素

示例 2：

输入：nums = [-1]
输出：[0]

示例 3：

输入：nums = [-1,-1]
输出：[0,0]

提示：

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

解法一：暴力解。超出时间限制

  1. class Solution {
  2.     public List<Integer> countSmaller(int[] nums) {
  3.         List<Integer> counts = new ArrayList<>();
  4.         int n = nums.length;
  5.         for (int i = 0; i < n; i++) {
  6.             int count = 0;
  7.             for (int j = n - 1; j >= i; j--) {
  8.                 if (nums[j] < nums[i]) {
  9.                     count++;
  10.                 }
  11.             }
  12.             counts.add(count);
  13.         }
  14.         return counts;
  15.     }
  16. }

解法二：

  1. class Solution {
  2.     public List<Integer> countSmaller(int[] nums) {
  3.         int n = nums.length;
  4.         List<Integer> res = new ArrayList<>(n);
  5.  
  6.         int[] index = new int[n];
  7.         int[] helper = new int[n];
  8.         int[] count = new int[n];
  9.  
  10.         for (int i = 0; i < n; i++) {
  11.             index[i] = i;
  12.         }
  13.  
  14.         merge(nums, index, helper, count, 0, nums.length - 1);
  15.  
  16.         for (int i = 0; i < n; i++) {
  17.             res.add(i, count[i]);
  18.         }
  19.         return res;
  20.     }
  21.  
  22.     private void merge(int[] nums, int[] index, int[] helper, int[] count, int left, int right) {
  23.         if (left == right || left > right)
  24.             return;
  25.         int mid = (left + right) >> 1;
  26.  
  27.         if (left < mid) {
  28.             merge(nums, index, helper, count, left, mid);
  29.         }
  30.  
  31.         if (mid + 1 < right) {
  32.             merge(nums, index, helper, count, mid + 1, right);
  33.         }
  34.  
  35.         int i = left, j = mid + 1;
  36.         int hi = left;
  37.         while (i <= mid && j <= right) {
  38.             if (nums[index[i]] <= nums[index[j]]) {
  39.                 helper[hi++] = index[j++];
  40.             } else {
  41.                 count[index[i]] += right - j + 1;
  42.                 helper[hi++] = index[i++];
  43.             }
  44.         }
  45.         while (i <= mid) {
  46.             helper[hi++] = index[i++];
  47.         }
  48.  
  49.         while (j <= right) {
  50.             helper[hi++] = index[j++];
  51.         }
  52.  
  53.         for (int k = left; k <= right; k++) {
  54.             index[k] = helper[k];
  55.         }
  56.     }
  57. }

9. 前k个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：

  • 1 <= nums.length <= 10^5
  • k 的取值范围是 [1, 数组中不相同的元素的个数]
  • 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

解法一：HashMap + 小根堆

（图片来自. - 力扣（LeetCode））

  1. public class Solution {
  2.     public int[] topKFrequent(int[] nums, int k) {
  3.         HashMap<Integer, Integer> count = new HashMap<>();
  4.  
  5.         // 1. 使用HashMap统计每个元素出现的次数
  6.         for (int num : nums) {
  7.             count.put(num, count.getOrDefault(num, 0) + 1);
  8.         }
  9.  
  10.         // 2. 使用一个小根堆来维护前k个高频元素
  11.         PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>(k,
  12.                 (a, b) -> a.getValue() - b.getValue());
  13.         for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
  14.             minHeap.offer(entry);
  15.             // 如果堆的大小超过k，移除频率最低的元素，最后剩下的k个元素即为所求
  16.             if (minHeap.size() > k) {
  17.                 minHeap.poll();
  18.             }
  19.         }
  20.  
  21.         // 3. 获取结果
  22.         int i = 0;
  23.         int[] result = new int[k];
  24.         while (!minHeap.isEmpty()) {
  25.             result[i++] = minHeap.poll().getKey();
  26.         }
  27.         return result;
  28.     }
  29. }

解法二：HashMap + 桶排序

  1. class Solution {
  2.     public int[] topKFrequent(int[] nums, int k) {
  3.         HashMap<Integer, Integer> count = new HashMap<>();
  4.         List<Integer> res = new ArrayList<>();
  5.  
  6.         // 1. 使用HashMap统计每个元素出现的次数
  7.         for (int num : nums) {
  8.             count.put(num, count.getOrDefault(num, 0) + 1);
  9.         }
  10.  
  11.         // 2. 将频率作为数组下标，对于出现频率不同的数字集合，存入对应的数组下标
  12.         List<Integer>[] list = new List[nums.length + 1];
  13.         for (Integer key : count.keySet()) {
  14.             int i = count.get(key);
  15.             if (list[i] == null) {
  16.                 list[i] = new ArrayList<>();
  17.             }
  18.             list[i].add(key);
  19.         }
  20.  
  21.         // 3. 倒序遍历数组获取出现频率从大到小的排列
  22.         for (int i = list.length - 1; i >= 0 && res.size() < k; i--) {
  23.             if (list[i] == null) {
  24.                 continue;
  25.             }
  26.             res.addAll(list[i]);
  27.         }
  28.         return res.stream().mapToInt(Integer::intValue).toArray();
  29.     }
  30. }

10. 颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

提示：

  • n == nums.length
  • 1 <= n <= 300
  • nums[i] 为 0、1 或 2

进阶：

  • 你能想出一个仅使用常数空间的一趟扫描算法吗？

解法一：维护三个指针，分别指向当前分析的元素、红色的末尾边界和蓝色的起始边界。

  1. class Solution {
  2.     public void sortColors(int[] nums) {
  3.         int zeroIndex = 0;
  4.         int twoIndex = nums.length - 1;
  5.         int current = 0;
  6.  
  7.         while (current <= twoIndex) {
  8.             if (nums[current] == 0) {
  9.                 // 红色
  10.                 swap(nums, current, zeroIndex);
  11.                 zeroIndex++;
  12.                 current++;
  13.             } else if (nums[current] == 2) {
  14.                 // 蓝色
  15.                 swap(nums, current, twoIndex);
  16.                 twoIndex--;
  17.             } else {
  18.                 // 白色
  19.                 current++;
  20.             }
  21.         }
  22.     }
  23.  
  24.     private void swap(int[] nums, int i, int j) {
  25.         int temp = nums[i];
  26.         nums[i] = nums[j];
  27.         nums[j] = temp;
  28.     }
  29. }

11. 数组中的第k个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：

  • 1 <= k <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

解法一：自定义堆小根堆。执行耗时21ms

  1. class Solution {
  2.     static class MinHeap {
  3.         int[] array;
  4.         int size;
  5.  
  6.         public MinHeap(int capacity) {
  7.             array = new int[capacity];
  8.         }
  9.  
  10.         public int peek() {
  11.             return array[0];
  12.         }
  13.  
  14.         public boolean offer(int offered) {
  15.             if (size == array.length) {
  16.                 return false;
  17.             }
  18.             up(offered);
  19.             size++;
  20.             return true;
  21.         }
  22.  
  23.         public void replace(int replaced) {
  24.             array[0] = replaced;
  25.             down(0);
  26.         }
  27.  
  28.         private void up(int offered) {
  29.             int child = size;
  30.             while (child > 0) {
  31.                 int parent = (child - 1) >> 1;
  32.                 if (offered < array[parent]) {
  33.                     array[child] = array[parent];
  34.                 } else {
  35.                     break;
  36.                 }
  37.                 child = parent;
  38.             }
  39.             array[child] = offered;
  40.         }
  41.  
  42.         private void down(int parent) {
  43.             int left = (parent << 1) + 1;
  44.             int right = left + 1;
  45.             int min = parent;
  46.             if (left < size && array[left] < array[min]) {
  47.                 min = left;
  48.             }
  49.             if (right < size && array[right] < array[min]) {
  50.                 min = right;
  51.             }
  52.             if (min != parent) {
  53.                 swap(min, parent);
  54.                 down(min);
  55.             }
  56.         }
  57.  
  58.         // 交换两个索引处的元素
  59.         private void swap(int i, int j) {
  60.             int t = array[i];
  61.             array[i] = array[j];
  62.             array[j] = t;
  63.         }
  64.     }
  65.  
  66.     public int findKthLargest(int[] nums, int k) {
  67.         MinHeap heap = new MinHeap(k);
  68.         // 先将k个元素入堆
  69.         for (int i = 0; i < k; i++) {
  70.             heap.offer(nums[i]);
  71.         }
  72.         // 将剩余的元素与堆顶元素比较，如果比堆顶元素大则替换。比较完成后，堆顶元素即为第k大的元素（小根堆）
  73.         for (int i = k; i < nums.length; i++) {
  74.             if (nums[i] > heap.peek()) {
  75.                 heap.replace(nums[i]);
  76.             }
  77.         }
  78.  
  79.         return heap.peek();
  80.     }
  81. }

解法二：堆排序（优先队列）。执行耗时63ms

  1. class Solution {
  2.     public int findKthLargest(int[] nums, int k) {
  3.         PriorityQueue<Integer> minHeap = new PriorityQueue<>();
  4.         for (int num : nums) {
  5.             minHeap.offer(num);
  6.             if(minHeap.size() > k) {
  7.                 minHeap.poll();
  8.             }
  9.         }
  10.         return minHeap.peek();
  11.     }
  12. }

解法三：快排（随机 + 处理重复 + 插入）。执行耗时28ms

  1. class Solution {
  2.  
  3.     public int findKthLargest(int[] nums, int k) {
  4.         quickSort(nums, 0, nums.length - 1);
  5.         return nums[nums.length - k];
  6.     }
  7.  
  8.     private static void quickSort(int[] nums, int left, int right) {
  9.         if (right - left <= 32) {
  10.             insertionSort(nums, left, right);
  11.             return;
  12.         }
  13.         int pivot = partition(nums, left, right);
  14.         ;
  15.         quickSort(nums, left, pivot - 1);
  16.         quickSort(nums, pivot + 1, right);
  17.     }
  18.  
  19.     private static int partition(int[] nums, int left, int right) {
  20.         int idx = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
  21.         swap(nums, idx, left);
  22.         int i = left + 1, j = right;
  23.         int pivot = nums[left];
  24.  
  25.         while (i <= j) {
  26.             while (i <= j && nums[i] < pivot) {
  27.                 i++;
  28.             }
  29.             while (i <= j && nums[j] > pivot) {
  30.                 j--;
  31.             }
  32.             if (i <= j) {
  33.                 swap(nums, i, j);
  34.                 i++;
  35.                 j--;
  36.             }
  37.         }
  38.         swap(nums, j, left);
  39.         return j;
  40.     }
  41.  
  42.     private static void insertionSort(int[] nums, int left, int right) {
  43.         for (int low = left + 1; low <= right; low++) {
  44.             int t = nums[low];
  45.             int i = low - 1;
  46.             while (i >= left && t < nums[i]) {
  47.                 nums[i + 1] = nums[i];
  48.                 i--;
  49.             }
  50.             if (i != low - 1) {
  51.                 nums[i + 1] = t;
  52.             }
  53.         }
  54.     }
  55.  
  56.     private static void swap(int[] nums, int i, int j) {
  57.         int temp = nums[i];
  58.         nums[i] = nums[j];
  59.         nums[j] = temp;
  60.     }
  61. }

12. 翻转对

给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。

你需要返回给定数组中的重要翻转对的数量。

示例 1:

输入: [1,3,2,3,1]
输出: 2

示例 2:

输入: [2,4,3,5,1]
输出: 3

注意:

  1. 给定数组的长度不会超过50000。
  2. 输入数组中的所有数字都在32位整数的表示范围内。

解法一：归并排序

  1. class Solution {
  2.     public int reversePairs(int[] nums) {
  3.         if (nums == null || nums.length < 2) {
  4.             return 0;
  5.         }
  6.         return mergeSort(nums, 0, nums.length - 1);
  7.     }
  8.  
  9.     private int mergeSort(int[] nums, int left, int right) {
  10.         if (left >= right) {
  11.             return 0;
  12.         }
  13.         int mid = left + (right - left) / 2;
  14.  
  15.         // 统计左半部分和右半部分的翻转对
  16.         int count = mergeSort(nums, left, mid) + mergeSort(nums, mid + 1, right);
  17.         // 统计跨越两部分的翻转对数量
  18.         count += countImportantPairs(nums, left, mid, right);
  19.         // 合并两个部分
  20.         merge(nums, left, mid, right);
  21.  
  22.         return count;
  23.     }
  24.  
  25.     private void merge(int[] nums, int left, int mid, int right) {
  26.         int[] temp = new int[right - left + 1];
  27.         int i = left, j = mid + 1, k = 0;
  28.  
  29.         while (i <= mid && j <= right) {
  30.             if (nums[i] <= nums[j]) {
  31.                 temp[k++] = nums[i++];
  32.             } else {
  33.                 temp[k++] = nums[j++];
  34.             }
  35.         }
  36.  
  37.         while (i <= mid) {
  38.             temp[k++] = nums[i++];
  39.         }
  40.  
  41.         while (j <= right) {
  42.             temp[k++] = nums[j++];
  43.         }
  44.         System.arraycopy(temp, 0, nums, left, temp.length);
  45.     }
  46.  
  47.     private int countImportantPairs(int[] nums, int left, int mid, int right) {
  48.         int count = 0;
  49.         int j = mid + 1;
  50.  
  51.         // 使用双指针法，j 代表右边数组的指针
  52.         for (int i = left; i <= mid; i++) {
  53.             // 转换为long处理超出Integer.MAX_VALUE -> 2147483647的情况
  54.             while (j <= right && (long) nums[i] > 2 * (long) nums[j]) {
  55.                 j++;
  56.             }
  57.             // 当前 j 的位置表示 (mid + 1) 到 j - 1 都和 nums[i] 满足条件
  58.             count += (j - (mid + 1));
  59.         }
  60.         return count;
  61.     }
  62. }

13. 通过删除字母匹配到字典里最长单词

给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。

如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。

示例 1：

输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
输出："apple"

示例 2：

输入：s = "abpcplea", dictionary = ["a","b","c"]
输出："a"

提示：

  • 1 <= s.length <= 1000
  • 1 <= dictionary.length <= 1000
  • 1 <= dictionary[i].length <= 1000
  • s 和 dictionary[i] 仅由小写英文字母组成

解法一：

1. 检查子序列：通过遍历字典中的每个字符串，检查它是否是s中的一个子序列

2. 比较长度和字典序：对于所有符合条件的字符串，选择最长的一个。如果有多个长度相同的字符串，则选择字典序较小的那个

  1.     public String findLongestWord(String s, List<String> dictionary) {
  2.         String result = "";
  3.  
  4.         for (String word : dictionary) {
  5.             if(isSubsequence(word, s)) {
  6.                 // 比较长度和字典序
  7.                 if(word.length() > result.length() || (word.length() == result.length() && word.compareTo(result) < 0))  {
  8.                     result = word;
  9.                 }
  10.             }
  11.         }
  12.  
  13.         return result;
  14.     }
  15.  
  16.     /**
  17.      * 检查字典中的每个字符串是否为s的一个子序列
  18.      * @param word
  19.      * @param s
  20.      * @return
  21.      */
  22.     private boolean isSubsequence(String word, String s) {
  23.         int wIndex = 0, sIndex = 0;
  24.         while(wIndex < word.length() && sIndex < s.length()) {
  25.             if(word.charAt(wIndex) == s.charAt(sIndex)) {
  26.                 wIndex++;
  27.             }
  28.             sIndex++;
  29.         }
  30.  
  31.         return wIndex == word.length();
  32.     }

14. 有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums 已按 非递减顺序 排序

进阶：

  • 请你设计时间复杂度为 O(n) 的算法解决本问题

解法一：双指针法。大的元素添加到结果数组末尾

  1. class Solution {
  2.     public int[] sortedSquares(int[] nums) {
  3.         int n = nums.length;
  4.         int[] result = new int[n];
  5.         // 双指针法
  6.         int left = 0, right = n - 1;
  7.         int position = n - 1;
  8.  
  9.         while (left <= right) {
  10.             int leftSquare = nums[left] * nums[left];
  11.             int rightSquare = nums[right] * nums[right];
  12.  
  13.             // 大的添加到结果数组
  14.             if (leftSquare > rightSquare) {
  15.                 result[position--] = leftSquare;
  16.                 left++;
  17.             } else {
  18.                 result[position--] = rightSquare;
  19.                 right--;
  20.             }
  21.         }
  22.         return result;
  23.     }
  24. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/990052
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号