1.归北排序算法简介
归并排序主要用到了分治策略.所谓分治就是把复杂的问题分解成规模较小而结构与原问题类似的子问题.子问题都是简单问题,就很容易解决了.最后合并子问题的解进行得到复杂问题的解.
假如有n个待排序的元素.归并排序的算法是这样的:
1.把n个元素分成各含n/2个元素的两个序列
2.再对两个序列递归排序.(递归到子序列只有两个元素的时候自然容易排序了)
3.合并两个排序好的子序列得到排序结果.(合并排序好的子序列的算法是这样的.比如有排序好的序列A(a1,a2,a3)和B(b1,b2).有个临时数组array.首比较A中第一元素和B中第一个元素.哪个小就放入array中.哪个序列中元素放入了就把数组下标加1.接着对比两个序列最前面的两个元素.哪个序列的元素全部放入array了就停止比较.把另一个序列中的元素全部添加到array中.
举个简单的例子:假如有这样一个待排序的序列:5,3,4,1
第一步:把该序列分成两个子序列5,3,和4,1
第二步:对子序列排序得到3,5和1,4
第三步合并3,5,和1,4得到1,3,4,5.
2.用C#实现归并排序算法:
一.建一个类.实现排序功能//注意:下面函数中会看到array,first,last这三个参数在一起.它表示对数组中下标从first到last这一段的数据进行排序操作.下标是其他的不管
class MergeSortClass
{
public void MergeSort(int[] array) //假设array为待排序的一个数组.作为参数传入
{
SubMergeSort(array, 0, array.Length -1);
}
//递归调用就是不停的调用这个函数.first和last指子序列的第一个位置和最后一个位置
private void SubMergeSort(int[] array,int first,
int last)
{
int mid; //序列中间位置.
if(first < last ) //这个判断是递归调用的中止条件.当只有两个元素时再分下去就会出现first=last.这时停止递归
{
mid = (first + last )/2;
SubMergeSort(array,first,mid ); //序列拆分后的前一半.再递归调用
SubMergeSort (array,mid + 1,last ); //序列拆分后的后一半.再递归调用
FinalMergeSort(array,first ,mid ,last ); //合并前面排好序的两个子序列
}
}
//此时array中下标first至last这一段以mid为分界点.前面一半已排好序.后面一半也已排好序.接下来要做的是让整个一段排好序
private void FinalMergeSort(int[] array, int first, int mid, int last)
{
int[] temp = new int[(last - first + 1)]; //新建 一个临时数组.
int j = 0; //作为得时数组的下标
int begin1 = first, end1 = mid; //排好序的前面部分的起始结束位置.设前部分为A
int begin2 = mid + 1, end2 = last; //排好序的后面部分的起始结束位置.设后部分为B
while (begin1 <= end1 && begin2 <= end2) //当两个子序列的值都还没完全放入临时数组中时循环
{
if (array[begin1] < array[begin2]) //A第一个元素小
{
temp[j++] = array[begin1]; //小元素放入临时数组中.临时数组下标向后移一位
begin1++; //A下标向后移一位
}
else //B第一个元素小
{
temp[j++] = array[begin2];
begin2++;
}
}
while (begin1 <= end1) //B已被全部放入临时数组.剩下的A不用比了.全部放入临时数组
{
temp[j++] = array[begin1++];
}
while (begin2 <= end2) //A已被全部放入临时数组.剩下的B就不用比了.全部放入临时数组
{
temp[j++] = array[begin2++];
}
for (int i = 0; i < (last - first + 1); i++) //把临时数组元素复制到原数组中
{
array[first + i] = temp[i];
}
}
}
二.建一个测试程序.调用排序类
class Program
{
static void Main(string[] args)
{
int[] array = { 1, 9, 8, 5, 7, 6, 2, 4, 3,785,235,897,111 };
MergeSortClass ms = new MergeSortClass();
ms.MergeSort(array);
foreach (int i in array)
{
Console.WriteLine(i);
}
}
}
分享到:
相关推荐
基于python的排序算法-归并排序Merge Sort
归并排序(Merge sort)(台灣譯作:合併排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段...
排序——归并排序(Merge sort)
归并排序(Merge Sort)源码及运行示例
void merge_sort(int A[],int p,int r) { int q; if(p) { q=(p+r)/2;//计算q的值,即将问题拆分成两个子问题; merge_sort(A,p,q); //左半边递归调用merge_sort,缩小问题规模 printf("\n"); //print_A(A...
经典排序算法 - 归并排序Merge sort 经典排序算法 - 冒泡排序Bubble sort 经典排序算法 - 选择排序Selection sort 经典排序算法 - 鸡尾酒排序Cocktail sort 经典排序算法 - 希尔排序Shell sort 经典排序算法 - ...
C#,单向链表(Simply Linked List)的归并排序(Merge Sort)算法与源代码 归并排序法(3Merge Sort,以下简称MS)是分治法思想运用的一个典范。 其主要算法操作可以分为以下步骤: Step 1:将n个元素分成两个含n/...
在B站讲归并排序的笔记,需要的同学可以免费下载
C#,双向链表(Doubly Linked List)归并排序(Merge Sort)算法与源代码 1 双向链表 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一...
归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"...
归并算法的简单举例
归并排序的matlab实现,且该程序实现了多维数据的高效排序,并不是单纯的一维数组排序!
归并排序(Merge sort,台湾译作:合并排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
归并排序是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。...
珠排序(Bead Sort) 二进制插入排序(Binary Insertion Sort)...迭代归并排序(Iterative Merge Sort) 归并插入排序(Merge Insertion Sort) 归并排序(Merge Sort) 最高有效数字优先的基数排序(Msd Radix Sort)
归并排序(Merge Sort)是一种采用分治法(Divide and Conquer)策略的排序算法。该算法首先将已有序的子序列合并,得到完全有序的序列。在归并排序中,合并操作是将两个有序表合并成一个有序表的过程。 归并排序的...
主要给大家介绍了关于python基本算法之实现归并排序(Merge sort)的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧