算法-排序与双指针

news/2024/10/31 5:29:13/

n平方复杂度的排序有哪些?

n平方复杂度的排序算法包括:

  1. 冒泡排序(Bubble Sort):比较相邻的元素,如果前一个比后一个大,就交换它们的位置,重复进行直到排序完成。

  2. 选择排序(Selection Sort):每次从未排序的元素中选择最小的元素,放到已排序的末尾,重复进行直到排序完成。

  3. 插入排序(Insertion Sort):将未排序的元素插入到已排序的合适位置,重复进行直到排序完成。

  4. 希尔排序(Shell Sort):将待排序的元素按照一定的间隔分组,对每组进行插入排序,逐渐缩小间隔,直到间隔为1,最后进行一次插入排序。

  5. 快速排序(Quick Sort):选择一个基准元素,将小于基准元素的放在左边,大于基准元素的放在右边,对左右两个子序列递归进行快速排序。

这些排序算法的时间复杂度都是O(n^2),其中冒泡排序、选择排序和插入排序是比较简单的排序算法,但效率较低,适用于小规模数据的排序;希尔排序是插入排序的改进版,效率比前三种算法要高一些;快速排序是一种高效的排序算法,虽然最坏情况下时间复杂度也是O(n^2),但平均情况下时间复杂度为O(nlogn),是常用的排序算法之一。

 如何实现冒泡排序,如何进行优化?

冒泡排序是一种简单的排序算法,其基本思想是通过相邻元素之间的比较和交换来将较大的元素逐步“冒泡”到数组的末尾,从而实现排序。具体实现过程如下:

  1. 从数组的第一个元素开始,依次比较相邻的两个元素,如果前一个元素比后一个元素大,则交换它们的位置。

  2. 继续比较下一对相邻元素,重复上述操作,直到将最大的元素“冒泡”到数组的末尾。

  3. 重复执行上述操作,直到整个数组排序完成。

以下是一个简单的JavaScript实现冒泡排序的示例代码:

function bubbleSort(arr) {const len = arr.length;for (let i = 0; i < len - 1; i++) {for (let j = 0; j < len - i - 1; j++) {if (arr[j] > arr[j + 1]) {[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];}}}return arr;
}

 在这个实现中,bubbleSort函数接受一个数组arr作为参数,并返回一个排序后的数组。这个函数使用两层循环来实现冒泡排序,外层循环控制排序的轮数,内层循环控制每一轮比较的次数。如果相邻的两个元素顺序不对,则交换它们的位置。

冒泡排序的时间复杂度为O(n^2),在处理大规模数据时效率较低。为了提高冒泡排序的效率,可以进行以下优化:

  1. 设置标志位:如果在一轮排序中没有发生任何交换,说明数组已经有序,可以直接退出循环。

  2. 设置边界:每一轮排序后,最后一个元素已经是有序的,可以将下一轮排序的边界设置为上一轮排序的最后一个元素。

  3. 鸡尾酒排序:在冒泡排序的基础上,每一轮排序既从左往右进行比较和交换,又从右往左进行比较和交换,可以更快地将较小的元素“冒泡”到数组的前面。

这些优化可以提高冒泡排序的效率,但时间复杂度仍然是O(n^2)。因此,在处理大规模数据时,应该选择更高效的排序算法。

如何实现选择排序和插入排序? 

选择排序

选择排序的基本思想是每次从未排序的元素中选择最小的元素,将其放到已排序的元素末尾。具体实现过程如下:

  • 从数组的第一个元素开始,依次遍历数组中的每个元素,将当前元素设为最小值。

  • 继续遍历数组,如果找到比当前元素更小的元素,则将其设为最小值。

  • 遍历完成后,将最小值与数组的第一个元素交换位置,将其放到已排序的元素末尾。

  • 重复执行上述操作,直到整个数组排序完成。

以下是一个简单的JavaScript实现选择排序的示例代码:

function selectionSort(arr) {const len = arr.length;for (let i = 0; i < len - 1; i++) {let minIndex = i;for (let j = i + 1; j < len; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];}return arr;
}

 在这个实现中,selectionSort函数接受一个数组arr作为参数,并返回一个排序后的数组。这个函数使用两层循环来实现选择排序,外层循环控制排序的轮数,内层循环控制每一轮比较的次数。在每一轮比较中,找到未排序元素中的最小值,并将其放到已排序元素的末尾。

选择排序的时间复杂度为O(n^2),与冒泡排序相同。但是,选择排序的交换次数比冒泡排序少,因此在某些情况下,选择排序的效率可能会更高。

插入排序

插入排序的基本思想是将未排序的元素插入到已排序的元素中,使得已排序的元素仍然有序。具体实现过程如下:

  • 从数组的第二个元素开始,依次遍历数组中的每个元素,将当前元素插入到已排序的元素中。

  • 在已排序的元素中,从后往前遍历,找到当前元素应该插入的位置。

  • 将当前元素插入到已排序的元素中,使得已排序的元素仍然有序。

  • 重复执行上述操作,直到整个数组排序完成。

以下是一个简单的JavaScript实现插入排序的示例代码:

function insertionSort(arr) {const len = arr.length;for (let i = 1; i < len; i++) {let j = i;while (j > 0 && arr[j] < arr[j - 1]) {[arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];j--;}}return arr;
}

在这个实现中,insertionSort函数接受一个数组arr作为参数,并返回一个排序后的数组。这个函数使用两层循环来实现插入排序,外层循环控制排序的轮数,内层循环控制每一轮比较的次数。在每一轮比较中,找到当前元素应该插入的位置,并将其插入到已排序的元素中。

插入排序的时间复杂度为O(n^2),与冒泡排序和选择排序相同。但是,插入排序的交换次数比冒泡排序和选择排序少,因此在某些情况下,插入排序的效率可能会更高。

n*logn复杂读的排序有哪些?

n*logn复杂度的排序算法有以下几种:

  1. 快速排序

快速排序是一种基于分治思想的排序算法,其基本思想是选择一个基准元素,将数组分成两个子数组,其中一个子数组中的所有元素都小于基准元素,另一个子数组中的所有元素都大于基准元素。然后递归地对子数组进行排序,最终将整个数组排序完成。快速排序的时间复杂度为O(n*logn),但是在最坏情况下,时间复杂度可能会退化为O(n^2)。

    2. 归并排序

归并排序是一种基于分治思想的排序算法,其基本思想是将数组分成两个子数组,递归地对子数组进行排序,然后将两个有序的子数组合并成一个有序的数组。归并排序的时间复杂度为O(n*logn),但是需要额外的空间来存储临时数组。

   3. 堆排序

堆排序是一种基于堆的数据结构的排序算法,其基本思想是将数组构建成一个堆,然后依次将堆顶元素取出并放到已排序的元素中。堆排序的时间复杂度为O(n*logn),但是需要额外的空间来存储堆。

   4.希尔排序

希尔排序是一种基于插入排序的排序算法,其基本思想是将数组分成若干个子数组,对每个子数组进行插入排序,然后逐步缩小子数组的范围,最终将整个数组排序完成。希尔排序的时间复杂度为O(n*logn),但是其时间复杂度的分析比较困难。

以上是常见的n*logn复杂度的排序算法,它们都具有较高的效率和稳定性,可以应用于各种排序场景。

如何实现快速排序和归并排序?

快速排序的实现:

  1. 选择一个基准元素,通常选择第一个或最后一个元素。
  2. 将数组分成两个子数组,其中一个子数组中的所有元素都小于基准元素,另一个子数组中的所有元素都大于基准元素。
  3. 递归地对子数组进行排序,最终将整个数组排序完成。

代码实现:

void quickSort(int arr[], int left, int right) {int i = left, j = right;int tmp;int pivot = arr[(left + right) / 2];/* partition */while (i <= j) {while (arr[i] < pivot)i++;while (arr[j] > pivot)j--;if (i <= j) {tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;i++;j--;}};/* recursion */if (left < j)quickSort(arr, left, j);if (i < right)quickSort(arr, i, right);
}

 归并排序的实现:

  1. 将数组分成两个子数组。
  2. 递归地对子数组进行排序。
  3. 将两个有序的子数组合并成一个有序的数组。

代码实现:

void merge(int arr[], int left, int mid, int right) {int i, j, k;int n1 = mid - left + 1;int n2 = right - mid;/* create temp arrays */int L[n1], R[n2];/* copy data to temp arrays L[] and R[] */for (i = 0; i < n1; i++)L[i] = arr[left + i];for (j = 0; j < n2; j++)R[j] = arr[mid + 1 + j];/* merge the temp arrays back into arr[left..right]*/i = 0; /* initial index of first subarray */j = 0; /* initial index of second subarray */k = left; /* initial index of merged subarray */while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];i++;}else {arr[k] = R[j];j++;}k++;}/* copy the remaining elements of L[], if there are any */while (i < n1) {arr[k] = L[i];i++;k++;}/* copy the remaining elements of R[], if there are any */while (j < n2) {arr[k] = R[j];j++;k++;}
}void mergeSort(int arr[], int left, int right) {if (left < right) {int mid = left + (right - left) / 2;/* sort first and second halves */mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);/* merge the sorted halves */merge(arr, left, mid, right);}
}

复杂度为n的排序算法有哪些?具体的思路是什么样的?

复杂度为n的排序算法有计数排序、桶排序和基数排序。计数排序的思路是统计每个元素出现的次数,然后根据元素出现的次数将元素放入相应的位置。具体实现时,需要先确定待排序数组中最大元素的值max,然后创建一个长度为max+1的计数数组count,遍历待排序数组,统计每个元素出现的次数,最后根据计数数组将元素放入相应的位置。

桶排序的思路是将待排序数组分成若干个桶,每个桶内部使用其他排序算法进行排序,最后将所有桶中的元素按照顺序依次放入待排序数组中。具体实现时,需要先确定桶的数量和每个桶的范围,然后遍历待排序数组,将每个元素放入相应的桶中,最后对每个桶内部使用其他排序算法进行排序,最后将所有桶中的元素按照顺序依次放入待排序数组中。

基数排序的思路是将待排序数组按照位数从低到高依次进行排序,具体实现时,需要先确定待排序数组中最大元素的位数maxDigit,然后从个位开始,对每一位进行排序,最后得到有序数组。具体实现时,可以使用桶排序对每一位进行排序,也可以使用计数排序对每一位进行排序。

快速排序和归并排序的区别是什么?

快速排序和归并排序都是常用的排序算法,它们的区别主要在于排序的方式和实现方法。快速排序的思路是选取一个基准元素,将待排序数组分成两部分,一部分小于基准元素,一部分大于基准元素,然后对这两部分分别进行递归排序,最后将排序好的两部分合并起来。具体实现时,可以选取第一个元素或者随机选取一个元素作为基准元素,然后使用双指针法将数组分成两部分,再递归排序这两部分。

归并排序的思路是将待排序数组分成若干个子数组,对每个子数组进行排序,然后将排好序的子数组合并起来,最终得到有序数组。具体实现时,可以使用递归将数组分成两部分,对每个子数组进行排序,然后使用归并操作将排好序的子数组合并起来。

快速排序的时间复杂度为O(nlogn),空间复杂度为O(logn),归并排序的时间复杂度也为O(nlogn),但空间复杂度为O(n)。因此,在空间有限的情况下,快速排序更适合使用;而在空间充足的情况下,归并排序更适合使用。

返回arr的最长无重复元素子数组的长度

可以使用滑动窗口的思想来解决这个问题。定义一个左指针left和一个右指针right,表示当前子数组的左右边界。遍历数组,每次将右指针向右移动一位,如果当前元素不在子数组中,则将右指针继续向右移动;如果当前元素在子数组中,则将左指针向右移动,直到子数组中不包含当前元素为止。每次移动右指针时,都记录当前子数组的长度,并更新最长无重复元素子数组的长度。最终返回最长无重复元素子数组的长度即可。

具体实现时,可以使用一个哈希表来记录每个元素最后一次出现的位置,如果当前元素在哈希表中已经存在,则更新左指针的位置为当前元素最后一次出现的位置加一。每次移动右指针时,都更新当前元素的最后一次出现位置。时间复杂度为O(n),空间复杂度为O(n)。以下是代码实现:

function maxLength(arr) {let left = 0, right = 0, maxLen = 0;const map = new Map();while (right < arr.length) {if (map.has(arr[right]) && map.get(arr[right]) >= left) {left = map.get(arr[right]) + 1;}map.set(arr[right], right);maxLen = Math.max(maxLen, right - left + 1);right++;}return maxLen;
}

无重复最长子串

可以使用滑动窗口的思想来解决这个问题。定义一个左指针left和一个右指针right,表示当前子串的左右边界。遍历字符串,每次将右指针向右移动一位,如果当前字符不在子串中,则将右指针继续向右移动;如果当前字符在子串中,则将左指针向右移动,直到子串中不包含当前字符为止。每次移动右指针时,都记录当前子串的长度,并更新最长无重复字符子串的长度。最终返回最长无重复字符子串即可。

具体实现时,可以使用一个哈希表来记录每个字符最后一次出现的位置,如果当前字符在哈希表中已经存在,则更新左指针的位置为当前字符最后一次出现的位置加一。每次移动右指针时,都更新当前字符的最后一次出现位置。时间复杂度为O(n),空间复杂度为O(n)。以下是代码实现:

function maxLength(str) {let left = 0, right = 0, maxLen = 0;const map = new Map();while (right < str.length) {if (map.has(str[right]) && map.get(str[right]) >= left) {left = map.get(str[right]) + 1;}map.set(str[right], right);maxLen = Math.max(maxLen, right - left + 1);right++;}return maxLen;
}

最长上升子序列

最长上升子序列问题是指在一个给定的序列中,找到一个最长的子序列,使得这个子序列中的元素是递增的。可以使用动态规划来解决这个问题。

定义一个数组dp,其中dp[i]表示以第i个元素为结尾的最长上升子序列的长度。初始时,dp数组中的每个元素都为1,因为每个元素本身都可以作为一个长度为1的上升子序列。

然后遍历整个序列,对于每个元素i,从0到i-1遍历之前的元素j,如果当前元素i大于元素j,说明可以将元素i加入到以元素j为结尾的最长上升子序列中,此时更新dp[i]的值为dp[j]+1。最终dp数组中的最大值即为最长上升子序列的长度。

时间复杂度为O(n^2),空间复杂度为O(n)。以下是代码实现:

function lengthOfLIS(nums) {const n = nums.length;if (n === 0) {return 0;}const dp = new Array(n).fill(1);for (let i = 1; i < n; i++) {for (let j = 0; j < i; j++) {if (nums[i] > nums[j]) {dp[i] = Math.max(dp[i], dp[j] + 1);}}}return Math.max(...dp);
}

盛水最多的容器 

盛水最多的容器问题是指在一个给定的数组中,找到两个数,使得它们组成的容器可以盛最多的水。可以使用双指针来解决这个问题。

定义两个指针left和right,分别指向数组的左右两端。计算当前容器的容量,即min(height[left], height[right]) * (right - left),并更新最大容量maxArea的值。然后移动指针,如果height[left] < height[right],则left++,否则right--。重复上述步骤直到left >= right。

时间复杂度为O(n),空间复杂度为O(1)。以下是代码实现:

function maxArea(height) {let left = 0;let right = height.length - 1;let maxArea = 0;while (left < right) {const area = Math.min(height[left], height[right]) * (right - left);maxArea = Math.max(maxArea, area);if (height[left] < height[right]) {left++;} else {right--;}}return maxArea;
}


http://www.ppmy.cn/news/347904.html

相关文章

如何进行App性能测试?SoloPi是最佳选择!

目录 引言 SoloPi简介 SoloPi特点 SoloPi的主要功能 下载SoloPi 安装SoloPi 使用SoloPi进行性能测试 性能数据查看与记录 环境加压 响应耗时计算工具 注意事项 Solopi提供的各项性能指标介绍 引言 大家好&#xff01;我是凡哥。 今天我想跟你们分享一下如何进行A…

联想y7000p怎么开启高性能模式?

联想用户应该都知道联想拯救者Y7000P配备了好几个性能模式&#xff0c;用户可以根据需求进行开启。那联想y7000p拥有几个性能模式呢&#xff1f;联想y7000p要如何开启高性能模式呢&#xff1f;下面就来一起瞧瞧。 一、联想拯救者Y7000P拥有的性能模式 联想拯救者Y7000P 2021款有…

计算机win7开超级性能模式,笔记本win10系统开启超级性能模式(卓越性能模式)的方法...

在笔记本win10系统中&#xff0c;自带有超级性能模式&#xff0c;也就是卓越性能模式&#xff0c;如果要让电脑使用更加流畅的话&#xff0c;就可以开启超级性能模式(卓越性能模式)&#xff0c;但是许多用户却不知道要怎么开启超级性能模式(卓越性能模式)&#xff0c;针对这个问…

高性能模式消失不见 的解决方法

解决方法 以管理员身份运行cmd命令提示符&#xff0c;输入powercfg -s 8c5e7fda-e8bf-4a96-9a85-a6e23a8c635c&#xff0c;再回车&#xff0c;高性能模式就恢复了。对CSDN某些文章的吐槽 以上方法是我用了有效的&#xff0c;但是CSDN里好几篇文章&#xff0c;他们说用reg add H…

如何配置高性能的计算机,笔记本电脑如何设置电源计划为高性能

笔记本电脑设置高性能模式&#xff0c;能更好的提升和发挥笔记本性能&#xff0c;但同时要付出的代价就是会增加笔记本的功效&#xff0c;不建议大家在没有接通电源的情况下使用&#xff0c;因为很快会让笔记本没电。由于一些游戏用户想要高笔记本性能、流畅的玩游戏&#xff0…

提升计算机性能的方式,提升电脑性能的几个方法,如果电脑越用越卡,不妨试试看...

提升电脑性能的几个方法&#xff0c;如果电脑越用越卡&#xff0c;不妨试试看 首先在相同的硬件下&#xff0c;如果要想获得更好的性能肯定会有较高的功耗&#xff0c;所以很多设置对笔记本用户来说就要考虑下了&#xff0c;因为对续航和电池寿命都可能会有影响。除非天天是插电…

win10笔记本电源的高性能找不到

虽然我是程序员噻&#xff0c;但是呢&#xff0c;有时候我也是研究电脑的 在自己使用win10还没有装过系统的时候&#xff0c;是有电源的高性能的 但是呢&#xff0c;重装之后&#xff0c;就死活找不到了&#xff0c;好像隐藏了噻 解决的方法来了&#xff0c;如下&#xff1a…

《五》TypeScript 中类的类型

在 TypeScript 中&#xff0c;类的属性必须要明确声明&#xff0c;否则会报错。 class Person {// 在 TypeScript 中类的属性必须要明确声明&#xff0c;否则会报错// 声明属性的同时可以初始化值&#xff1b;或者也可以直接初始化值&#xff0c;此时会默认进行类型推断name: …