8.2.46 二路归并排序设计思路

请简述冒泡排序和二路归并排序的算法思想。

冒泡排序和二路归并排序的原理都是基于最大最小(或者是平均)原则。

因为它们均要求前n个比较次数，也就是说一旦有n个相同的元素，我们希望找到所有这些元素中，下标在前的元素，且把这些元素按升序排列起来。

(1)从性能角度出发，我们需要衡量每一比较次数对于整个搜索的影响，因此我们希望排序算法是尽可能的快。

(2)在尽可能快的前提下，还需要尽可能的将结果保持紧凑，即希望排序后的结果尽可能的简单易懂。

这里的简单易懂是指排序算法尽可能的不依赖于上下文，以及排序后的结果尽可能地独立于搜索空间。

二者均采用了单向链表结构，因此其数据结构均属于2-8树。

对比(1)、(2)，从性能的角度来看，冒泡排序可以明显优于二路归并排序。

当然，二者也具有各自的缺点，这里不再赘述。

二路归并排序是将元素映射到二路链表上，而冒泡排序则是将元素映射到一个双向链表上。

二者也存在很多共同的特点，下面分别进行介绍。

(1)与冒泡排序一样，二路归并排序也需要将待排序的元素映射到一个链表上，但是二路归并排序将每个待排序的元素依次对应到一个单独的比较次数中，因此它的比较次数是无序的。

(2)二路归并排序仅仅使用了链表结构，因此它的搜索速度与链表本身的数据结构相关，二路归并排序对比较次数的限制也更加严格，搜索速度也相对较慢。

(3)二路归并排序的比较次数具有严格的顺序性，即每个比较次数的下标只能在链表的上升方向的元素中，当链表上的元素已经达到最大值时，该元素的下标仍然必须在链表的上升方向的元素中。

二者各有优劣。

对于普通的非稀疏性文件，文件容量较小，通常可以采用冒泡排序。

对于文件容量较大，即记录较多的文件，如果采用冒泡排序，效率会很低，因此，二路归并排序显得更有优势。

由于冒泡排序对比较次数有严格的顺序性，因此，冒泡排序适合于文件内存储数据的顺序排序。

但是，二路归并排序在文件内存储数据的逆序排序中，也有其应用价值，因此，二路归并排序在文件内部存储数据的混合排序中，也有其应用价值。

归并排序大概讲解
归并排序是一种高效的排序算法，它的基本思路是将待排序的序列分为若干个子序列，每个子序列都是有序的，然后再将这些子序列合并成一个有序的序列。

归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)，是一种稳定的排序算法。

归并排序的主要步骤如下：
1. 将待排序的序列不断地分为两个子序列，直到每个子序列只有一个元素为止。

2. 将两个子序列合并成一个有序的序列，这个过程称为归并。

3. 不断地重复步骤2，直到所有的子序列合并成一个完整的有序序列。

归并排序可以使用递归或迭代的方法实现。

递归实现的归并排序思路较为简单，但是由于递归调用的开销较大，实际应用较少。

迭代实现的归并排序需要借助一个辅助数组，可以在空间上进行优化。

归并排序具有以下优点：
1. 稳定性好，相同元素的相对位置不会改变。

2. 时间复杂度较低，最坏时间复杂度为O(nlogn)，平均时间复杂度为O(nlogn)。

3. 可以排序大规模数据，适用于外部排序。

需要注意的是，归并排序的缺点是需要额外的空间来存储待排序的序列，空间复杂度较高。

此外，归并排序的常数因子较大，在小规模数据的排序中表现不如插入排序等简单排序算法。

数据结构归并排序
归并排序
归并排序是一种常见的排序算法，它基于分治的思想，将一个大问题分解成若干个子问题，然后将子问题的解进行合并，得到最终的排序结果。

本文将详细介绍归并排序的算法原理、步骤以及时间复杂度分析。

⒈算法原理
归并排序的基本思想是将待排序的序列分成两个相等长度的子序列，然后分别对两个子序列进行排序，最后将两个已排序的子序列合并成一个有序的序列。

具体步骤如下：
●将待排序序列分为两个相等的子序列，不断递归地将子序列继续分解，直到无法再分解（即子序列只有一个元素）
●对每个子序列进行排序，可以使用归并排序递归地对子序列进行排序。

●将两个已排序的子序列合并成一个有序的序列，合并过程可以使用额外的空间存储。

⒉算法步骤
归并排序的步骤如下：
●将待排序的序列分成两个相等长度的子序列。

●对子序列递归地应用归并排序，直到子序列只有一个元素。

●将两个已排序的子序列通过比较大小，按照顺序合并成一个
有序的序列。

●重复以上步骤，直到合并完成，得到最终的有序序列。

⒊时间复杂度分析
归并排序的时间复杂度为O(nlogn)，其中n为待排序序列的长度。

分析归并排序的时间复杂度可以通过递归树来实现，每层递归
都需要处理整个序列。

假设序列的长度为n，递归树的高度为logn，每层的时间复杂度为O(n)，所以总的时间复杂度为O(nlogn）附件：
本文档未涉及附件。

法律名词及注释：
本文档未涉及法律名词及注释。

c语言有序单链表的二路归并算法C语言有序单链表的二路归并算法一、引言有序单链表是一种常见的数据结构，其中的元素按照一定的顺序排列。

当需要将两个有序单链表合并为一个有序单链表时，可以使用二路归并算法。

本文将介绍使用C语言实现有序单链表的二路归并算法的原理和步骤。

二、算法原理二路归并算法是一种常见的排序算法，它通过将两个有序链表合并为一个有序链表的方式来实现排序。

算法的基本思想是通过比较两个链表中的元素大小，将较小的元素添加到新的链表中，直到将两个链表全部合并为止。

三、算法步骤下面是使用C语言实现有序单链表的二路归并算法的详细步骤：1. 定义两个指针，分别指向两个有序单链表的头结点；2. 创建一个新的链表，用于存储合并后的有序链表；3. 循环比较两个链表中的元素大小，将较小的元素添加到新链表中，并将指针后移；4. 当其中一个链表遍历完毕时，将另一个链表中剩余的元素添加到新链表的末尾；5. 返回新链表的头结点，即为合并后的有序单链表。

四、代码实现下面是使用C语言实现有序单链表的二路归并算法的示例代码：```c#include <stdio.h>#include <stdlib.h>// 定义链表结点typedef struct Node {int data;struct Node* next;} Node;// 创建有序链表Node* createList(int arr[], int size) {Node* head = NULL;Node* tail = NULL;for (int i = 0; i < size; i++) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = arr[i];newNode->next = NULL;if (head == NULL) {head = newNode;tail = newNode;} else {tail->next = newNode;tail = newNode;}}return head;}// 合并两个有序链表Node* mergeList(Node* list1, Node* list2) { if (list1 == NULL) {return list2;}if (list2 == NULL) {return list1;}Node* head = NULL;Node* tail = NULL;while (list1 != NULL && list2 != NULL) { if (list1->data <= list2->data) {if (head == NULL) {head = list1;tail = list1;} else {tail->next = list1;tail = list1;}list1 = list1->next;} else {if (head == NULL) {head = list2;tail = list2;} else {tail->next = list2;tail = list2;}list2 = list2->next;}}if (list1 != NULL) {tail->next = list1;}if (list2 != NULL) {tail->next = list2;}return head;}// 打印链表void printList(Node* head) { Node* p = head;while (p != NULL) {printf("%d ", p->data); p = p->next;}printf("\n");}int main() {int arr1[] = {1, 3, 5};int arr2[] = {2, 4, 6};Node* list1 = createList(arr1, sizeof(arr1) / sizeof(int));Node* list2 = createList(arr2, sizeof(arr2) / sizeof(int));printf("链表1：");printList(list1);printf("链表2：");printList(list2);Node* mergedList = mergeList(list1, list2);printf("合并后的链表：");printList(mergedList);return 0;}```五、算法分析有序单链表的二路归并算法的时间复杂度为O(n)，其中n为两个链表的总长度。

归并排序归并排序(merge sort)归并的含义是将两个或两个以上的有序表合并成一个新的有序表。

归并排序有多路归并排序、两路归并排序 , 可用于内排序，也可以用于外排序。

这里仅对内排序的两路归并方法进行讨论。

两路归并排序算法思路①把 n 个记录看成 n 个长度为 l 的有序子表；②进行两两归并使记录关键字有序，得到 n/2 个长度为 2 的有序子表；③重复第②步直到所有记录归并成一个长度为 n 的有序表为止。

【实现代码】#include<stdio.h>#include<stdlib.h>void merget(int a[],int start,int mid,int end){int t=end-start+1;int i=start,j=mid+1;int k=0;int *p=(int *)malloc(sizeof(int)*t);while(i<=mid&&j<=end){if(a[i]<=a[j]){p[k++]=a[i++];}else{p[k++]=a[j++];}}if(i>mid){while(j<=end){p[k++]=a[j++];}}else{while(i<=mid){p[k++]=a[i++];}}for(i=start,k=0;i<=end;i++,k++){a[i]=p[k];}free(p);}void mergetsort(int a[],int start,int end) {int mid;if(start<end){mid=(end+start)/2;mergetsort(a,start,mid);mergetsort(a,mid+1,end);merget(a,start,mid,end);}}void main(){int a[10];int i;for(i=0;i<10;i++)scanf("%d",&a[i]);mergetsort(a,0,9);for(i=0;i<10;i++)printf("%d\n",a[i]);}。

⼆路归并排序算法将两个按值有序序列合并成⼀个按值有序序列，则称之为⼆路归并排序，下⾯有⾃底向上和⾃顶向下的两种排序算法，⾃顶向下的排序在本⽂末讲述，使⽤递归实现，代码较简洁，经供参考。

1. 归并⼦算法：把位置相邻的两个按值有序序列合并成⼀个按值有序序列。

例如把序列 X[s..u] = {3, 12, 23, 32}和序列 X[u+1..v] = {2, 5, 8, 99} 合并成序列Z[s..v] = {2, 3, 5, 8, 12, 23, 32, 99}, 注意合并前的元素都位于同⼀个有序序列的相邻位置，合并后的有序序列的下标与合并前的序列总的起始下标相同。

算法过程中需要三个整型变量，i ⽤来遍历归并的前⼀个有序序列，其初始位置是s；j ⽤来遍历归并的后⼀个有序序列，其初始值是u+1；q ⽤来指出归并后得到的有序序列的末尾元素的位置，其初始值是s。

当遍历完成其中的⼀个有序序列之后，只需把另⼀个未结束有序序列的剩余元素复制到合并后的有序序列的末尾。

看代码：[cpp]1. //将有序的X[s..u]和X[u+1..v]归并为有序的Z[s..v]2. void merge(int X[], int Z[], int s, int u, int v)3. {4. int i, j, q;5. i = s;6. j = u + 1;7. q = s;8.9. while( i <= u && j<= v )10. {11. if( X[i] <= X[j] )12. Z[q++] = X[i++];13. else14. Z[q++] = X[j++];15. }16.17. while( i <= u ) //将X中剩余元素X[i..u]复制到Z18. Z[q++] = X[i++];19. while( j <= v ) //将X中剩余元素X[j..v]复制到Z20. Z[q++] = X[j++];21. }2. ⼀趟归并扫描⼦算法：将参加排序的序列分成若⼲个长度为 t 的，且各⾃按值有序的⼦序列，然后多次调⽤归并⼦算法merge将所有两两相邻成对的⼦序列合并成若⼲个长度为2t 的，且各⾃按值有序的⼦序列。

归并排序的详细过程归并排序是一种常见的排序算法，它通过将待排序序列分成若干个子序列，分别对每个子序列进行排序，然后再将排好序的子序列合并成最终的有序序列。

下面将详细介绍归并排序的过程。

1. 分解阶段：将待排序的序列不断二分，直到每个子序列只剩下一个元素为止。

这个过程可以使用递归来实现。

例如，对于序列[8, 4, 2, 5, 1, 3, 6, 7]，先将其二分为[8, 4, 2, 5]和[1, 3, 6, 7]两个子序列，再将这两个子序列继续二分，直到每个子序列只剩下一个元素。

2. 合并阶段：将相邻的两个子序列合并成一个有序序列。

具体的合并过程如下：- 创建一个临时数组来存放合并后的序列。

- 初始化两个指针，分别指向两个子序列的起始位置。

- 依次比较两个子序列中的元素，将较小的元素放入临时数组中，并将指向该元素的指针后移一位。

- 当其中一个子序列的指针移到末尾时，将另一个子序列中剩余的元素依次放入临时数组中。

- 将临时数组中的元素复制回原始序列的对应位置。

以序列[8, 4, 2, 5, 1, 3, 6, 7]为例，将其分解为[8, 4, 2, 5]和[1, 3, 6, 7]两个子序列，然后对这两个子序列进行合并。

首先比较两个子序列的第一个元素，4小于8，将4放入临时数组中，并将指向4的指针后移一位。

接着比较2和8，2小于8，将2放入临时数组中，并将指向2的指针后移一位。

继续比较5和8，5小于8，将5放入临时数组中，并将指向5的指针后移一位。

此时第一个子序列中的元素已经全部放入临时数组中。

接下来比较两个子序列的第一个元素，3小于1，将3放入临时数组中，并将指向3的指针后移一位。

继续比较6和1，6大于1，将1放入临时数组中，并将指向1的指针后移一位。

接着比较6和3，6大于3，将3放入临时数组中，并将指向3的指针后移一位。

最后比较6和7，7小于6，将7放入临时数组中，并将指向7的指针后移一位。

此时第二个子序列中的元素已经全部放入临时数组中。

归并排序算法图⽂详解（模版使⽤）算法介绍引⽤百度百科的介绍。

归并排序（Merge Sort）是建⽴在操作上的⼀种有效，稳定的排序算法，该算法是采⽤（Divide and Conquer）的⼀个⾮常典型的应⽤。

将已有序的⼦合并，得到完全有序的序列；即先使每个⼦序列有序，再使⼦序列段间有序。

若将两个有序表合并成⼀个有序表，称为⼆路归并。

算法描述归并排序，采⽤是分治法，先将数组分成⼦序列，让⼦序列有序，再将⼦序列间有序，合并成有序数组。

算法描述：（1）把长度为n的输⼊序列分成长度 n/2的⼦序列；（2）对两个⼦序列采⽤归并排序；（3）合并所有⼦序列。

算法实现void mergeSortInOrder(int[] arr,int bgn,int mid, int end){int l = bgn, m = mid +1, e = end;//相当于对⼀个数组的前半部分和后半部分进⾏排序排序，从开始的只有两个数，到后⾯//因为基本有序，所以只需要进⾏合并就⾏int[] arrs = new int[end - bgn + 1];int k = 0;//进⾏有序合并while(l <= mid && m <= e){if(arr[l] < arr[m]){arrs[k++] = arr[l++];}else{arrs[k++] = arr[m++];}}//如果前半部分⼤的⽐较多，直接接在后⾯while(l <= mid){arrs[k++] = arr[l++];}//如果后半部分⼤的⽐较多，直接接在后⾯while(m <= e){arrs[k++] = arr[m++];}//对我们原来的数组进⾏值的覆盖for(int i = 0; i < arrs.length; i++){arr[i + bgn] = arrs[i];}}void mergeSort(int[] arr, int bgn, int end){//如果开始指针⼤于结束指针，结束if(bgn >= end){return;}//通过分治将我们的数组分成多个⼩数组int mid = (bgn + end) >> 1;mergeSort(arr,bgn,mid);mergeSort(arr,mid + 1, end);//对我们的⼩数组进⾏排序mergeSortInOrder(arr,bgn,mid,end);}算法分析稳定排序外排序（需要消耗额外的内存）时间复杂度O(nlogn)，空间复杂度为O(1)。

二路归并排序算法思想
二路归并排序，又称为二路归并算法，是一种高效的排序算法。

它采用二分法的思想，将一组未排序的数据集合分为两个子集，先分别对每个子集进行排序，再将排序后的子集合归并在一起，得到一个完全有序的数据集合。

二路归并排序是一种“分而治之”的思想，三个步骤组成：分解、排序和合并。

首先，将数据集分解为两个规模较小的子数据集，然后分别对子集进行排序，最后将排序后的子集合归并在一起，得到一个完全有序的数据集合。

二路归并排序的时间复杂度和空间复杂度都比较低，其时间复杂度为O(nlogn)，其空间复杂度为O(n)。

二路归并排序的优点在于：可以对非常大的数据集进行排序，非常稳定（相同的元素排序后仍然保持相同的排序），并且有效的利用计算机的内存空间。

总体来说，二路归并排序是一种低开销、高效率的排序算法，不但能够处理大数据集而且能保证排序的稳定性，使用场合很多。

【算法】归并排序算法的讲解和代码实践归并排序算法是一种基于分治思想的排序算法，它的核心思想是将待排序的数据分成两个子序列，分别进行排序，再将两个已排序的子序列合并成一个有序的序列。

归并排序算法的优点是其稳定性、时间复杂度为O(nlogn)和空间复杂度为O(n)。

下面将详细讲解和代码实践归并排序算法。

一、算法思路归并排序算法的思路可以分为三个步骤：分解、排序和合并。

1.分解：将待排序的序列分成左右两个子序列，直到子序列只有1个元素。

2.排序：对左右两个子序列分别进行归并排序。

3.合并：将两个已排序的子序列合并成一个有序的序列。

二、算法实现下面是基于递归实现的归并排序算法的代码：```void mergeSort(int arr[], int l, int r){if(l < r){int mid = (l + r) / 2;mergeSort(arr, l, mid);mergeSort(arr, mid + 1, r);merge(arr, l, mid, r);}}void merge(int arr[], int l, int mid, int r){int i = l, j = mid + 1, k = 0;int temp[r - l + 1];while(i <= mid && j <= r){if(arr[i] < arr[j]){temp[k++] = arr[i++];}else{temp[k++] = arr[j++];}}while(i <= mid){temp[k++] = arr[i++];}while(j <= r){temp[k++] = arr[j++];}for(int p = 0; p < k; p++){arr[l + p] = temp[p];}}```三、代码说明1.mergeSort函数：该函数接受一个待排序的数组和左右边界值，如果左边界值小于右边界值，则进入分治过程，分别递归调用mergeSort函数对左右两个子序列进行归并排序，然后合并两个已排序的子序列。

归并排序——思路及其实现归并排序（MERGE-SORT）是利⽤归并的思想实现的排序⽅法，该算法采⽤经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成⼀些⼩的问题然后递归求解，⽽治(conquer)的阶段则将分的阶段得到的各答案"修补"在⼀起，即分⽽治之)。

归并排序中，我们会先找到⼀个数组的中间下标mid，然后以这个mid为中⼼，对两边分别进⾏排序，之后我们再根据两边已排好序的⼦数组，重新进⾏值⼤⼩分配。

我们就以下⾯的数组为例：（1）mid等于数组最⼤下标 / 2 = 3，于是我们以下标3（值为7）为中⼼，分别排序0~3和4~7的数字。

（2）此时两边的数组还可以创建分⽀：（3）可以看到上⾯还有四个⼩数组，我们继续创建分⽀：（4）可以看到，此时我们已经⽆法继续创建分⽀了，因为数组数量为1时是没有必要进⾏排序的，这时我们可以开始进⾏对每⼀个⼩的数组进⾏排序并且合并：（5）继续，拿到上⼀步组成的⼩数组，再组合成新的排序数组：（6）最后，我们想要的结果就来了：代码如下：public class MergeSort {public static void mergeSort(int[] arr) {if (arr == null || arr.length < 2) {return;}mergeSort(arr, 0, arr.length - 1);}public static void mergeSort(int[] arr, int l, int r) {if (l == r) {return;}int mid = l + ((r - l) >> 1);mergeSort(arr, l, mid);mergeSort(arr, mid + 1, r);merge(arr, l, mid, r);}public static void merge(int[] arr, int l, int m, int r) { int[] help = new int[r - l + 1];int i = 0;int l1 = l;int r1 = m + 1;while (l1 <= m && r1 <= r) {help[i++] = arr[l1] < arr[r1] ? arr[l1++] : arr[r1++]; }while (l1 <= m) {help[i++] = arr[l1++];}while (r1 <= r) {help[i++] = arr[r1++];}for (int j = 0; j < help.length; j++) {arr[l + j] = help[j];}}}。

归并排序算法思想归并排序这次我们来讲述归并排序的基本思想。

归并排序，⾸先把⼀个数组中的元素，按照某⼀⽅法，先拆分了之后，按照⼀定的顺序各⾃排列，然后再归并到⼀起，使得归并后依然是有⼀定顺序的。

归并排序算法可以利⽤递归的思想或者迭代的思想去实现。

⾸先我们先把⼀个⽆序的数组去拆分，然后利⽤⼀定的规则，去合并。

类似于⼆叉树的结构。

其总的时间复杂度为O( n log n)。

空间复杂度为 S（n）因为最⼤的空间使⽤量为该排序数组的最⼤个数。

⽰例图如下:⾸先我们看到，⼀个⽆序的数组如下，为了简约，以及简便解释，我们定义了8个元素。

然后，我们把该8个元素进⾏划分，分成左边四个，和右边四个，如下图。

依次按照上边的⽅法，把剩余的数组继续拆分，⼀直拆到只剩下⼀个元素的时候，停⽌。

如下图由于存在8个单独的⼦元素，然后我们两两把元素合并，并且按照⼀定顺序排序(此处⽤从⼩到⼤的顺序排序)。

如下图:此时，我们可以看到我们⼜得到了四个不同颜⾊的数组，并且在这个数组⾥边，也是按照⼀定的顺序排好序的。

随后，继续利⽤这种⽅法，把剩余的继续合并，⼀直合并到所有数都在⼀个数组⾥边。

此时便是完成了合并。

如下图演⽰：整个过程(包括拆分和合并)如下：代码如下：#include<iostream>#include<cstdlib>#include<vector>using namespace std;void Split(vector<int>& pos, vector<int>& temp, const int start, const int end);void Merge(vector<int>& pos, vector<int>& temp, const int left, const int mid, const int right); void MergeSort(vector<int>& pos, const int start, const int end);void Display1(vector<int>& pos);void Display2(vector<int>& pos);int main(){int n;cout << "请输⼊排序的数的个数" << endl;cin >> n;vector<int>pos(n, 0);//申请n个数cout << "请输⼊需要排序的数" << endl;for (int i = 0; i < n; i++)cin >> pos[i];//初始化数据Display1(pos);//显⽰排序前的数组MergeSort(pos, 0, pos.size() - 1);//从第⼏个数开始，0个到最后⼀个数进⾏归并排序Display2(pos);//显⽰排序后的数组pos.clear();return 0;}//拆分void Split(vector<int>& pos, vector<int>& temp, const int start, const int end){if (start < end)//条件，不能分割为⽌{int mid;//中间数定位mid = (start + end) / 2;Split(pos, temp, start, mid);//左边拆分Split(pos, temp, mid + 1, end);//右边拆分Merge(pos, temp, start, mid, end);//归并}}//合并void Merge(vector<int>& pos, vector<int>& temp, const int left, const int mid, const int right) {int i, j, k;i = left;j = mid + 1;k = 0;/*i 表⽰第⼀个数组，从左到中间的数j 表⽰第⼆个数组，从中间到右边的数k 表⽰临时数组中的下表*/while (i <= mid && j <= right)//两个数组判⽐{if (pos[i] <= pos[j])//如果左边的⼤于右边的{temp[k] = pos[i];//左边的放进临时数组中k++; i++;//继续跟下⼀个⽐较}else{temp[k] = pos[j];//如果右边的⼤于左边k++; j++;//同样放⼊临时数组中，继续跟下⼀个⽐较}}//当⼀⽅数组中有剩余的时候，把他放进临时数组中，然后等待归并 while (i <= mid){temp[k] = pos[i];k++; i++;}while (j <= right){temp[k] = pos[j];k++; j++;}//把临时数组中的内容复制到实际数组中for (int i = 0; i < k; i++)pos[left + i] = temp[i];}//排序算法void MergeSort(vector<int>& pos, const int start, const int end){vector<int>temp(pos.size(), 0);//创建临时数组Split(pos, temp, start, end);temp.clear();}void Display1(vector<int>& pos){cout << "排序前的数组如下" << endl;for (int i = 0; i < pos.size(); i++){cout << pos[i] << " ";}cout << endl;}void Display2(vector<int>& pos){cout << "排序后的数组如下" << endl;for (int i = 0; i < pos.size(); i++){cout << pos[i] << " ";}cout << endl;}程序执⾏结果图有什么问题或者错误可以评论留⾔，欢迎指正。

前言1.1排序的重要性生活中，无时不刻不充满这排序，比如：班级同学的成绩排名问题，公司产值高低的问题等等，解决这些问题的过程中，都涉及到了一个数据结构的构造思想过程。

数据结构中的排序，也有很多种，如：插入排序、交换排序、选择排序等等，此时我们就要注意选择具有优解的算法，将一个数据元素（或记录）的任意序列，重新排列成一个有序的排列，便于我们查找。

假设含有n个记录的序列为{R1,R2,Rn},其相应的关键字序列为{K1,K2,…,Kn}需确定1，2…n的一种排序P1,P2…Pn,使其相应的关键字满足如下的非递减的关系：Kp1≤Kp2≤…≤Kpn,即按关键字{Rp1,Rp2,…,Rpn}有序的排列，这样的一种操作称为排序。

一般情况下，排序又分为内部排序和外部排序。

而在内部排序中又含有很多排序方法，就其全面性能而言，很难提出一种被认为是最好的方法，因为每一种方法都有它的优缺点，适合在不同的环境下使用。

我们学习的排序有:直接插入排序、折半插入排序、希尔排序、快速排序、基数排序、归并排序等。

本次课题研究中，我主要进行了二路归并排序的研究和学习。

1.2设计的背景和意义排序是计算机领域的一类非常重要的问题，计算机在出来数据的过程中，有25%的时间花在了排序上，有许多的计算机设备，排序用去计算机处理数据时间的一半以上，这对于提高计算机的运行速度有一定的影响。

此时排序算法的高效率显得尤为重要。

在排序算法汇中，归并排序（Merging sort）是与插入排序、交换排序、选择排序不同的另一类排序方法。

归并的含义是将两个或两个以上的有序表组合成一个新的有序表。

归并排序可分为多路归并排序，两路归并排序，既可用于内排序，也可以用于外排序。

这里仅对内排序的两路归并排序进行讨论。

而我们这里所探究学习的二路归并排序，设计思路更加清晰、明了，程序本身也不像堆结构那样复杂，同时时间复杂度仅为0(N)，同时在处理大规模归并排序的时候，排序速度也明显优于冒泡法等一些排序算法，提高排序算法的效率。