转自:http://blog.csdn.net/morewindows/article/details/6678165
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
首先考虑下如何将将二个有序数列合并。这个非常简单,只要从比较二个数列的第一个数,谁小就先取谁,取了后就在对应数列中删除这个数。然后再进行比较,如果有数列为空,那直接将另一个数列的数据依次取出即可。
//将有序数组a[]和b[]合并到c[]中 void MemeryArray(int a[], int n, int b[], int m, int c[]) { int i, j, k; i = j = k = 0; while (i < n && j < m) { if (a[i] < b[j]) c[k++] = a[i++]; else c[k++] = b[j++]; } while (i < n) c[k++] = a[i++]; while (j < m) c[k++] = b[j++]; }
可以看出合并有序数列的效率是比较高的,可以达到O(n)。
解决了上面的合并有序数列问题,再来看归并排序,其的基本思路就是将数组分成二组A,B,如果这二组组内的数据都是有序的,那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了?
可以将A,B组各自再分成二组。依次类推,当分出来的小组只有一个数据时,可以认为这个小组组内已经达到了有序,然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列,再合并数列就完成了归并排序。
static void Main(string[] args) { int[] array = { 49, 38, 65, 97, 76, 13, 27, 0, 34 }; int[] temp = new int[array.Length]; mergesort(array, 0, array.Length - 1,temp); foreach (int num in array) { Console.Write(num + " ,"); } Console.WriteLine(); } public static void mergearray(int[] a, int first, int mid, int last, int[] temp) { int leftHalf = first, rightHalf = mid + 1;//设置左半边和右半边的起始指针 int k = 0;//这个指针是用来设置temp数组中的元素位置 while (leftHalf <= mid && rightHalf <= last) { if (a[leftHalf] <= a[rightHalf])//不断从原数组的左右半边开始的元素相互比较 temp[k++] = a[leftHalf++];//小的就放到temp中,经过while语句之后,肯定 else temp[k++] = a[rightHalf++];//会出现某半边的元素全部被填充到temp中,另半边还有剩余 } while (leftHalf <= mid)//如果左半边有剩余,就全部按序填入temp temp[k++] = a[leftHalf++]; while (rightHalf <= last)//如果右半边有剩余,就全部按序填入temp temp[k++] = a[rightHalf++]; for (leftHalf = 0; leftHalf < k; leftHalf++)//这时temp数组中的全部元素已经排序好了, a[first + leftHalf] = temp[leftHalf];//只要按序填入原来的数组就行了 } public static void mergesort(int[] a, int first, int last, int[] temp) { if (first < last)//终止递归的条件 { int mid = (first + last) / 2; mergesort(a, first, mid, temp); //左边有序 mergesort(a, mid + 1, last, temp); //右边有序 mergearray(a, first, mid, last, temp); //再将二个有序数列合并 } }
归并排序的效率是比较高的,设数列长为N,将数列分开成小数列一共要logN步,每步都是一个合并有序数列的过程,时间复杂度可以记为O(N),故一共为O(N*logN)。因为归并排序每次都是在相邻的数据中进行操作,所以归并排序在O(N*logN)的几种排序方法(快速排序,归并排序,希尔排序,堆排序)也是效率比较高的。
归并排序的效率略低于快排,但是归并排序是稳定的,这是相对于快排的一个优势。
相关推荐
在第一版的基础上新加了对冒泡排序,直接插入排序,直接选择排序,希尔排序,归并排序,快速排序和堆排序这七种常用的排序方法的总结篇,方便大家复习,合适作为笔试面试前的复习资料。
对冒泡排序,直接插入排序,直接选择排序,希尔排序,归并排序,快速排序和堆排序这七种常用的排序方法进行了详细的讲解
这是本人在研一上课时所整理的文档,包括冒泡排序,直接插入排序,直接选择排序,希尔排序,归并排序,快速排序和堆排序这七种常用的排序方法,这些文章不仅使我在考试中取了不错的成绩,也为后来顺利面过迅雷,腾讯...
在第一版的基础上新加了对冒泡排序,直接插入排序,直接选择排序,希尔排序,归并排序,快速排序和堆排序这七种常用的排序方法的总结篇,方便大家复习,合适作为笔试面试前的复习资料。
包括冒泡排序,直接 插入排序,直接选择排序,希尔排序,归并排序,快速排序和堆 排序这七种常用的排序方法,
直接选择排序 希尔排序 归并排序 快速排序 堆排序等经典算法之七大排序白话讲解第二版
冒泡排序,直接插入排序,直接选择排序,希尔排序,归并排序,快速排序和堆排序这七种常用的排序方法的总结,方便大家复习,合适作为笔试面试前的复习资料
* 实现归并排序、快速排序、插入排序、冒泡排序、选择排序* 编程实现O(n)时间复杂度内找到一组数据的第K大元素 ## 二分查找 * 实现一个有序数组的二分查找算法* 实现模糊二分查找算法(比如大于等于给定值的第一个...
参考csdn博客专栏《白话经典算法》用python实现数据结构种常见的7种排序
MoreWindows白话经典算法之七大排序 这是本人在研一上课时所整理的文档,包括冒泡排序,直接插入排序,直接选择排序,希尔排序,归并排序,快速排序和堆排序
问题:实现归并排序、快速排序、插入排序、冒泡排序、选择排序 问题:编程实现O(n)时间复杂度内找到一组数据的第K大元素 二分查找、散列表、字符串处理、二叉树、堆、图、回溯、分治、动态回归等。 资源中包括常用...