大兴建设网站公司,网页界面设计的网络系统有哪些,咸阳seo,广西建设职业学院技术教务系统网站废话不多说#xff0c;喊一句号子鼓励自己#xff1a;程序员永不失业#xff0c;程序员走向架构#xff01;本篇Blog的主题是【手撕排序系列】#xff0c;使用【数组】这个基本的数据结构来实现#xff0c;这个高频题的站点是#xff1a;CodeTop#xff0c;筛选条件为喊一句号子鼓励自己程序员永不失业程序员走向架构本篇Blog的主题是【手撕排序系列】使用【数组】这个基本的数据结构来实现这个高频题的站点是CodeTop筛选条件为目标公司最近一年出现频率排序由高到低的去牛客TOP101去找只有两个地方都出现过才做这道题CodeTop本身汇聚了LeetCode的来源确保刷的题都是高频要面试考的题。手撕排序系列共3道常考题分别是【快速排序、归并排序、堆排序】这个顺序也是面试出现频度的顺序
明确目标题后附上题目链接后期可以依据解题思路反复快速练习题目按照题干的基本数据结构分类且每个分类的第一篇必定是对基础数据结构的介绍。
快速排序【MID】
首先来最高频的题目快速排序
题干 解题思路
使用快速排序的思路来解决快速排序Quick Sort是一种基于分治思想的排序算法它通过将数组分成较小和较大的两部分并分别对这两部分进行排序最终将整个数组排序。快速排序是一种高效的排序算法通常在平均情况下具有较快的执行速度。
下面是快速排序的基本思想和步骤 [划分]选择基准元素Pivot 从数组中选择一个元素作为基准元素。 [划分]划分Partition 将数组分成两部分使得基准元素左边的元素都小于等于基准元素右边的元素都大于基准元素。这一步骤通常称为“划分”。 [解决]递归排序 递归地对基准元素左边和右边的子数组进行排序。也就是说对小于基准元素的子数组和大于基准元素的子数组分别执行快速排序。 [合并] 合并 由于子数组都是在原数组中进行排序所以最终整个数组也就被排序了。
这些步骤使得较大问题被分解成较小的子问题这些子问题又能通过递归地应用快速排序来解决。在最好情况下每次划分都能将数组均匀分成两半这使得算法的时间复杂度为O(n log n)。
然而需要注意的是快速排序的性能高度依赖于基准元素的选择。最坏情况下如果每次划分都使数组分成极不平衡的两部分算法的时间复杂度可能会退化到O(n^2)。为了应对这种情况通常可以选择合适的基准元素如随机选择或者采用三数取中等方法。
总之快速排序是一种常用且高效的排序算法尤其适用于大规模数据的排序。
代码实现
给出代码实现基本档案 基本数据结构数组 辅助数据结构无 算法快速排序分治算法、二分查找 技巧双指针 import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param n int整型 the n* return int整型*/public int[] sortArray(int[] nums) {return quikSort(nums, 0, nums.length - 1);}// 对数组进行快速排序private int[] quikSort(int[] nums, int start, int end) {int privot;if (start end) {// 1 获取数组基准值元素位置privot partition(nums, start, end);// 2 分治左半边元素快排quikSort(nums, start, privot - 1);// 3 分治右半边元素快排quikSort(nums, privot 1, end);}return nums;}// 单次归位基准值方法private int partition(int[] nums, int start, int end) {// 0 随机选择基准数大小并与最左侧位置交换int randomValueIndex new Random().nextInt(end - start 1) start;swap(nums, start, randomValueIndex);// 1 数组左边第一个为基准值双指针分别执行开始和结束int privot nums[start];int i start;int j end;// 2 开始交互直到ij碰面顺排while (i j) {// 2-1 从右边开始找如果值一直大于基准值则一直循环直到找到小于基准值的元素终止// 需要注意满足条件情况下因为基准值在最左边最后要与j交换所以j停止元素一定要小于基准值所以优先满足j的条件j要先走while (i j nums[j] privot) {j--;}// 2-2 从左边开始找如果值一直小于基准值则一直循环直到找到大于基准值的元素终止while (i j nums[i] privot) {i;}// 2-3 找到要交换的元素且依然满足ij的条件交换if (i j) {swap(nums, i, j);}}// 3 i和j碰面说明该交换的元素已经交换完了最后交换基准值与碰面的值swap(nums, start, j);// 4 返回基准值的当前位置需要按此位置分割return j;}// 元素交换方法private void swap(int[] numbers, int i, int j) {int temp numbers[i];numbers[i] numbers[j];numbers[j] temp;}}需要注意为了保证平衡性可以选择随机找个值作为基准值
int randomValueIndex new Random().nextInt(end - start 1) start;
swap(partNums, start, randomValueIndex);复杂度分析
快速排序的时间复杂度和空间复杂度如下
时间复杂度 平均情况 在平均情况下快速排序的时间复杂度为O(n log n)其中n是待排序数组的长度。这是因为每次划分都能将数组大致均匀地分成两部分导致递归的深度大约为log n而每次划分的过程需要O(n)的时间。 最坏情况 在最坏情况下如果每次划分都导致一个极不平衡的分割例如每次选取的基准元素都是当前子数组的最大或最小元素那么快速排序的时间复杂度可能退化到O(n^2)。这是因为需要执行n次划分每次划分都需要O(n)的时间。为了避免最坏情况通常采用随机选择基准元素或者三数取中法来减少极端情况的发生。 最好情况 快速排序的最好情况时间复杂度为O(n log n)与平均情况相同。这种情况发生在每次划分都能将数组准确地分成相等的两部分时。
空间复杂度
快速排序的空间复杂度主要取决于递归调用的深度和每次划分所使用的额外空间。 递归调用的深度 在递归调用中每次只需要保存一个基准元素的索引和部分数组的边界信息。因此递归调用的深度为O(log n)。 每次划分所使用的额外空间 每次划分需要O(1)的额外空间来存储基准元素和进行交换。
综合考虑快速排序的空间复杂度为O(log n)。这是因为虽然递归调用的深度为O(log n)但在每层递归中所需的额外空间是常数级别的。这使得快速排序在空间上比某些其他排序算法如归并排序更加节省。
归并排序【MID】
然后再做一道次高频的题目归并排序题干与快排一样
题干 解题思路
基本思路借助额外空间合并两个有序数组得到更长的有序数组。归并排序算法主要依赖归并(Merge)操作。归并操作指的是将两个已经排序的序列合并成一个序列的操作
申请空间使其大小为两个已经排序序列之和该空间用来存放合并后的序列设定两个指针最初位置分别为两个已经排序序列的起始位置比较两个指针所指向的元素选择相对小的元素放入到合并空间并移动指针到下一位置重复步骤3直到某一指针到达序列尾
接下来实现递归的归并排序
代码实现
给出代码实现基本档案 基本数据结构数组 辅助数据结构无 算法归并排序 技巧双指针 import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param n int整型 the n* return int整型*/public int[] sortArray(int[] nums) {mergeSort(nums, 0, nums.length - 1);return nums;}// 对数组进行递归的归并排序private void mergeSort(int[] nums, int left, int right) {// 1 与快排不同的是分割点直接选择中间位置int middle left (right - left) / 2;// 2 只要startend就一直进行归并if (left right) {// 2-1 先分别归并左右两边左右两边有序了则最终有序mergeSort(nums, left, middle);mergeSort(nums, middle 1, right);// 2-2 最后合并左右两边有序数组merge(nums, left, middle, right);}}// 单次划分的归并private void merge(int[] nums, int left, int middle, int right) {// 1 设置归并临时结果集,大小为归并后的总长度int[] result new int[right - left 1];// 2 定义两个排序数组的指针和结果集指针int i left;int j middle 1;int k 0;// 3 开始比较已排序集合值并将结果加入结果集while (i middle j right) {if (nums[i] nums[j]) {result[k] nums[i];} else {result[k] nums[j];}}// 4 如果有一个已经用完了补充另一个排序数组while (i middle) {result[k] nums[i];}while (j right) {result[k] nums[j];}// 5 需要把这一段合并后已排序结果合并到整体nums的分段上for (int index 0; index result.length; index) {nums[left index] result[index];}}}复杂度分析
时间复杂度O(NlogN)这里 N 是数组的长度 空间复杂度O(N)辅助数组与输入数组规模相当。
堆排序【MID】
最后做一道频度最低的题目堆排序
题干
题干与快排及归并排序一致
解题思路
这里简单介绍下数组中下标为 i 的节点的左子节点就是下标为 i∗2 的节点右子节点就是下标为 i∗21 的节点父节点就是下标为 2i 的节点
1 建堆
我们首先将数组原地建成一个堆。所谓“原地”就是不借助另一个数组就在原数组上操作。建堆的过程是从后往前处理数组并且每个数据都是从上往下堆化因为叶子节点往下堆化只能自己跟自己比较所以我们直接从最后一个非叶子节点开始依次堆化就行了
2 排序
建堆结束之后数组中的数据已经是按照大顶堆的特性来组织的。数组中的第一个元素就是堆顶也就是最大的元素。我们把它跟最后一个元素交换那最大元素就放到了下标为 n 的位置。这个过程有点类似上面讲的“删除堆顶元素”的操作当堆顶元素移除之后我们把下标为 n 的元素放到堆顶然后再通过堆化的方法将剩下的 n−1 个元素重新构建成堆。堆化完成之后我们再取堆顶的元素放到下标是 n−1 的位置一直重复这个过程直到最后堆中只剩下标为 1 的一个元素排序工作就完成了
代码实现
给出代码实现基本档案 基本数据结构数组 辅助数据结构无 算法堆排序 技巧双指针 import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param n int整型 the n* return int整型*/public int[] sortArray(int[] nums) {heapSort(nums);return nums;}// 1 堆排序函数private void heapSort(int[] nums) {// 1 构建大顶堆此时数组0的位置即为堆顶元素也就是数组最大值int heapSize nums.length;buildMaxHeap(nums, heapSize);// 2 将堆顶元素与数组末尾元素交换for (int i nums.length - 1; i 1; i--) {// 2-1 交换末尾元素与堆顶元素swap(nums, i, 0);// 2-2 缩小堆的生成范围不包含末尾元素因为末尾元素已调整完heapSize--;// 2-3 因为将一个末尾元素放到了堆顶且其不一定是剩余元素中最大的所以需要重新进行堆调整heapify(nums, 0, heapSize);}}// 2 构建大顶堆函数private void buildMaxHeap(int[] nums, int heapSize) {for (int i heapSize / 2; i 0; i--) {heapify(nums, i, heapSize);}}// 3 堆调整函数private void heapify(int[] nums, int i, int heapsize) {// 逐层的进行元素调整:这里包含号是因为要允许存在只有左节点的情况while (2 * i 1 nums.length) {// 1 确定节点的左右节点位置int leftChild 2 * i;int rightChild 2 * i 1;int maxPos 0;// 2 当前层进行堆调整获取(当前、左子节点、右子节点)中值最大的索引与堆顶进行交换maxPos i;if (leftChild heapsize nums[i] nums[leftChild] ) {maxPos leftChild;}if ( rightChild heapsize nums[maxPos] nums[rightChild] ) {maxPos rightChild;}// 3 如果maxPos不是i则交换if (i ! maxPos) {swap(nums, i, maxPos);// 继续下沉进行堆调整i maxPos;} else {break;}}}// 4元素交换方法private void swap(int[] numbers, int i, int j) {int temp numbers[i];numbers[i] numbers[j];numbers[j] temp;}
}复杂度分析
在堆排序算法中建立堆的时间复杂度通常为O(n)其中n是要排序的元素数量。这是因为堆的构建分为两个阶段堆的构建和堆的调整。 堆的构建首先将待排序的n个元素按照从左到右的顺序依次插入堆中这个过程是线性时间的即O(n)。 堆的调整然后需要对堆进行调整以满足堆的性质通常是最大堆或最小堆。这个调整阶段的时间复杂度取决于堆的高度通常为O(log n)。在堆排序的整个过程中堆的调整阶段需要执行n次所以总时间复杂度是O(n log n)。
总的来说堆排序的建堆阶段的时间复杂度是O(n)而排序阶段的时间复杂度是O(n log n)。因此堆排序的总时间复杂度为O(n n log n)通常被表示为O(n log n)因为在渐进分析中线性时间的操作通常被忽略。
由于堆是原地构建所以空间复杂度为ON
拓展知识分治算法、堆的基本概念、算法比较
1 分治算法
分治法是一种解决问题的算法设计范式它将一个问题分解成多个相似的子问题然后解决这些子问题并将它们的解合并以得出原始问题的解。分治法的核心思想是将大问题分解成更小的、相似的子问题通过解决子问题来解决原始问题。
分治法通常包含三个步骤分解Divide、解决Conquer、合并Combine。 分解Divide 将原始问题划分为更小、相似的子问题。这一步骤通常是递归地进行的即将问题逐步分解为更小规模的子问题。 解决Conquer 递归地解决子问题。当子问题足够小可以直接求解时就停止分解转而解决这些子问题。 合并Combine 将子问题的解合并以得出原始问题的解。这是分治法的关键步骤将各个子问题的解整合起来形成更大问题的解。
分治法通常用于解决一些可以被分解成相似子问题的问题如排序、搜索、求解最短路径等。典型的分治算法包括归并排序和快速排序。以下是一个分治法的示例
归并排序 分解Divide 将数组分成两半分别对这两半进行排序。 解决Conquer 对分解得到的子数组递归地进行排序直到子数组长度足够小。 合并Combine 将排好序的子数组合并得到完整的有序数组。
分治法的优点在于它可以将问题分解成独立的子问题每个子问题的求解都相对简单。这使得算法设计和理解变得更加清晰。然而分治法有时会在子问题的合并阶段引入额外的开销因此在设计分治算法时需要权衡分解和合并的成本。
堆的基本概念
在计算机科学中一个堆Heap通常指的是一种特殊的数据结构它是一种树状结构通常用于优先队列和堆排序等算法。
堆具有以下特点 完全二叉树结构堆通常是一棵完全二叉树这意味着树的所有层级都被填满除了最底层最底层的节点从左向右依次填充。这个特性使得堆可以有效地使用数组来表示因为树的节点可以在数组中按照特定的规则排列从而节省内存和提高访问效率。 堆序性质堆被维护为满足堆序性质Heap Property的树这意味着在最大堆Max Heap中对于任意节点i其父节点的值必须大于或等于i的值而在最小堆Min Heap中父节点的值必须小于或等于i的值。这个性质使得在堆中的根节点永远是最大值最大堆或最小值最小堆。
堆被广泛用于解决一些基本问题如 优先队列通过使用最小堆或最大堆可以实现高效的优先队列其中具有最高或最低优先级的元素在队列的顶部。 堆排序堆排序是一种基于堆数据结构的排序算法它利用堆的特性来进行排序。在堆排序中首先将未排序的元素构建为一个堆然后反复删除堆顶元素将其放入已排序部分直到堆为空。 调度算法堆可以用于操作系统中的进程调度其中具有最高优先级的进程被安排在最前面。 最短路径算法一些最短路径算法如Dijkstra算法使用最小堆来快速查找最小距离的节点。
总之堆是一种重要的数据结构它提供了高效的方式来管理数据特别是在需要按优先级对数据进行操作时。最大堆和最小堆分别用于找到最大值和最小值这使得堆在许多领域中非常有用。
3 排序算法比较
以下是快速排序、归并排序和堆排序的比较包括时间复杂度、空间复杂度和一些其他关键特点
特性快速排序归并排序堆排序时间复杂度平均情况 O(n log n)平均情况 O(n log n)平均情况 O(n log n)最坏情况 O(n^2)最坏情况 O(n log n)最坏情况 O(n log n)最佳情况 O(n log n)最佳情况 O(n log n)最佳情况 O(n log n)稳定性不稳定稳定不稳定空间复杂度平均情况 O(log n)平均情况 O(n)平均情况 O(1)最坏情况 O(n)最坏情况 O(n)最坏情况 O(1)适用性通常用于大型数据集通常用于大型数据集通常用于内存受限情况且需要稳定排序时分治策略是是是额外的数据移动较多较少较少需要的额外空间递归调用的栈空间辅助数组常数额外空间(in-place)实现复杂度中等中等相对较高
总结
快速排序通常在平均情况下具有较好的性能但在最坏情况下性能较差因此不适用于某些特定情况。归并排序具有一致的性能但需要较大的额外内存空间通常不适用于内存受限的情况。堆排序通常需要较少的额外内存空间但在排序稳定性和实现复杂性方面有一些局限性适合内存受限的情况。
选择排序算法应根据具体情况和性能要求来决定没有一种算法适用于所有情况。
4 稳定性分析
“稳定性是指排序算法在处理具有相等键值的元素时能否保持它们在原始序列中的相对顺序。一个排序算法被称为稳定”如果对于相等的元素它们的相对顺序在排序后仍然保持不变。相反如果排序算法不能保持相等元素的相对顺序那么它被称为不稳定。
下面是对快速排序、归并排序和堆排序的稳定性解释 快速排序快速排序是一个不稳定的排序算法。在快速排序中相等元素的相对顺序可能会发生变化具体取决于选择的划分策略和元素交换操作。 归并排序归并排序是一个稳定的排序算法。在归并排序中相等元素的相对顺序始终保持不变。这是因为在合并过程中如果有相等的元素它们会按照它们在原始数组中的顺序放置在合并后的数组中。 堆排序堆排序通常是一个不稳定的排序算法。虽然堆排序的堆构建过程可能会改变相等元素的相对顺序但在堆化和排序的过程中相等元素的相对顺序通常不会被保持。
稳定性在某些应用中很重要特别是在需要按多个条件进行排序或者需要保持原始数据的某种有序性时。在这些情况下稳定的排序算法更有用。如果稳定性不是关键因素那么可以选择性能更高的不稳定排序算法。
