数据结构算法操作试题(C++/Python)：数据结构算法操作试题(C++/Python)——目录 ---- 1.
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/116194.html原文链接：https://javaforall.cn
20201201 题目: 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。...如果数组中不存在目标值 target，返回 [-1, -1]。 进阶: 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？...输入：nums = [], target = 0 输出：[-1,-1] 提示： 0 <= nums.length <= 105 -109 <= nums[i] <= 109 nums 是一个非递减数组...-109 <= target <= 109 抛砖引玉 思路： 一遍循环 一遍循环，记录数组中等于 target 元素的位置，如果变量到元素大于 target，则终止循环，直接返回结果 抛砖引玉 /**...return [left, right] } else { return [-1, -1] } } 博客: 前端小书童 每天的每日一题，写的题解会同步更新到公众号一天一大
步骤如下： 1）随机选其中一个元素，假设为a[i]，将所有值比a[i]小的元素，移到a[i]的左边，假设为数组b；所有比a[i]大的元素，移到a[i]的右边，假设为数组c。...二、问题分析 快速排序在众多排序算法中，属于非常优秀的算法，不过这几十年来，还是有许多人对其进行贡献，提供了一些很好的改进。...结束循环后，将a[i]和a[q]进行互换，实现将切分元素换到数组的中间位置。...代码如下： /** * 获取快速排序的切分元素，并进行部分排序，保证切分元素左侧元素都小，右侧都大 */ private static int partition(Comparable...经过上述方法，在获取切分元素的同时，实际上已经完成了以切分元素值为中值，对数组进行的切分。 如下图所示： ? 2、小数组排序 当数组元素较少，不采用快速排序。
每一条线代表一个数字，数字小向左倾斜，数字大就向右倾斜。（请注意，你可以对一组任何东西进行洗牌，不只是数字，但这种可视化编码对于显示元素的顺序很管用。...它的灵感来自于Robert Sedgwick的《用C语言实现的算法》中的排序可视化。 该算法把数组划分为两个部分，右半边是已洗牌区域（用黑色表示），左半边是待洗牌区域（用灰色表示）。...这个额外的空间用于归并排序的子数组，把来自子数组的每对元素组合在一起，同时保持顺序。由于归并排序运行副本而不是交换，因此我们必须相应地修改动画（或有误导读者的风险）。 归并排序自下而上进行。...最初，它合并大小为1的子数组，因为它们经过了排序。每个相邻的子数组：首先，只是一对元素，使用额外的数组合并为大小为2的排序子数组。然后，将大小为2的每个相邻排序子数组合并成大小为4的排序子数组。...Prim的算法通常使用堆来实现，这是用于对元素进行优先级排序的有效数据结构。 当一个新的单元格加入迷宫时，连接的边缘（以红色标示）被添加到堆。尽管边以任意顺序添加，堆允许快速除去最低加权边。
最后，第二个和第三个元素还会再次互换，得到最终顺序： 「A B D E H」 下图演示了如何对一个大的数字数据集合进行冒泡排序。在图中，我们分析了插入数组中的两个特定值：2 和 72。...交换时，我们用一个中间值来存储某一交换项的值。其他排序法也会用到这个方法，因此我们声明一个方法swap放置这段交换代码以便重用。 有时候我们在循环的中间迭代时已经完成了排序。...然而，在实际情况中，归并排序还有一些问题，当我们用这个算法对一个很大的数据集进行排序时，我们需要相当 大的空间来合并存储两个子数组。...接着，算法对划分后的小数组（较主元小的值组成的子数组，以及较主元大的值组成的子数组）重复之前的两个步骤，直至数组已完全排序。...算法的步骤如下： 找出待排序的数组中最大和最小的元素 统计数组中每个值为i的元素出现的次数，存入数组C的第i项 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加） 反向填充目标数组：将每个元素
一、概念 快速排序算法由 C. A. R. Hoare 在 1960 年提出。...我们先编写一下操作的主要部分，就是选出一个基准，这个基准的左边的数值比基准值小，而右边的值比基准值大或者相等。...] return pivotIndex; }; 代码以最后一个元素为基准，用变量 pivotIndex 来跟踪“中间”位置，这个位置左侧的所有元素都比 pivotValue 小，而右侧的元素都比...，之后对左右两个子数组进行分区。...(pivotIndex - 1); } // 如果基准的右侧有未排序的元素， // 则将该子数组添加到栈中，以便稍后对其进行排序
） 每次共带排序数组中选择一个最小值的数组元素（若从大到小的顺序，每次选择最大值的数组元素） 将这个数组元素的值与最前面还未排序的数组元素的值进行交换，直到整个数组都是已排序的数组元素为止 程序定义了两个循环变量...，内层for循环对当前某轮剩余未排序元素进行选择排序。...小编给大家推荐一个学习氛围超好的地方，C/C++交流企鹅裙：870963251！适合在校大学生，小白，想转行，想通过这个找工作的加入。...接下来，我们就对三种排序方法做个小比较 1 。...冒泡法排序 在小例中，使用flag作为判断终止循环的条件。
前言 我们在页面上渲染数据时，通常会根据特定规则来对数据进行一个排序，然后再将其渲染到页面展示给用户。 那么对数据进行排序有很多种方式，哪一种效率高？哪一种稳定性好？那一种占用内存小？...对左右两部分继续执行分割 合并数组: 我们将数组分割完后，对小数组进行排序，然后将其合并成大数组并返回。...分布式排序使用已组织好的辅助数据结构，然后进行合并，得到排好序的数组。计数排序使用一个用来存储每个元素在原始数组中出现次数的临时数组。...，然后将目标值和找到的值进行大小比较，如果比中间值大就往中间值的右边找，否则就往中间值的左边找。...实现思路 选择数组的中间值 如果选中值是待搜索值，那么算法执行完毕 如果待搜索值比选中值要小，则返回步骤1并在选中值左边的子数组中寻找（较小） 如果待搜索值比选中值要大，则返回步骤1并在选中值右边的子数组中寻找
快速排序的基本思想是任取待排序序列的一个元素作为中心元素(可以用第一个，最后一个，也可以是中间任何一个)，习惯将其称为pivot，枢轴元素； 将所有比枢轴元素小的放在其左边； 将所有比它大的放在其右边...； 形成左右两个子表； 然后对左右两个子表再按照前面的算法进行排序，直到每个子表的元素只剩下一个。...将一个数组分成两个数组的方法为： 先从数组右边找到一个比枢轴元素小的元素，将数组的第一个位置赋值为该元素； 再从数组的左边找到一个比枢轴元素大的元素，将从上面取元素的位置赋值为该值； 依次进行，直到左右相遇...排序全过程 代码 对每一个数组进行分化的代码如下： 初始化pivot为数组第一个元素； 只要left还小于right就进行循环； 外层循环内部如下： 先从右边找一个比枢轴元素小的元素； 将当前...这样的话，长度为n的数组需要经过n趟划分，这时的时间复杂度为O(n^2)； 为改善最坏情况下的时间性能，可以在最枢轴元素的原则中进行优化，选第一个元素，最后一个元素，中间元素中的中位数即可。
快速排序的基本思想是任取待排序序列的一个元素作为中心元素(可以用第一个，最后一个，也可以是中间任何一个)，习惯将其称为pivot，枢轴元素； 将所有比枢轴元素小的放在其左边； 将所有比它大的放在其右边；...将一个数组分成两个数组的方法为： 先从数组右边找到一个比枢轴元素小的元素，将数组的第一个位置赋值为该元素； 再从数组的左边找到一个比枢轴元素大的元素，将从上面取元素的位置赋值为该值； 依次进行，直到左右相遇...排序全过程 代码 对每一个数组进行分化的代码如下： 初始化pivot为数组第一个元素； 只要left还小于right就进行循环； 外层循环内部如下： 先从右边找一个比枢轴元素小的元素； 将当前left...right小，进行一次划分，将返回来的值赋值给middle； 对left到middle - 1的部分进行一次快排（递归进行）； 对middle + 1到right的部分进行一次快排（递归进行）。...这样的话，长度为n的数组需要经过n趟划分，这时的时间复杂度为； 为改善最坏情况下的时间性能，可以在最枢轴元素的原则中进行优化，选第一个元素，最后一个元素，中间元素中的中位数即可。
这里将引入一些著名的算法进行介绍，每一个都是经典，值得收藏。 排序算法（数组） 排序算法可能是最基础、最适合算法入门的经典算法，在面试中经常会问到排序算法及其相关的问题。...如果第一个比第二个大，就交换它们两个；对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；针对所有的元素重复以上的步骤，除了最后一个；重复上述步骤，直到排序完成...算法描述为：从数列中挑出一个元素，称为"基准"，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。...算法思路是：找到数组的中间元素坐标并记录，将需要查找的元素跟中间元素进行比较，如果大于中间元素，则截取中间元素以后的所有元素作为新的数组，将中间元素设为新数组的起始元素，如果小于中间元素，则截取中间元素以前的所有元素作为新的数组...然后再在新的数组中找到中间元素，继续进行比较，如果中间元素等于目标值则返回输出。
快速排序（QuickSort）是对冒泡排序的一种改进。由 C. A. R. Hoare 在1962年提出。...它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列...在现在内存空间比较大的情况下，可以考虑下面这种算法（通过Python代码做了示例）： 从数组 A 中取一个中间值 t，创建两个数组B、C，一个（B）用来存放小于 t 的数据，另一个（C）用来存放大于 t...遍历数组 A 并与中间值 t 进行比较，将小于中间值的数据放入数组 B，将大于中间值的数据放入数组 C。 对数组 B、C 按照1、2步进行排序。 将 B、t、C组合后输出为排序后的结果。...保持最大值低于这些关键数据，最小值高于这些关键数据，从而避免对已经有序的中间的数据进行重排。完成后，数组的中间空位必然空出，把这个buffer写入数组中间空位。
归并排序就是分治思想的一种体现，归并排序的操作如下，假设给定一个数组num，需要对它排序，首先将数组分成两半部分，对这两半部分分别进行归并排序。...它们分别指向了待合并的两个子序列的 //第一个元素，然后比较这两个元素的大小(我在这里排序的结果是从小到大的),将小的那个元素放到 //备用数组中。...快速排序是使得下标s之前的元素都比num[s]小，在s之后元素都比num[s]大。...这样我们把num[s]的位置就确定下来了，然后对num[s]之前的元素进行快速排序，也对num[s]之后的元素快速进行排序。这样就把一个序列的顺序排好了。...关于s的选择策略有很多，其中较为简单的一种是选择第一个元素，中间元素，最后一个元素这三者的中值作为num[s]。 例：给定一个序列，输出它的前m的大的数，要求从大到小输出。
归并排序 核心思想：将数组从中间分成前后两部分，然后对前后两部分分别进行排序，再将排序好的两个部分有序合并在一起，这样整个数组有序。...全文图示来源于王争的《数据结构和算法之美》 image.png 归并排序使用的就是分治思想。分治，顾名思义，就是分而治之，讲一个大的问题分解成小的问题来解决，小的问题解决了大的问题也就解决了。...快速排序 核心思想：选取一个基准元素 pivot，比 pivot 小的放到左边，比 pivot 大的放到右边，对 pivot 左右两边的序列递归进行以上操作。...，这里用C++实现一遍，这里的 partition 非常巧妙而且容易理解，取最后元素为基准 pivot，i 开始取值 l，j 从 l 遍历至 h-1，当 A[j] < pivot 时，交换 A[i] 和...，而且不需要将数组全部排序，只要求出第 k 大的值即可，非常高效。
我们一起来看看十大基础算法吧~ 算法一：快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(nlogn) 次比较。...重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。...搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。...算法五：BFPRT(线性查找算法) BFPRT 算法解决的问题十分经典，即从某 n 个元素的序列中选出第 k 大（第 k 小）的元素，通过巧妙的分析，BFPRT 可以保证在最坏情况下仍为线性时间复杂度。...若 i==k，返回 x；若 ik，在大于 x 的元素中递归查找第 i-k 小的元素。 终止条件：n=1 时，返回的即是 i 小元素。
5、选择排序： 选择排序在某些地方和冒泡排序相似：第一次选出最大（最小）的元素置于数组开头，第二次选出第二大（第二小）的元素置于数组第二个位置。。。直到所有的元素都有序。...*/ a[i] = temp; // 把基数放在中间，比基数小的数在左边，比基数大的数在右边 quickSort(a, left, i - 1); quickSort(a,...7、归并排序： 其实归并排序和快速排序有点像，因为归并排序也是通过分治递归来实现的，但是归并排序是先通过分治递归将所有的数组元素都分成一个个独立的元素个体，之后通过合并函数按照从小到大（从大到小）来进行和并...int b[N]; // 合并两组数用的中间数组 // 合并左右两边的数组元素，数组元素的交换在这里进行 void merge(int left, int mid, int right) {...如果是从大到小进行堆排序，那么我们需要建立最大堆，然后不断取出堆顶元素并对堆进行维护，直到堆为空。
排序的复杂度与稳定性 直接排序与希尔排序 直接插入排序 我们在玩扑克牌的时候，每次抓一张牌都要放在适合的位置，比如我就喜欢左边大右边小，这就算是插入排序。...gap越大，虽然大的数据和小的数据排序越快，但是顺序越乱，gap越小则相反。 那么让最初的gap等于数组长度，每次除以3，进行越来越细致的预处理。...选择排序 选择排序 选择排序是从左向右或者是从右向左开始选择一个最小的数然放在左边或者是右边，然后再选剩下的数中最小的数放在左边或者是右边： 这里我们选择对这个数组进行升序，第一次在整个数组里面找最小的...例： 这里key我选的是数组中第一个值，R找比key小的，L找比key大的，如果R找到的值比key找到的小就与L位置进行交换（但是key值只在R与L相遇才会换位置），就像这样，假如R先走，就先和key...比如高考的时候，全国有很多分数相同的同学，但是我想先看谁语文分数高，然后在进行总分的排序，如果用一个稳定的排序就不会打乱原来的排序。
如果前一个比后一个大，就交换它们两个； 2）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数； 3）针对所有的元素重复以上的步骤，除了最后一个； 4）重复步骤...这样在递归排序区间的时候，我们就不必再对第二部分元素均相等的区间进行快排了，这在待排序列存在大量相同元素的情况下能大大提高快排效率。 来看下面的三路划分示意图： ?...此时 a[j] 就是数组的第 j 小的元素，我们可以转换一下题意，第 k 大的元素就是第 nums.size() - k 小的元素。...② 算法描述 1）找出待排序的数组中最大和最小的元素； 2）统计数组中每个值为 i 的元素出现的次数，存入数组C的第i项； 3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；...4）反向填充目标数组：将每个元素 i 放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
在对快速排序进行优化前，先让我们回顾一些快速排序的思想： 快速排序就是分而治之思想的体现，将有序序列分成对立的两部分，一部分值都比关键字值小，一部分值都比关键字值大，再分别对两部分进行排序 对快速排序不了解的可以先看看快速排序的具体过程和代码讲解...int partition(int arr[],int len,int low,int high) { int pivotkey; //用数组的第一个元素做关键值 pivotkey = arr[...如果数组非常小，其实快速排序不如直接插入排序来得更好（直接插入排序是简单排序中性能最好的） 因为快速排序需要用到递归操作，对于大量数据操作时，这点性能影响对于它的整体算法优势而言可以忽略不计，但如果数组只有几个数据需要排序的时候...)//当high-low大于常数时用快速排序 { //获取当前关键值的位置（在数组中的下标） pivot=partition(arr, len, low, high); //分别对关键值前面较小部分和后面较大部分进行排序...小于等于常数时用直接插入排序 { //当某一部分子序列长度小于常数时，就用直接插入排序进行排序操作 InsertSort(arr,high,low); } } //升序 void QuickSort
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
实时音视频
即时通信 IM
对象存储
