首页天道酬勤java归并排序算法,归并排序算法流程

java归并排序算法,归并排序算法流程

admin 08-29 19:56 359次浏览

文章目录 一、归并排序介绍二、归并排序的思想2.1 归并排序的基本思想2.2 归并的基本步骤 三、归并排序的代码实现

一、归并排序介绍

归并排序(merge sorting)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide and conquer)策略。分治策略将问题分解(divide)分解为一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案合并在一起,即分而治之。

归并排序的时间复杂度为 O(nlogn)。

二、归并排序的思想 2.1 归并排序的基本思想

归并排序的基本思想如下图所示:

从上图可以看出来:归并排序主要分为两个部分——分、治。

对于分的部分,没有什么好研究的,简单来说就是把 n 个元素组成的一个序列最终分解为 n 个序列,每个序列只有一个元素。

对于治(也即合并)的部分,则是归并排序中最复杂的内容。

从上图可以看出来,由 8 个元素组成的序列分解完毕之后,在治的部分共合并了 7 次。那么这 7 次合并过程究竟是如何进行的呢?下面将具体讲解。

2.2 归并的基本步骤

从归并排序的基本思想图中我们可以得知:合并都是发生在相邻的两个有序子序列之间的。因此,我们只需要掌握有序子序列的合并过程,便可以推出完整的归并过程。

对于两个有序子序列的合并过程,基本都是按照以下步骤进行的:

首先为左子序列附设一个指针 left 指向左子序列的第一个元素,为右子序列附设一个指针 right 指向右子序列的第一个元素;附设一个临时数组 temp 用于临时存储排序后的结果;右子序列的指针 right 向右移动,在移动的过程中如果指向的元素小于 left 指向的元素,则将 arr[right] 记录在临时数组 temp 中;若右子序列的指针 right 移动过程指向的元素大于 left 指向的元素,则将 arr[left] 追加到临时数组 temp 中;左子序列的指针 left 再向右移动,若移动过程中指向的元素小于 right 指向的元素,则将 arr[left] 追加到 temp 中;若左子序列的指针 left 向右移动过程中指向的元素大于 right 指向元素,则将 arr[right] 追加到 temp 中;循环执行 3~6步,直到其中一个子序列中的元素都被记录完毕;然后将尚存在元素的子序列按顺序追加在 temp 数组中,将 temp 数组中的元素复制到原序列 arr 中,则两个有序子序列的合并正式完成。

从上面的步骤我们不难看出:它和两个有序链表的合并思想基本是一致的

【举例说明】

下面将用两个例子来具体描述一下两个有序序列的合并的过程。

以两个有序子序列 [4,8]、[5,7] 合并为例,过程如下:

再以两个有序子序列 [4,5,7,8]、[1,2,3,6] 合并为例,过程如下:

三、归并排序的代码实现

【案例需求】

假设待排序序列如下:

int[] arr = {8,4,5,7,1,3,6,2};

要求将上面的序列使用归并排序算法按照从小到大顺序排序。

【思路分析】

我们知道,归并排序中最复杂的代码就是两个有序子序列的合并过程,根据 2.2 示例中的图解,我们可以写出两个有序子序列合并的代码如下:

/** * 合并两个有序序列 * @param arr 两个子序列组成的原始数组,arr[left]~arr[mid] 为左子序列、arr[mid+1]~arr[last] 为右子序列 * @param left 指向左子序列的首个元素 * @param mid 指向左子序列的末尾元素 * @param last 指向待归并序列的最后一个元素 * @return void */public static void merge(int[] arr, int left, int mid, int last){ int i = left, j = mid + 1; // i 为左子序列起点,j 为右子序列起点 int m = mid, n = last; // m 为左子序列终点,n 为右子序列终点 int t = 0; // 临时数组索引int[] temp = new int[arr.length];// 临时数组 /* 把两个子序列组成的数组元素按照规则放入到 temp 数组中, 直到有一个子序列的元素被读完。 */ while(i<=m && j<=n) { if (arr[j] <= arr[i]) { temp[t] = arr[j]; t += 1; j += 1; } else { temp[t] = arr[i]; t += 1; i += 1; } } /* 哪个子序列元素有剩余,就都读取到 temp 中 */ while(i<=mid){ // 如果是左子序列还有剩余元素 /* 把剩余元素都填充到 temp */ temp[t]=arr[i]; t+=1; i+=1; } while(j<=last){ // 如果是右边的序列元素有剩余 /* 把剩余元素都填充到 temp */ temp[t]=arr[j]; t+=1; j+=1; } /* 从 temp 数组中 copy 数据到原数组 */ for (i=0; i<t; i++){ arr[left + i] = temp[i]; }}

合并的代码如上面所示。对于分解的代码则比较简单,就是递归调用归并方法,最后调用合并方法。

【代码实现】

完整的归并排序代码如下:

/** * 归并排序 * @param arr 待归并排序序列 * @param left 左子序列的起点 * @param last 右子序列的终点 */public static void mergeSort(int[] arr, int left, int last) { if(left < last) { int mid = (left + last) / 2; // 中间索引 mergeSort(arr, left, mid);// 左子序列递归 mergeSort(arr, mid + 1, last );// 右子序列递归 merge(arr, left, mid, last);// 合并 }}/** * 合并两个有序序列 * @param arr 两个子序列组成的原始数组,arr[left]~arr[mid] 为左子序列、arr[mid+1]~arr[last] 为右子序列 * @param left 指向左子序列的首个元素 * @param mid 指向左子序列的末尾元素 * @param last 指向待归并序列的最后一个元素 * @return void */public static void merge(int[] arr, int left, int mid, int last){ int i = left, j = mid + 1; // i 为左子序列起点,j 为右子序列起点 int m = mid, n = last; // m 为左子序列终点,n 为右子序列终点 int t = 0; // 临时数组索引int[] temp = new int[arr.length];// 临时数组 /* 把两个子序列组成的数组元素按照规则放入到 temp 数组中,直到有一个子序列的元素被读完。 */ while(i<=m && j<=n) { if (arr[j] <= arr[i]) { temp[t] = arr[j]; t += 1; j += 1; } else { temp[t] = arr[i]; t += 1; i += 1; } } /* 哪个子序列元素有剩余,就都读取到 temp 中 */ while(i<=mid){ // 如果是左子序列还有剩余元素 /* 把剩余元素都填充到 temp */ temp[t]=arr[i]; t+=1; i+=1; } while(j<=last){ // 如果是右边的序列元素有剩余 /* 把剩余元素都填充到 temp */ temp[t]=arr[j]; t+=1; j+=1; } /* 从 temp 数组中 copy 数据到原数组 */ for (i=0; i<t; i++){ arr[left + i] = temp[i]; } System.out.println("第" + ++x + "次合并后:" + Arrays.toString(temp));}

最终运行结果如下:

从运行结果可以看到,8 个元素的序列最终进行了 7 次合并,其中每次合并的结果可以对照归并排序的基本思想自行体会。

实时通信)的普及帖空格和标点符号?这是一篇RTC(Real-time Communicationsflink内存配置及优化
顺序表归并排序,归并排序解 归并排序c++代码,归并排序是稳定的排序算法吗
相关内容