1. 三种比较方法
1. equals 方法
用途: 用于比较两个对象是否“相等”。
定义:
equals是Object类中的一个方法，所有类都继承自Object，因此所有对象都有equals方法。默认行为: 默认情况下，
equals方法比较的是两个对象的引用是否相同（即是否指向同一个内存地址）。重写: 通常需要根据业务逻辑重写
equals方法，以比较对象的内容是否相等。
2. Comparable 接口
用途: 用于定义对象的自然排序顺序。
定义:
Comparable是一个接口，包含一个方法compareTo。实现: 类实现
Comparable接口后，必须实现compareTo方法，该方法返回一个整数，表示当前对象与传入对象的比较结果。返回负数表示当前对象小于传入对象。
返回零表示两者相等。
返回正数表示当前对象大于传入对象。
3. Comparator 接口
用途: 用于定义对象的外部排序顺序，尤其是在无法修改类本身或需要多种排序方式时使用。
定义:
Comparator是一个接口，包含一个方法compare。实现: 通常通过匿名类或Lambda表达式实现
Comparator接口，compare方法返回一个整数，表示两个对象的比较结果。返回负数表示第一个对象小于第二个对象。
返回零表示两者相等。
返回正数表示第一个对象大于第二个对象。
| 特性 | equals |
Comparable |
Comparator |
|---|---|---|---|
| 作用 | 比较对象是否相等 | 定义对象的自然排序规则 | 定义对象的外部排序规则 |
| 接口/方法 | equals 方法 |
Comparable 接口，compareTo 方法 |
Comparator 接口，compare 方法 |
| 使用场景 | 判断对象是否逻辑相等 | 定义默认排序规则 | 定义自定义排序规则 |
| 灵活性 | 只能判断是否相等 | 只能定义一种排序规则 | 可以定义多种排序规则 |
| 示例 | p1.equals(p2) |
p1.compareTo(p2) |
comparator.compare(p1, p2) |
2. 排序的概念
| 特性 | 内部排序 | 外部排序 |
|---|---|---|
| 数据存储位置 | 内存 | 外部存储设备（如硬盘） |
| 数据量 | 较小，能够完全加载到内存中 | 较大，无法完全加载到内存中 |
| 常见算法 | 快速排序、归并排序、堆排序等 | 多路归并排序、置换选择排序等 |
| 适用场景 | 小规模数据排序 | 大规模数据排序 |
3. 常⻅排序算法的实现
1. 插入排序
每次从未排序的部分取出一个元素，将其插入到已排序部分的正确位置。
1. 直接插入排序
1. 插入排序的基本思想
将数组分为两部分：
已排序部分：初始时只包含第一个元素。
未排序部分：包含剩余的元素。
每次从未排序部分取出一个元素，将其插入到已排序部分的正确位置。
重复上述过程，直到所有元素都被插入到已排序部分。
2. 插入排序的步骤
从第二个元素开始，依次遍历数组。
将当前元素与已排序部分的元素从后向前比较。
如果当前元素小于已排序部分的元素，则将已排序部分的元素向后移动一位。
找到合适的位置后，插入当前元素。
重复上述过程，直到所有元素都被插入到正确的位置。
最好情况：数组已经有序，时间复杂度为 O(n)。
最坏情况：数组逆序，时间复杂度为 O(n²)。
平均情况：时间复杂度为 O(n²)。
插入排序是 原地排序，不需要额外的存储空间。
public void insertSort(int[] array){
if(array==null){
return;
}
for(int i = 1;i<array.length;i++){
// int cur = i;//保存i位置
int data = array[i];//保存i位置的元素
int j = i-1;// 用于遍历已排序的部分，从当前元素的前一个元素开始。
for(;j>=0;j--){
//如果当前值小于data，跳出循环
if(data>array[j]){
break;
}
array[j+1]=array[j];//则将 array[j] 向后移动一个位置，为 data 腾出存放空间。
}
//将data插入到正确位置
array[j+1]=data;
}
}2. 希尔排序
希尔排序（Shell Sort）是一种插入排序的改进版本，也被称为“缩小增量排序”（Diminishing Increment Sort），因为它通过引入间隔（gap）的概念来对数组进行分组，然后在这些分组内进行插入排序。随着算法的进行，间隔逐渐减小，直到为 1，最终整个数组变为有序。
希尔排序的步骤
选择间隔序列：首先选择一个间隔序列，例如
{n/2, n/4, ..., 1}，其中n是数组的长度。分组排序：对于每个间隔
gap，将数组分成若干组，每组包含间隔为gap的元素。对每组元素进行直接插入排序。减小间隔：减小间隔，重复步骤2，直到间隔为1。
完成排序：当间隔为1时，整个数组只包含一个组，此时对其进行插入排序，算法结束。
希尔排序的时间复杂度：
希尔排序的时间复杂度取决于增量序列的选择。
最坏情况下，时间复杂度为 O(n²)。
对于某些增量序列（如 Hibbard 序列、Sedgewick 序列），时间复杂度可以降低到 O(n^(3/2)) 或 O(n^(4/3))。
平均情况下，时间复杂度为 O(n log n)。
希尔排序的空间复杂度： O(1)
希尔排序是 原地排序，不需要额外的存储空间。
public void shellSort(int[] array) {
if(array==null){
return;
}
int gap = array.length;
while(gap>1){
gap /=2;//寻找间隔
for(int i= gap;i<array.length;i++){
int data = array[i];//待插入元素
int j=i-gap;//用于遍历已排序的部分，从当前元素的前gap元素开始。
for(;j>=0;j-=gap){
//如果当前值小于data，跳出循环
if(array[j]<data){
break;
}
array[j+gap] = array[j];//将 array[j] 向后移动gap个位置，为 data 腾出存放空间。
}
array[j+gap] = data;//插入data
}
}
}
2. 选择排序
1. 标准选择排序
也称单向选择排序，不适合处理大规模数据
1. 选择排序的基本思想
将数组分为两部分：
已排序部分：初始时为空。
未排序部分：初始时为整个数组。
每次从未排序部分中选择最小（或最大）的元素，将其与未排序部分的第一个元素交换。
重复上述过程，直到所有元素都被排序。
2. 选择排序的步骤
从数组的第一个元素开始，依次遍历数组。
在未排序部分中找到最小元素的索引。
将最小元素与未排序部分的第一个元素交换。
将未排序部分的起始位置向后移动一位。
重复上述过程，直到所有元素都被排序
选择排序的时间复杂度
最好情况：时间复杂度为 O(n²)。
最坏情况：时间复杂度为 O(n²)。
平均情况：时间复杂度为 O(n²)。
无论数组是否有序，选择排序都需要进行 n(n-1)/2 次比较。
空间复杂度为 O(1)
选择排序是 原地排序，不需要额外的存储空间。
选择排序的稳定性：不稳定
public void selectSort(int[] array){
if(array==null){
return;
}
for(int i=0;i<array.length;i++){
int min = i;//假设i为最小值下标
for(int j=i+1;j<array.length;j++){
//寻找最小值
if(array[min]>array[j]){
min = j;
}
}
swap(array,i,min);//将最小值与i下标值进行交换
}
}2. 双向选择排序
双向选择排序的步骤
初始化两个指针：
left指向数组的起始位置，right指向数组的末尾位置。在每一轮排序中：
找到
[left, right]范围内的最小值和最大值。将最小值放到
left位置，将最大值放到right位置。
缩小排序范围：
left++，right--。重复上述过程，直到
left >= right。
双向选择排序的时间复杂度
最好情况：时间复杂度为 O(n²)。
最坏情况：时间复杂度为 O(n²)。
平均情况：时间复杂度为 O(n²)。
稳定性： 不稳定排序
public void bidSelectSort(int[] array){
if(array==null){
return;
}
for(int i=0;i<array.length;i++){
int min = i;
int end = array.length-i-1;
int max = end;
for(int j=i;j<=end;j++){
if(array[min]>array[j]){
min = j;
}
if(array[max]<array[j]){
max = j;
}
}
swap(array,i,min);
//如果max在i位置，此时i位置的值已被交换
if(max == i){
max = min;
}
swap(array,max,end);
}
}3. 堆排序
是一种基于 二叉堆 数据结构的排序算法。它利用堆的性质（最大堆或最小堆）来实现排序。
注意：排升序要建⼤堆，排降序建⼩堆。
堆排序的步骤
构建最大堆：将待排序数组转化为最大堆，即从最后一个非叶子节点开始，逐个节点调整为最大堆。
交换堆顶元素：将堆顶的最大元素与数组的最后一个元素交换，使最大元素放到正确的位置上。
调整堆：把堆的范围缩小1个，将剩余的元素重新调整为最大堆，即将堆顶元素进行下沉调整。
重复：重复步骤2和步骤3，直到堆的大小为 1，数组有序。
堆排序的时间复杂度
构建最大堆：时间复杂度为 O(n)。
排序：每次调整堆的时间复杂度为 O(log n)，共需要调整 n-1 次，因此时间复杂度为 O(n log n)。
总时间复杂度为 O(n log n)。
堆排序是 原地排序，不需要额外的存储空间
堆排序的稳定性：不稳定
因为在交换堆顶元素和堆尾元素时，可能会改变相等元素的相对顺序。
public void priorityQueueSort(int[] array){
if(array==null){
return;
}
//创建大堆
for(int parent = (array.length-2)/2;parent>=0;parent--){
priorityQueue(array,parent,array.length);
}
//排序
int last=array.length-1;
while (last>0){
//交换头尾元素
swap(array,0,last);
priorityQueue(array,0,last--);
}
}
//向下调整
private void priorityQueue(int[] array,int parent,int size){
int child = parent*2+1;//左孩子
while(child<size){
//比较两个子孩子的大小
if(child+1<size&&array[child]<array[child+1]){
child +=1;
}
//比较父子大小
if(array[parent]<array[child]){
swap(array,parent,child);
parent = child;//更新父亲节点
child = parent*2+1;//更新孩子节点
}else{//大堆，跳出循环
break;
}
}
}3. 交换排序
通过 相邻元素的比较和交换，将最大（或最小）的元素逐步移动到正确的位置
1. 冒泡排序
冒泡排序的步骤
从数组的第一个元素开始，依次遍历数组。
比较相邻的两个元素，如果顺序不正确，则交换它们，从开始第一对到结尾的最后一对。
每完成一轮遍历，最大的元素会被移动到数组的末尾。
缩小遍历范围（-1），
重复上述过程1，2，3，4，直到整个数组有序。
冒泡排序的时间复杂度
最好情况：数组已经有序，时间复杂度为 O(n)。
最坏情况：数组逆序，时间复杂度为 O(n²)。
平均情况：时间复杂度为 O(n²)。
空间复杂度为 O(1)
冒泡排序是 原地排序，不需要额外的存储空间。
稳定性:稳定
public void bubbleSort(int[] array){
if(array==null){
return;
}
for(int i =0;i<array.length-1;i++){
boolean flg = false;
for(int j=1;j<array.length-i;j++){
if(array[j]<array[j-1]){
swap(array,j,j-1);
flg = true;
}
}
//如果数组已经有序
if(flg==false){
return;
}
}
}2. 快速排序
a[key] ）与 a[left] （此时left == right ）交换时， a[left]比基准值大。
//快速排序
public void quickSort(int[] array){
if(array==null){
return;
}
sort(array,0,array.length-1);
}
//排序
private void sort(int[] array,int begin,int end){
if (begin >= end) {
return; // 递归终止条件
}
int basis = partition(array,begin,end);// 获取基准元素的位置
sort(array,begin,basis-1);// 递归排序左半部分
sort(array,basis+1,end);// 递归排序右半部分
}1. hoare法
hoare排序的步骤
选择基准值：选择子数组的第一个元素作为基准值（
keyi），并将keyi的索引保存在keyi变量中。分区操作：使用两个指针
begin和end，分别从数组的左右两端开始扫描。end指针从右向左移动，直到找到一个小于或等于基准值的元素。同时，begin指针从左向右移动，直到找到一个大于等于基准值的元素。如果begin和end没有相遇（即begin < end），则交换a[begin]和a[end]的值，然后继续移动指针。这个过程会一直进行，直到begin和end相遇或交错。当begin和end相遇时，将基准值（即a[keyi]）与a[begin]（此时begin == end）交换，这样基准值就被放到了它最终应该在的位置。递归排序：对基准值左边的子数组（
left到keyi-1）和右边的子数组（keyi+1到right）分别递归调用Quicksort函数进行排序
时间复杂度：
平均情况：O(n log n)
最坏情况：O(n^2)（当数组已经有序或所有元素相等时）
空间复杂度：
O(log n)（递归栈的深度）
// 分区(hoare）
private int partition1(int[] array,int left,int right){
int start = left;// 基准元素的位置
while(left<right){
// 从右向左找到第一个小于基准的元素
while(right>left && array[right]>=array[start]){
right--;
}
// 从左向右找到第一个大于基准的元素
while(left<right && array[left]<=array[start]){
left++;
}
swap(array,left,right);
}
swap(array,start,left); // 将基准元素放到正确的位置
return left;// 返回基准元素的最终位置
}2. 挖坑法
挖坑法的步骤
选择基准元素（通常选择数组的第一个元素、最后一个元素或中间元素），并将其值保存到一个临时变量中（相当于“挖坑”）。
右指针向左移动，找到第一个小于基准元素的值，将其填入左指针的位置（相当于“填坑”）。
左指针向右移动，找到第一个大于基准元素的值，将其填入右指针的位置（相当于“填坑”）。
重复上述过程，直到左指针和右指针相遇。
将基准元素放入相遇的位置（相当于“填最后一个坑”）。
//分区（挖坑法）
private int partition(int[] array,int left,int right){
int data = array[left];//存放基准值
while(left<right){
// 从右向左找到第一个小于基准的元素
while(right>left&&array[right]>=data){
right--;
}
array[left]=array[right];//将小于基准元素的值放入左坑
// 从左向右找到第一个大于基准的元素
while (left<right&&array[left]<=data){
left++;
}
array[right]=array[left];//将大于基准基准元素的值放入右坑
}
array[left]=data;//将基准值放入正确位置
return left;//返回基准元素位置
}3. 前后指针
前后指针法的步骤
选择基准元素：
选择数组中的一个元素作为基准（例如，最后一个元素）。
将基准元素的值保存到一个临时变量中。
初始化指针：
前指针
prev初始化为数组的第一个元素。后指针
curr初始化为prev+1。
遍历数组：
从
cur开始遍历数组，直到cur到达 end（即数组的末尾）。如果
cur指向的元素小于基准元素key：将
prev指针向后移动一位。交换
prev和cur指针指向的元素。
无论是否交换，
cur指针都向后移动一位。
放置基准元素：
遍历结束后，将基准元素
key放到prev + 1的位置。此时，
prev + 1是基准元素的正确位置。
返回基准元素的索引：
返回
prev + 1，作为分区后的基准元素索引。
经过一次单趟排序，最终也能使得key左边的数据全部都小于key，key右边的数据全部都大于key。
然后将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作
//分区（前后指针）
private int partition(int[] array,int left,int right){
int start = left;// 基准元素的位置
int prev = left;
int cur = prev+1;// 当前遍历的指针
while(cur<=right){
//避免不必要的交换
//将所有小于基准元素的元素移动到 prev 的左侧
if(array[cur]<array[start]&&prev++!=cur){
swap(array,prev,cur);
}
cur++;
}
swap(array,start,prev);// 将基准元素放到正确的位置
return prev;// 返回基准元素的最终位置
}4. 快速排序优化
1. 三数取中法选key
2. 递归到⼩的⼦区间时，可以考虑使⽤插⼊排序
在快速排序的递归过程中，当子数组的大小小于某个阈值（例如10或20）时，不再继续递归使用快速排序，而是改用插入排序来对这部分数据进行排序。
这种策略可以减少递归调用的开销，并且对于小规模数据，插入排序的性能通常优于快速排序
//排序
private void sort(int[] array,int begin,int end){
if (begin >= end) {
return; // 递归终止条件
}
if(end-begin<=20){
insertSort(array,begin,end);
return;
}
//三数取中法
medianOfThree(array,begin,end);
int basis = partition(array,begin,end);// 获取基准元素的位置
sort(array,begin,basis-1);// 递归排序左半部分
sort(array,basis+1,end);// 递归排序右半部分
}
//三数取中法
private void medianOfThree(int[] array,int begin,int end){
int mid = begin + (end-begin)/2;//取中间位置下标
if(array[begin]>array[mid]){
swap(array,begin,mid);
}
if(array[begin]>array[end]){
swap(array,begin,end);
}
if(array[mid]>array[end]){
swap(array,mid,end);
}
swap(array,begin,mid);
}
//小区间插入排序
private void insertSort(int[] array,int begin,int end){
for(int i=begin+1;i<=end;i++){
int data = array[i];
int j=i-1;
for(;j>=begin;j--){
if(array[j]<data){
break;
}
array[j+1]=array[j];
}
array[j+1]=data;
}
}分析
4. 归并排序
归并排序步骤
1. 分解
将数组从中间分成两个子数组。
递归地对左半部分和右半部分进行归并排序。
递归的终止条件是数组长度为 1 或 0（此时数组已经有序）。
2. 合并
创建一个临时数组，用于存储合并后的结果。
使用两个指针分别遍历两个子数组，比较指针所指的元素，将较小的元素放入临时数组。
如果其中一个子数组遍历完毕，将另一个子数组的剩余部分直接放入临时数组。
将临时数组的内容复制回原数组。
时间复杂度分析
分解：每次将数组分成两半，递归深度为 O(log n)。
合并：每次合并需要遍历所有元素，时间复杂度为 O(n)。
总时间复杂度为 O(n log n)。
空间复杂度分析
归并排序需要额外的空间来存储临时数组，空间复杂度为 O(n)
//归并排序
public void mergeSort(int[] array){
if(array==null){
return;
}
dMergeSort(array,0,array.length-1);
}
//分解
private void dMergeSort(int[] array,int begin,int end){
//如果有一个节点，或一个节点都没有
if(begin>=end){
return;
}
int mid = begin+(end-begin)/2;//找中间位置
dMergeSort(array,begin,mid);
dMergeSort(array,mid+1,end);
merge(array,begin,mid,end);
}
//合并
private void merge(int[] array,int begin,int mid,int end){
int s1 = begin;
int s2 = mid+1;
int[] tem = new int[end-begin+1];
int i=0;
while(s1<=mid&&s2<=end){
if(array[s1]<=array[s2]){
tem[i++] = array[s1++];
}else{
tem[i++]=array[s2++];
}
}
while(s1<=mid){
tem[i++] = array[s1++];
}
while(s2<=end){
tem[i++]=array[s2++];
}
//将数组tem中的数据转到array中
for(i=0;i<tem.length;i++){
array[begin++] = tem[i];
}
}5. 计数排序
计数排序的步骤
找到最大值和最小值：
遍历数组，找到最大值
max和最小值min，确定数据的范围。
创建计数数组：
创建一个大小为
max - min + 1的计数数组count，用于存储每个元素的出现次数。
统计元素出现次数：
遍历数组，统计每个元素出现的次数，并存储在
count数组中。
累加计数数组：
对
count数组进行累加操作，使得count[i]表示小于等于i + min的元素的总数。
将元素放回正确的位置：
1.遍历原数组，根据count数组中的信息，将元素放入 array 数组的相应位置。
时间复杂度低：
计数排序的时间复杂度为O(n+k)，其中 n 是数组长度，k 是数据范围。
当 k 较小且 n 较大时，计数排序的效率非常高。
空间复杂度：
计数排序需要额外的空间来存储计数数组，空间复杂度为 O(k)。
稳定性：
计数排序是稳定的排序算法，相同元素的相对顺序不会改变。
//计数排序
public void countSort(int[] array){
if(array==null){
return;
}
int min = array[0];
int max = array[0];
//寻找最小和最大值
for(int i=0;i<array.length;i++){
if(array[i]<min){
min = array[i];
}
if(array[i]>max){
max = array[i];
}
}
//创建数组
int[] tmp = new int[max-min+1];
for(int i=0;i<array.length;i++){
tmp[array[i]-min]++;// 统计每个元素的出现次数
}
int j=0;
for(int i=0;i<tmp.length;i++){
while(tmp[i]-->0){
array[j++]=i+min; // 将元素写回原数组
}
}
}
}6. 基数排序
算法步骤：
确定最大位数：找到列表中最大数字的位数，确定需要排序的轮数。
按位排序：从最低位开始，依次对每一位进行排序（通常使用计数排序或桶排序作为子排序算法）。
合并结果：每一轮排序后，更新列表的顺序，直到所有位数排序完成。
时间复杂度
每一轮排序：O(n)，使用计数排序对每一位进行排序。
总轮数：k 轮，其中 k 是最大数字的位数。
总时间复杂度：O(n * k)。
空间复杂度
O(n + k)，需要额外的存储空间来存放计数数组和输出数组。
稳定性
基数排序是稳定的排序算法，相同元素的相对顺序不会改变。
适用场景
数据为整数或字符串，且位数较小。
数据范围较大，但位数较少。
需要稳定排序的场景。
//基数排序
public void contingSort(int[] array){
if(array==null){
return;
}
int max = array[0];
//寻找最最大值
for(int i=0;i<array.length;i++){
if(array[i]>max){
max = array[i];
}
}
//要进行几次排序
int k = 0;
while(max!=0){
max /= 10;
k++;
}
//创建大小为10的顺序表，里面存放顺序表，记录每一位的值
List<LinkedList<Integer>> count= new ArrayList<>(10);
//为顺序表的每个元素添加顺序表
for(int i=0;i<10;i++){
count.add(new LinkedList<>()) ;
}
//按位排序
for(int n=1;n<=k;n++){
//按位排序
for(int i=0;i<array.length;i++){
//寻找该位上的数
int num = findNum(array[i],n);
//将该数存入对应count下标的顺序表中
count.get(num).add(array[i]);
}
int j =0;
//将链表中的数字放入array中
for(int i=0;i<10;i++){
while(!count.get(i).isEmpty()){
array[j++] = count.get(i).remove(0);
}
}
}
}
//寻找指定位上的数
private int findNum(int num,int k){
int data=0;
while(k>0){
data = num%10;
num /=10;
k--;
}
return data;
}7. 桶排序
算法步骤：
初始化桶：根据数据的范围和分布，创建若干个桶。
分配元素：遍历待排序的列表，将每个元素分配到对应的桶中。
排序每个桶：对每个桶中的元素进行排序（可以使用插入排序、快速排序等）。
合并桶：将所有桶中的元素按顺序合并，得到最终排序结果。
时间复杂度
分配元素：O(n)，遍历列表一次。
排序每个桶：假设每个桶中的元素数量为 m，则排序一个桶的时间复杂度为 O(m log m)。如果桶的数量为 k，则总时间复杂度为 O(k * m log m)。
合并桶：O(n)，遍历所有桶一次。
总时间复杂度：O(n + k * m log m)，其中 n 是列表长度，k 是桶的数量，m 是每个桶的平均元素数量。
空间复杂度
O(n + k)，需要额外的存储空间来存放桶和排序后的结果。