ext-02-排序算法
难度说明:🟢简单🟡中等🔴困难
学习资料
学习目标
- 掌握数据结构核心基础
- 借助数据结构完成常见题型
ext-02-排序算法
理论基础
1.核心理论
常见排序算法考察
- 冒泡排序
- 选择排序
- 插入排序
- 快速排序
- 归并排序
- 堆排序
- ....
对于不同算法的理解可以分拆"已排序区间、待排序区间",然后思考如何进行处理以及遍历的顺序
1.排序算法核心概念
排序算法(sorting algorithm)用于对一组数据按照特定顺序进行排列。排序算法有着广泛的应用,因为有序数据通常能够被更高效地查找、分析和处理。
如图所示,排序算法中的数据类型可以是整数、浮点数、字符或字符串等。排序的判断规则可根据需求设定,如数字大小、字符 ASCII 码顺序或自定义规则
2.算法评价维度
运行效率:期望排序算法的时间复杂度尽量低,且总体操作数量较少(时间复杂度中的常数项变小)。对于大数据量的情况,运行效率显得尤为重要
就地性:顾名思义,原地排序通过在原数组上直接操作实现排序,无须借助额外的辅助数组,从而节省内存。通常情况下,原地排序的数据搬运操作较少,运行速度也更快
稳定性:稳定排序在完成排序后,相等元素在数组中的相对顺序不发生改变
稳定排序是多级排序场景的必要条件。假设我们有一个存储学生信息的表格,第 1 列和第 2 列分别是姓名和年龄。在这种情况下,非稳定排序可能导致输入数据的有序性丧失:
# 输入数据是按照姓名排序好的
# (name, age)
('A', 19)
('B', 18)
('C', 21)
('D', 19)
('E', 23)
# 假设使用非稳定排序算法按年龄排序列表,
# 结果中 ('D', 19) 和 ('A', 19) 的相对位置改变,
# 输入数据按姓名排序的性质丢失
('B', 18)
('D', 19)
('A', 19)
('C', 21)
('E', 23)
自适应性:自适应排序能够利用输入数据已有的顺序信息来减少计算量,达到更优的时间效率。自适应排序算法的最佳时间复杂度通常优于平均时间复杂度
是否基于比较:基于比较的排序依赖比较运算符(<、=、>)来判断元素的相对顺序,从而排序整个数组,理论最优时间复杂度为 O(nlogn) 。而非比较排序不使用比较运算符,时间复杂度可达 O(n) ,但其通用性相对较差
3.理想排序算法
运行快、原地、稳定、自适应、通用性好。显然,迄今为止尚未发现兼具以上所有特性的排序算法。因此,在选择排序算法时,需要根据具体的数据特点和问题需求来决定。
接下来,我们将共同学习各种排序算法,并基于上述评价维度对各个排序算法的优缺点进行分析
常用排序算法
学习核心
冒泡排序:每一轮依次从头到尾两两比较元素,将较小或者较大的元素依次置换到后面
- 核心:从后往前固定,将min/max交换到后面
- 双层循环:外层
i
表示比较轮次(取值为[0,n-1]
,每一轮都会从后往前固定1位数字),内层j
表示当前轮次比较位置(取值为[0,n-i-1]
,针对已经固定的数位不需要重复判断)- 比较目标:
nums[j]
与nums[j+1]
- 比较目标:
选择排序(基础版本):
- 核心:从前往后固定,选出当前轮次的min/max交换到前面
- 双层循环:外层
i
表示比较轮次(取值为[0,n-1]
,每一轮都会从前往后固定1位数字),内层j
用于限定当前的比较范围指针(从剩余的[i+1,n)
中选出min/max,然后将其固定到当前i
的位置)- 比较目标:
nums[i]
与nums[j]
- 比较目标:
选择排序(优化版本)
- 优化版本的核心思路和基础版本类似,每次从待排序区间中选出
min
对应的索引(只不过优化版本是简化了交换过程,无需每次都执行交换,只是记录本次检索过程中最小值的索引位置,待检索完成再执行一次有效的交换操作即可,优化了交换的时间效率)
- 优化版本的核心思路和基础版本类似,每次从待排序区间中选出
插入排序:
- 核心:从前往后固定,
i
位置为当前待插入处理元素,[0,i-1]
为已排序区间(从后往前扫描已遍历区间[0,i-1]
为其选择合适的插入位置) - 双层循环:
- 外层
i
定位当前待插入处理元素 - 内存循环通过
while
从后往前寻找合适的插入位置(例如此处先记录nums[i]
(curKey
),如果遇到比它大的数则将大数往后移动1位,依次类推,直到找到合适的插入位置后直接执行替换操作即可)- 为什么是从后往前?:如果是从后往前寻找插入位置的话,当寻找到合适的插入位置
idx
则需要将后面的元素都往后移动一位以空出插入位置,就会需要额外的数组移动损耗;而如果是从后往前寻找插入位置的话,通过比较待插入元素curKey
与比较位置元素nums[idx]
,如果发现nums[idx]>curKey
说明当前位置还不满足插入条件,此时将nums[idx]
往后移动一位(相当于逐步将大数往后移动,空出待插入位置:执行nums[idx+1]=nums[idx]
),随后执行idx--
继续寻找下一个可能的插入位置,以此类推。当while
循环退出,则说明找到了可插入的位置,即需要将curKey
插入到idx
的后一个位置(执行nums[idx+1]=curKey
)。基于此,从后往前遍历的过程中,已经逐步将大数往后移动,当找到满足的插入位置则直接执行插入操作即可
- 为什么是从后往前?:如果是从后往前寻找插入位置的话,当寻找到合适的插入位置
- 外层
- 核心:从前往后固定,
快速排序:
- 核心:选基准、分区、递归
① 选
pivot
:从数列中选出一个元素,作为基准pivot
- 对于
pivot
的选择,由于选择的基准不同进而衍生了不同版本的快排版本(随机选主概念),选择方向可以参考:选择第一个元素、选择最后一个元素、随机选择一个、选择中值
- 对于
②
partition
分区操作:重新排序数列,将所有元素值比基准值小的放在pivot
前面,将所有元素值比基准值大的元素放在pivot
后面,如果相同的数可以放置在任意一边③
recursive
递归处理:递归地将小于基准值元素的子数列和大于基准值元素的子数列排序
- 核心:选基准、分区、递归
归并排序
- 核心:递归:划分、合并
- 递归核心:基于【后序遍历】的思路处理,对于每一层递归需明确当层待合并区间范围
- ① 递归出口:当待合并区间元素个数少于2个则返回
- ② 划分:可以基于原数组进行划分,也可以copy出一份新数组进行划分,最重要的是明确区间取值。随后对左子数组、右子数组分别进行递归(左数组
[left,mid]
、右数组[mid+1,right]
(或(mid,right]
),注意此处需要将mid也纳入某个区间) - ③ 合并:合并上述递归处理后的有序数组
- 合并思路1:基于原数组进行合并
- 合并思路2:基于数组赋值,copy出一份新数组进行合并后处理
学习资料
排序算法
此处排序算法的演示均按照升序进行处理
1.冒泡排序
⚽ 核心概念
冒泡排序核心:循环遍历数组,每次从头到尾依次比较两个相邻的元素,按照递增或者递减的规则决定元素的交换,将当前轮次的min或max交换到数组末尾
- 核心:从后往前固定,将min/max交换到后面
- 双层循环:
- 外层
i
表示比较轮次(取值为[0,n-1]
,每一轮都会从后往前固定1位数字) - 内层
j
表示当前轮次比较位置(取值为[0,n-i-1]
,针对已经固定的数位不需要重复判断) - 每次比较相邻两数的大小,将较小或较大值往后置放,1轮校验结束会依次从后往前固定1位,针对已固定的数位不需要重复判断
- 外层
🚀 代码实现
public class BubbleSort {
/**
* 冒泡排序算法
*/
public int[] bubbleSort(int[] arr) {
// 冒泡:循环遍历数组,依次比较两个相邻的元素,按照递增或者递减的规则决定元素的交换,将当前轮次的min或max交换到数组末尾
for(int i = 0; i < arr.length - 1; i++) {
// 依次比较相邻两个元素(此处边界设定考虑有两个因素:一是相邻两个元素比较,二是数组尾部的是前面轮次放置的最大值,因此在后面的轮次中无需重复比较)
for(int j = 0; j < arr.length - i - 1; j++) {
if(arr[j] > arr[j + 1]) {
// 将较大的元素交换到后面
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
// 返回排序后的数组
return arr;
}
public static void main(String[] args) {
int[] arr = { 3, 5, 15, 26, 27, 2, 36 };
BubbleSort bubbleSort = new BubbleSort();
Arrays.stream(bubbleSort.bubbleSort(arr)).forEach(System.out::println);
}
}
2.选择排序
选择排序核心:从前往后依次固定值,每轮选出当前剩余元素序列中的min/max
- 核心:从前往后固定,选出当前轮次的min/max交换到前面
- 双层循环:
- 外层
i
表示比较轮次(取值为[0,n-1]
,每一轮都会从前往后固定1位数字) - 内层
j
用于限定当前的比较范围指针(从剩余的[i+1,n)
中选出min/max,然后将其固定到当前i
的位置) - 比较目标:
nums[i]
与nums[j]
- 外层
- 优化思路:由于每轮遍历的目的是从当前剩余的择选范围中选出当轮的min/max,因此可以在这个过程中记录"最值"的索引,然后再在当轮结束之前交换这个最值即可(可省略交换过程)
public class SelectionSort {
/**
* 选择排序算法(基础)
*/
public int[] selectionSortBase(int[] arr) {
// 选择:每一轮都将当前元素和其后面的元素进行比较,按照升序或降序的要求进行数据交换
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] > arr[j]) {
// 将较大的元素交换到后面
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
// 返回排序后的数组
return arr;
}
/**
* 选择排序算法(优化)
* 选择排序实际在每一轮比较中选择的是当前轮次(当前元素所在位置之后的元素)的min或max,最终交换也是将这个最值和当前轮次索引位置进行交换
* 因此对于过程中的比较可以记录这个最值索引,然后在当前轮次结束后执行一次交换即可(省略过程中一些不必要的交换)
*/
public int[] selectionSort(int[] arr) {
// 选择:循环遍历数组,依次比较两个相邻的元素,按照递增或者递减的规则决定元素的交换,将当前轮次的min或max交换到数组末尾
for (int i = 0; i < arr.length - 1; i++) {
// 初始化当前轮次的最小值
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[minIndex] > arr[j]) {
// 更新当前轮次的最值索引
minIndex = j;
}
}
// 一轮比较结束之后执行交换(如果minIndex!=i说明最小值索引更新了需要执行交换操作)
if(minIndex != i) {
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
// 返回排序后的数组
return arr;
}
}
3.插入排序
⚽ 核心概念
插入排序核心思路:
- 核心:类似打扑克牌的思路,将当前遍历元素插入到
[0,i-1]
区间内合适的位置(i
为当前待排序元素,[0,i-1]
区间为已排序区间) - 双层循环:
- 外层循环:选择当前轮次需要插入处理的元素位置
i
- 内层循环:从已排序的范围
[0,i-1]
从后往前寻找合适的插入位置(从后往前遍历是为了便于处理数组移动,避免数据直接被覆盖)- 记录
curKey=nums[i]
,从后往前寻找可插入的位置,如果curKey<nums[j]
则需要将其往后移动 - 为什么遍历顺序不选择从前往后?:如果是从前往后遍历寻找可插入位置,则当找到这个插入位置后,基于这个位置
idx
往后的所有元素([idx+1,i-1]
)都要统一往后移动1位,而从后往前遍历则是为了避免数组整体移动的消耗
- 记录
- 外层循环:选择当前轮次需要插入处理的元素位置
🚀 代码实现
public class InsertionSort {
/**
* 选择排序算法(基础)
*/
public int[] selectionSortBase(int[] arr) {
// 插入:类似排扑克牌的思路,
// 外循环:已排序区间为 [0, i-1](i位置前面的元素已经完成排序)
for (int i = 1; i < arr.length; i++) { // 从第2个元素开始执行第1轮插入
// 待插入元素
int curKey = arr[i];
// 待插入位置(起始从i-1位置开始往前进行比较,确认插入位置)
int idx = i - 1;
// 内循环:找到[0,i-1]区间内满足的插入位置,将 base 插入到已排序区间 [0, i-1] 中的正确位置
while (idx >= 0 && arr[idx] > curKey) { // 如果curKey相对较小则依次往前比较,直到找到第一个合适的位置(此处的while子句实际等价于for循环找位置)
arr[idx + 1] = arr[idx]; // 将 arr[idx] 向右移动一位
idx--;
}
arr[idx + 1] = curKey; // 将curKey赋值到正确位置
}
// 返回排序后的数组
return arr;
}
}
单次插入操作理解:
排序流程分析理解:
- 初始状态下,数组的第 1 个元素已完成排序
- 选取数组的第 2 个元素作为
base
,将其插入到正确位置后,数组的前 2 个元素已排序 - 选取第 3 个元素作为
base
,将其插入到正确位置后,数组的前 3 个元素已排序 - 以此类推,在最后一轮中,选取最后一个元素作为
base
,将其插入到正确位置后,所有元素均已排序
插入排序优势
插入排序的时间复杂度为 O(n2) ,而快速排序的时间复杂度为 O(nlogn) 。尽管插入排序的时间复杂度更高,但在数据量较小的情况下,插入排序通常更快。
这个结论与线性查找和二分查找的适用情况的结论类似。快速排序这类 O(nlogn) 的算法属于基于分治策略的排序算法,往往包含更多单元计算操作。而在数据量较小时,n2 和 nlogn 的数值比较接近,复杂度不占主导地位,每轮中的单元操作数量起到决定性作用。
实际上,许多编程语言(例如 Java)的内置排序函数采用了插入排序,大致思路为:对于长数组,采用基于分治策略的排序算法,例如快速排序;对于短数组,直接使用插入排序。
虽然冒泡排序、选择排序和插入排序的时间复杂度都为 O(n2) ,但在实际情况中,插入排序的使用频率显著高于冒泡排序和选择排序,主要有以下原因。
- 冒泡 VS 插入:
- 冒泡排序基于元素交换实现,需要借助一个临时变量,共涉及 3 个单元操作;
- 插入排序基于元素赋值实现,仅需 1 个单元操作。因此,冒泡排序的计算开销通常比插入排序更高
- 选择 VS 插入:
- 选择排序在任何情况下的时间复杂度都为 O(n2) ,且选择排序不稳定,无法应用于多级排序
- 如果给定一组部分有序的数据,插入排序通常比选择排序效率更高
4.快速排序
⚽ 核心概念
快速排序核心分析:
- ① 选
pivot
:从数列中选出一个元素,作为基准pivot
- 对于
pivot
的选择,由于选择的基准不同进而衍生了不同版本的快排版本(随机选主概念),选择方向可以参考:- 总是选择第一个元素作为 pivot
- 总是选择最后一个元素作为 pivot
- 随机选一个元素作为 pivot
- 选择中值作为 pivot
- 随机选主:此处如果仅仅采用某个方案会陷入超时限制问题,因此应采用随机选主的方式处理以进一步校验测试用例
- 对于
- ②
partition
分区操作:重新排序数列,将所有元素值比基准值小的放在pivot
前面,将所有元素值比基准值大的元素放在pivot
后面,如果相同的数可以放置在任意一边。分区完成之后,这个pivot
就处于数列的中间位置,这个过程称为分区partition
操作- 分区完成,返回选择的
pivot
所在的索引位置,用于递归分界
- 分区完成,返回选择的
- ③
recursive
递归处理:递归地将小于基准值元素的子数列和大于基准值元素的子数列排序
/* 快速排序核心 */
public void quickSort(int[] nums, int left, int right) {
// 子数组长度为 1 时终止递归
if (left >= right) {
return;
}
// 哨兵划分
int pivot = partition(nums, left, right);
// 递归左子数组、右子数组
quickSort(nums, left, pivot - 1);
quickSort(nums, pivot + 1, right);
}
针对分区,根据选择的哨兵不同(随机选主概念)会衍生多种不同版本的分区算法,此处给出一种【始终选择第1个元素作为 pivot】。其核心思路在于选定第1个元素作为基准,然后将每个元素与这个pivot
进行比较,依次将较大的元素置换到后面(如果是从小到大排序的话)。当所有元素校验完成,则最后将pivot
交换到期望位置
// partition 单指针分区处理(限定对指定区域范围进行分区处理)
private int partition(int[] nums, int left, int right) {
// 设置基准值(初始化),此处nums[]取值为闭区间[left,right]
int pivot = nums[left]; // 选择第一个数作为分区标准
int idx = left; // idx 指向当前分区的起始位置(随着遍历移动,最终会指向基准数所在位置)
// 从数组的第2个元素开始遍历,如果当前遍历元素比pivot大,则跳过
for (int i = left + 1; i <= right; i++) {
if (nums[i] <= pivot) {
// 如果找到了小于当前pivot的数,则需要将其与前面较大的数进行交换(此处相当于将较大的数逐步置换到后面去)
idx++;
swap(nums, i, idx);
}
}
// 上述遍历完成,最终需将比较元素交换到期望位置
swap(nums, left, idx);
// 返回基准值索引位置
return idx;
}
// 交换指定位置的数组元素
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
同理,类似地,如果选择【最后1个元素作为pivot
】,则需要从后往前遍历移动边界,将前面较大的数移动到后面,最终idx
指向位置就是pivot
期望的位置。此处idx
的移动条件是在找到满足移动条件的位置时才往前或者往后挪动一位以空出位置。idx
指向实际为分界线概念,将数组元素基于pivot
进行拆分
private int partition(int[] nums, int left, int right) {
// 设置基准值(初始化),此处nums[]取值为闭区间[left,right]
int pivot = nums[right]; // 选择最后1个数作为分区标准
int idx = right; // idx 指向当前分区的起始位置(随着遍历移动,最终会指向基准数所在位置)
// 从后往前遍历元素,将较大的值置换到后面
for (int i = right - 1; i >= left; i--) {
if (nums[i] >= pivot) {
// 如果找到了大于等于当前pivot的数,则需要将其与后面较小的数进行交换(此处相当于将较大的数逐步置换到后面去)
idx--;
swap(nums, i, idx);
}
}
// 上述遍历完成,最终需将比较元素交换到期望位置
swap(nums, right, idx);
// 返回基准值索引位置
return idx;
}
还有另一种双指针分区思路:partition算法使用头尾两个方向相反的指针进行遍历,先将数组第一个元素设置为比较元素,头指针从左至右找到第一个大于比较元素的数,尾指针从右至左找到第一个小于比较元素的数,全部交换完毕后将比较元素放到中间位置
// 划分数组
public static int partition(int a[], int low, int high)
{
int x = a[low]; //将该数组第一个元素设置为比较元素
int i=low;
int j=high;
while(i < j)
{
while(i<j && a[i] <= x)
i++;
while(i<j && a[j] >= x)
j--;
if(i!=j)
swap(a, i, j);
}
swap(a, j, low);
return j;
}
🚀 代码实现
/**
* 快速排序
*/
public class QuickSort {
/* 快速排序 */
public void quickSort(int[] nums, int left, int right) {
// 子数组长度为 1 时终止递归
if (left >= right) {
return;
}
// 哨兵划分
int pivot = partition(nums, left, right);
// 递归左子数组、右子数组
quickSort(nums, left, pivot - 1);
quickSort(nums, pivot + 1, right);
}
// partition 单指针分区处理(限定对指定区域范围进行分区处理)
private int partition1(int[] nums, int left, int right) {
// 设置基准值(初始化),此处nums[]取值为闭区间[left,right]
int pivot = nums[left]; // 选择第一个数作为分区标准
int idx = left; // idx 指向当前分区的起始位置(随着遍历移动,最终会指向基准数所在位置)
// 从数组的第2个元素开始遍历,如果当前遍历元素比pivot大,则跳过
for (int i = left + 1; i <= right; i++) {
if (nums[i] <= pivot) {
// 如果找到了小于当前pivot的数,则需要将其与前面较大的数进行交换(此处相当于将较大的数逐步置换到后面去)
idx++;
swap(nums, i, idx);
}
}
// 上述遍历完成,最终需将比较元素交换到期望位置
swap(nums, left, idx);
// 返回基准值索引位置
return idx;
}
private int partition(int[] nums, int left, int right) {
// 设置基准值(初始化),此处nums[]取值为闭区间[left,right]
int pivot = nums[right]; // 选择最后1个数作为分区标准
int idx = right; // idx 指向当前分区的起始位置(随着遍历移动,最终会指向基准数所在位置)
// 从后往前遍历元素,将较大的值置换到后面
for (int i = right - 1; i >= left; i--) {
if (nums[i] >= pivot) {
// 如果找到了大于等于当前pivot的数,则需要将其与后面较小的数进行交换(此处相当于将较大的数逐步置换到后面去)
idx--;
swap(nums, i, idx);
}
}
// 上述遍历完成,最终需将比较元素交换到期望位置
swap(nums, right, idx);
// 返回基准值索引位置
return idx;
}
// 交换指定位置的数组元素
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public static void main(String[] args) {
QuickSort quickSort = new QuickSort();
// int[] nums = new int[]{3, 6, 12, 4, 26};
// int[] nums = new int[]{2,4,1,0,3,5};
int[] nums = new int[]{2, 1, 4, 0, 3, 5};
quickSort.quickSort(nums, 0, nums.length - 1);
Arrays.stream(nums).forEach(System.out::println);
}
}
关于分界位置的初始值和移动处理讨论:
cur = left
说明当前位置就是基准位置,当出现了比基准位置小的数则往前找1个大数(移动cur
指针)进行交换存储(将小数交换到前面),最终所有元素遍历完成,cur指向位置就是基准位置cur = left + 1
表示当前位置为基准位置的下一个位置,当出现比基准位置小的数则进行交换存储(将小数交换到前面),那么最终所有的元素遍历完成,基准位置应该为cur-1
5.归并排序
⚽核心概念
归并排序(merge sort)是一种基于分治策略的排序算法,其核心在于将长数组的排序分治为递归处理有序短数组的合并问题,主要包含两个部分:
- ① 划分阶段:通过递归不断地将数组从中点处分开,将长数组的排序问题转换为短数组的排序问题
- ② 合并阶段:当子数组长度为 1 时终止划分,开始合并,持续地将左右两个较短的有序数组合并为一个较长的有序数组,直至结束
归并排序和二叉树的【后序遍历】顺序是一致的:
- 【后序遍历】:先递归左子树、后递归右子树、然后处理根节点
- 【归并排序】:先递归左子数组、后递归右子数组、然后处理合并
🚀代码实现
归并排序核心代码(有两种实现思路,一种是基于原数组处理,一种是copy出新数组进行处理)
① 基于原数组进行分拆
- 递归处理(后序遍历):
- 递归出口:
left≤right
退出,当子数组长度为1是终止递归(此处基于原数组进行分拆,因此根据left、right边界来划分) - ① 划分:左子数组
[left,mid]
、右子数组[mid+1,right]
- ② 合并:对递归排序后的数组元素进行合并(转化为合并两个有序数组的思路)
- 此处需注意合并处理的最终根据temp回填的范围:
temp[0,len]
对照的是nums[left,right]
- 此处需注意合并处理的最终根据temp回填的范围:
- 递归出口:
/**
* 归并排序
*/
public class MergeSort1 {
/**
* 归并排序:划分、合并
*
* @param nums 待合并数组
* @param left,right 待合并区间
*/
void mergeSort(int[] nums, int left, int right) {
// 终止条件
if (left >= right) {
return; // 当子数组长度为 1 时终止递归
}
// ① 划分阶段
int mid = left + (right - left) / 2; // 计算中点
mergeSort(nums, left, mid); // 递归左子数组
mergeSort(nums, mid + 1, right); // 递归右子数组
// ② 合并阶段
merge(nums, left, mid, right);
}
// 根据指定区域合并数组
/*
private void merge(int[] nums, int left, int mid, int right) {
// 创建临时数组存放合并后的元素
int len = right - left + 1;
int[] temp = new int[len];
// 定义双指针用于合并两个数组:左子数组取值[left,mid] 右子数组取值(mid,right]/[mid+1,right]
int p1 = left, p2 = mid + 1;
int cur = 0; // cur 指向当前合并位置
while (p1 <= mid || p2 <= right) {
int val1 = (p1 <= mid) ? nums[p1] : Integer.MAX_VALUE;
int val2 = (p2 <= right) ? nums[p2] : Integer.MAX_VALUE;
if (val1 <= val2) {
temp[cur++] = val1;
p1++;
} else {
temp[cur++] = val2;
p2++;
}
}
// 将临时数组元素重新填充到nums(此处需注意temp[0,len] => nums[left,right])
for (int i = 0; i < len; i++) {
nums[left + i] = temp[i];
}
}
*/
private void merge(int[] nums, int left, int mid, int right) {
// 创建临时数组存放合并后的元素
int len = right - left + 1;
int[] temp = new int[len];
// 定义双指针用于合并两个数组:左子数组取值[left,mid] 右子数组取值(mid,right]/[mid+1,right]
int p1 = left, p2 = mid + 1;
int cur = 0; // cur 指向当前合并位置
while (p1 <= mid && p2 <= right) {
if (nums[p1] <= nums[p2]) {
temp[cur++] = nums[p1++];
} else {
temp[cur++] = nums[p2++];
}
}
// 补充尾部
while (p1 <= mid) {
temp[cur++] = nums[p1++];
}
while (p2 <= right) {
temp[cur++] = nums[p2++];
}
// 将临时数组元素重新填充到nums(此处需注意temp[0,len] => nums[left,right])
for (int i = 0; i < len; i++) {
nums[left + i] = temp[i];
}
}
}
② copy 出新数组进行处理
递归处理(后序遍历):
- 递归出口:当子数组长度为1是终止递归(此处是基于copy出来的新数组进行处理,因此直接判定数组长度)
- ① 划分:针对待合并数组的范围为
[0,len)
,因此左子数组[0,mid)
、右子数组[mid,len)
- ② 合并:对递归排序后的数组元素进行合并(转化为合并两个有序数组的思路)
/**
* 归并排序
*/
public class MergeSort2 {
/**
* 归并排序:划分、合并(基于拷贝数组实现)
*
* @param nums 待合并数组
*/
int[] mergeSort(int[] nums) {
// 递归出口
if (nums.length < 2) {
return nums;
}
// ① 划分阶段
// int mid = (int) Math.floor(nums.length / 2); // 计算中点
int mid = nums.length / 2;
int[] left = Arrays.copyOfRange(nums, 0, mid); // [0,mid)
int[] right = Arrays.copyOfRange(nums, mid, nums.length); // [mid,n)
// ② 合并阶段(对排序后的左右子数组进行合并)
return merge(mergeSort(left), mergeSort(right));
}
// 合并两个有序数组
private int[] merge(int[] nums1, int[] nums2) {
int m = nums1.length, n = nums2.length;
int[] merge = new int[m + n];
// 定义指针分别遍历两个数组以及处理合并后的数组
int p1 = 0, p2 = 0; // p1、p2分别用于遍历nums1,nums2
int cur = 0; // cur 指向当前merge数组处理的位置
while (p1 < m || p2 < n) {
// 处理数组边界情况,如果越界则设置为MAX(辅助处理,简化尾部处理)
int val1 = (p1 < m ? nums1[p1] : Integer.MAX_VALUE);
int val2 = (p2 < n ? nums2[p2] : Integer.MAX_VALUE);
// 择选较小的值载入
if (val1 <= val2) {
merge[cur++] = val1;
p1++;
} else {
merge[cur++] = val2;
p2++;
}
}
// 返回合并后的数组
return merge;
}
}
6.堆排序
⚽ 核心概念
Java 中的堆排序会借助PriorityQueue
辅助构建小顶堆或者大顶堆。此处则是基于堆数据结构,基于"建堆操作"和"元素出堆操作"来实现堆排序:
- ① 输入数组并建立小顶堆,此时最小元素位于堆顶
- ② 不断执行出堆操作,依次记录出堆元素,即可得到从小到大的排序序列
上述思路需要构建一个额外数组来保存弹出的元素,比较浪费空间。实际的场景中会选择进行空间优化版本,也就是利用交换的概念来复用空间:
- ① 构建大顶堆,此时最大元素位于堆顶
- 升序用大顶堆,降序用小顶堆(因为每次都是择选堆顶元素放置到已排序区间,针对已排序区间其是从后往前覆盖处理的)
- ② 交换:
- 将堆顶元素与堆底元素进行交换(相当于从底往上依次固定排序序列),交换完成后此时堆的长度减1,而已排序的元素加1
- 也就是说如果是基于原数组进行堆排序,那么实际上这个数组被划分为两个区域:待排序区域(堆的有效区间)、已排序区域
- 上述交换操作完成之后,原有的堆结构被破坏了,因此需要从顶到底执行堆化操作(
sift down
),以修复堆的性质
- 将堆顶元素与堆底元素进行交换(相当于从底往上依次固定排序序列),交换完成后此时堆的长度减1,而已排序的元素加1
- ③ 循环执行第②步,当执行n-1轮之后即可完成数组排序
① 堆排序
堆结构概念
堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种**选择排序,**它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。先从堆结构切入:
堆:堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆
基于上述层序遍历得到数组序列,该数组从逻辑上讲就是一个堆结构,用简单的公式描述堆的定义:
- 大顶堆:arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
- 小顶堆:arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
堆排序
要获取到数组的升序序列,需要借助大顶堆,其排序核心思想如下:
- ① 构建大顶堆:将待排序序列构造成一个大顶堆,此时堆顶元素对照的就是整个序列的max
- ② 顶底交换 + 堆化修复:
- 顶底交换:将堆顶元素(当前待排序序列的最大值)与底部元素进行交换,交换完成待排序序列(堆的有效范围减1)、已排序序列加1(相当于将选出的堆顶元素固定到指定位置)
- 堆化修复:交换完成后会破坏现有的堆结构,因此需要进行
从顶到底
的堆化操作以修复堆结构
- ③ 循环执行步骤②
n-1
次(有序序列的固定是从后往前填充的,基于此理解为什么升序序列要选用大顶堆),最终确定了整个有序的序列
① 建堆(构建大顶堆)
以序列[4,6,8,5,9]
,初始化构建大顶堆。把大顶堆当做一个完全二叉树,其有一个关键的性质是可以将完全二叉树节点与数组下标索引进行对照,且对于一个完全二叉树而言,第1个非叶子节点的索引位置是这棵完全二叉树的元素个数除以2得到
② 堆底交换 + 堆化恢复
③ 反复执行步骤②
🚀 代码实现
/**
* 堆排序
*/
public class HeapSort {
/**
* 堆排序:
* ① 构建大顶堆(用于辅助构建升序序列)
* ② 顶底交换 + 堆化调整:
* - 将堆顶元素和堆底元素进行交换,交换后堆的有效范围减1,已排序序列加1
* - 交换后可能会破坏原有的堆结构,需要自顶向下进行堆化操作,以恢复堆结构
* ③ 重复n-1次步骤②
*/
public void heapSort(int[] arr) {
// 1.构建大顶堆
for (int i = arr.length / 2 - 1; i >= 0; i--) {
// 从第一个非叶子结点从下至上,从右至左调整结构
adjustHeap(arr, i, arr.length);
}
// 顶底交换 + 堆化调整
for (int j = arr.length - 1; j > 0; j--) { // 此处从底部元素位置开始遍历
swap(arr, 0, j);// 将堆顶元素与末尾元素进行交换
adjustHeap(arr, 0, j);// 从根结点开始到指定范围,由顶到底进行堆化
}
}
// 交换数组元素
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 堆化调整(此处堆化调整是针对大顶堆已构建的基础上)
private void adjustHeap(int[] arr, int i, int length) {
int temp = arr[i];//先取出当前元素i
for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {// 从i结点的左子结点开始,也就是2i+1处开始
if (k + 1 < length && arr[k] < arr[k + 1]) {// 如果左子结点小于右子结点,k指向右子结点
k++;
}
if (arr[k] > temp) {// 如果子节点大于父节点,将子节点值赋给父节点(不用进行交换)
arr[i] = arr[k];
i = k;
} else {
break;
}
}
arr[i] = temp;// 将temp值放到最终的位置
}
}
7.桶排序
⚽ 核心概念
🚀 代码实现
8.计数排序
⚽ 核心概念
🚀 代码实现
9.基数排序
⚽ 核心概念
🚀 代码实现
常见题型
123-xxx
1.题目内容
2.题解思路
👻方法1:
复杂度分析
时间复杂度:
空间复杂度:
01-xxx(123)
1.题目内容
2.题解思路
👻方法1:
复杂度分析
时间复杂度:
空间复杂度: