当前位置：首页 > news >正文

卫浴网站模板高端网站开放

news 2025/9/19 12:59:32

卫浴网站模板,高端网站开放,安溪哪里有学做网站,新人怎么做跨境电商排序算法是数据结构与算法中最基本的算法之一，其作用就是将一些可以比较大小的数据进行有规律的排序，而想要实现这种排序就拥有很多种方法~ 那么我将通过几篇文章，将排序算法中各种算法细化的，详尽的为大家呈现出来： …

排序算法是数据结构与算法中最基本的算法之一，其作用就是将一些可以比较大小的数据进行有规律的排序，而想要实现这种排序就拥有很多种方法~

那么我将通过几篇文章，将排序算法中各种算法细化的，详尽的为大家呈现出来：

📚 非线性时间比较类：

📕 插入类排序：数据结构与算法之排序算法-插入排序-CSDN博客

📖 直接插入排序

📖 希尔排序

📕 交换类排序：数据结构与算法之排序算法-快速排序(分治)-CSDN博客

📖 冒泡排序

📖 冒泡排序-优化

📖 快速排序(Hoare，挖坑法，前后指针法)

📖 快速排序-优化

📕 选择类排序：数据结构与算法之排序算法-选择排序-CSDN博客

📖 简单选择排序

📖 堆排序

📕 归并类排序：[本篇]

📖 归并排序

📚 线性时间非比较类：

📕 非比较类排序：数据结构与算法之排序算法-(计数,桶,基数排序)-CSDN博客

📖 计数排序

📖 桶排序

📖 基数排序

一、归并排序

稳定性：稳定

时间复杂度：O(n logn)

额外空间复杂度：O(n)

归并排序也是一种在实际应用中比较常用的排序算法，这是因为它的速度和快速排序一样也是O(n logn)，并且相较于快速排序，归并排序还具有稳定性

但唯一的缺点就是归并排序并不是"原地算法"，而是需要开辟一个和原数组一样大小的辅助数组，所以归并排序的额外空间复杂度为O(n)

① 习题引入:合并排序的数组

首先，为什么要使用这题作为习题引入呢？我们先接着上面的话题，研究研究归并排序：

上面我们提到归并排序的时间复杂度为O(n logn)，从这里就不难猜出，归并排序的算法大概也是和快排类似，是一种"不断将数组分为两份"的排序算法，也就是"分治"

归并排序的基本思想：取数组的开始位置为left，结束位置为right，不断对数组取中间下标mid，使数组均匀的被分成两个新数组，并继续对新数组进行如上操作。

直到left == right(数组中只有一个元素)时，我们认为此时这个数组为有序数组，将它向上递归。按照这个思想，我们后续递归回去的数组也都是有序的，而如此便能够提到我们上面说的这道习题了："合并排序的数组"

📚 思路提示：

合并有序的数组想必对大家来说肯定非常简单的~毕竟我们之前在学习"链表"的时候就实现过类似的题目，而"合并有序链表"应该是比"合并有序数组"要更加复杂一点点的。

我们只需要创建一个新的数组 arr ，使他的长度等于两个数组之和，然后遍历两个数组，使用双指针的思想，用cur1遍历 arr1，用cur2遍历arr2，将较小的元素放入arr中，随后移动cur1/cur2。

(最后可能会有一个数组没被加入完，记得处理一下就好)

📖 代码示例：

class Solution {public void merge(int[] A, int m, int[] B, int n) {int[] nums = new int[m + n];int cur1 = 0;int cur2 = 0;int i = 0;while(cur1 < m && cur2 < n){nums[i++] = A[cur1] < B[cur2] ? A[cur1++] : B[cur2++];}while(cur1 < m) nums[i++] = A[cur1++];while(cur2 < n) nums[i++] = B[cur2++];for(i = 0;i < n + m;i++){A[i] = nums[i];}}
}

② 归并排序

而上面我们又提到了，将有序的数组向上递归，排序后再递归，这样多此递归下来，我们就能够得到我们想要的"有序数组"。

这样就正好验证了，归并排序的排序速度与其中数组的有序性并没有关系，也就是说它是稳定的O(n logn)的排序~

⭐ 图示：

📖 代码示例：

    public static int[] arr;public int[] sortArray(int[] nums) {arr = new int[nums.length];mergeSort(nums, 0, nums.length - 1);return nums;}public static void mergeSort(int[] array, int left, int right) {if (left >= right) {return;}int mid = left + (right - left) / 2;mergeSort(array, left, mid);mergeSort(array, mid + 1, right);int cur1 = left;int cur2 = mid + 1;int i = 0;while (cur1 <= mid && cur2 <= right) {arr[i++] = array[cur1] < array[cur2] ? array[cur1++] : array[cur2++];}while (cur1 <= mid) {arr[i++] = array[cur1++];}while (cur2 <= right) {arr[i++] = array[cur2++];}for (i = left; i <= right; i++) {array[i] = arr[i - left];}}