算法回顾系列第七篇:归并排序
------------------------------------
归并排序
基本原理:
利用递归和分而治之的技术将数据序列划分成为越来越小的半子表,再对半子表排序,最后通过递归步骤将排好序的半子表合并成为越来越大的有序序列。
归并排序包括两个步骤,分别为:1、划分子表。2、合并半子表。
该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
程序实现:
public void sort(int[] data){
int[] temp = new int[data.length];
mergeSort(data,temp,0,data.length-1);
}
/**
* @param 待排序数组
* @param 辅助排序数组
* @param 起始位置
* @param 结束位置
*/
private void mergeSort(int[] data,int[] temp,int l,int r){
int mid=(l+r)/2;
if(l==r) return ;
//分治:递归划分左半个子表
mergeSort(data,temp,l,mid);
//分治:递归划分右半个子表
mergeSort(data,temp,mid+1,r);
System.out.println("begin merge ...");
/**
* 合并子表:
* 左半个子表和右半个子表标记(mid为中间位置)两个指针各指向头元素,
* 选择相对小的元素放入到合并空间,并移动指针到下一位置。
* 重复步骤上面步骤直到左(或右)某一指针达到序列尾,
* 将右(或左)剩下的所有元素直接复制到合并序列尾。
*/
System.out.println("data:"+Arrays.toString(data)+" temp:"+Arrays.toString(temp));
System.out.println("l:"+l+" r:"+r+" mid:"+mid);
//复制data中l到r内区域的数到temp的对应位置.
for(int i=l;i<=r;i++){
temp[i]=data[i];
}
System.out.println("copy data:"+Arrays.toString(data)+" copy temp:"+Arrays.toString(temp));
//声明2个指针:i1左子表头,i2右子表头,指针作用于temp,合并后的值写入data.
int i1=l;//指针:mid左边元素坐标位置(起始为l).
int i2=mid+1;//指针:mid右边元素坐标位置(起始为mid右边第一个元素).
//遍历l到r区域之间的数据(从l的最左边元素向右遍历直到r).
for(int cur=l;cur<=r;cur++){
if(i1==mid+1){//如果i1已经遍历到mid以右(mid为边界).
System.out.println("i1==mid+1");
data[cur]=temp[i2];//将tmp的mid以右坐标位置的元素写入data当前位置.
i2++;//mid右子表指针移动(mid右边元素坐标+1)
}else if(i2>r){//如果mid以右元素已经遍历超过r(r为边界).
System.out.println("i2>r");
data[cur]=temp[i1];//将tmp的mid以左坐标位置的元素写入data当前位置.
i1++;//mid左子表指针移动(mid左边元素坐标+1)
}else if(temp[i1]<temp[i2]){//如果tmp的mid以左坐标位置元素值小于tmp的mid以右的坐标位置元素值.
System.out.println("temp[i1]<temp[i2]");
data[cur]=temp[i1];//将较小的元素值写入data当前位置.
i1++;//mid左子表指针移动(mid左边元素坐标+1)
}else{//mid以左大于mid以右.
System.out.println("else");
data[cur]=temp[i2];//将tmp的mid以右坐标位置的元素值写入data当前位置.
i2++;//mid右子表指针移动(mid右边元素坐标+1)
}
System.out.println("swap data:"+Arrays.toString(data)+" swap temp:"+Arrays.toString(temp));
}
//System.out.println("last data:"+Arrays.toString(data)+" last temp:"+Arrays.toString(temp));
//System.out.println("l:"+l+" r:"+r);
}
public static void main(String[] args){
//int[] arrays = new int[]{10,2,4,8,5,1,6,3,7,9};
int[] arrays = new int[]{10,9,8,7,6,5,4,3,2,1};
new MergeSort().sort(arrays);
System.out.println(Arrays.toString(arrays));
}
上面程序中:
1、首先通过递归将待排序数组data划分为若干个子序列,
2、合并某个data子序列时将该子序列内元素的复制到temp对应位置。
每个子序列有l,r,mid三个位置,分别对应它的:起始位置、结束位置、中间位置。
从l到mid(包含)为左子表,从mid+1到r(包含)为右子表。
声明两个指针(或标记)分别指向temp的:i1左子表头(l)位置、i2右子表头(mid+1)位置。
比较这两个位置的元素值,如果:
(1)左子表元素值小于右子表元素值,将左子表元素写入data当前位置。左子表指针右移,data当前位置右移。
(2)右子表元素值小于左子表元素值,将右子表元素写入data当前位置。右子表指针右移,data当前位置右移。
(3)左子表遍历完,即i1到达mid+1的位置。将右子表元素写入data当前位置。右子表指针右移,data当前位置右移,相当于把右子表内的剩余元素直接写入data中。
(4)右子表遍历完,即i2到达r+1的位置。将左子表元素写入data当前位置。左子表指针右移,data当前位置右移,相当于把做子表内的剩余元素直接写入到data中。
3、重复以上步骤合并每个子序列,最后通过递归步骤将排好序的子序列合并成为越来越大的有序序列。
性能分析:
平均时间复杂度是O(nlogn) 。
速度仅次于快速排序(且为稳定排序算法)。
空间复杂度:O(n)。
稳定性:稳定。
PS:另外有改进算法如下,有时间研究一下:
http://www.cnblogs.com/zhanglanyun/archive/2012/09/03/2669416.html
In-place Merge Sort (原地归并排序)
即时间复杂度还是O(nlogn),但空间复杂度为O(1)的归并排序算法。
分享到:
相关推荐
- 归并排序:分治法,将数据分成小块排序后再合并,时间复杂度为 O(n log n)。 - 基数排序:非比较排序,利用多关键字思想,如基数排序,时间复杂度为 O(n)。 2. **时间复杂度与排序方法**: - 时间复杂度为 O(n...
5. **归并排序**(Merge Sort):归并排序是一种稳定的排序算法,它将大问题分解为小问题,再将小问题的结果合并为大问题的解。PHP中可以使用递归,将数组拆分成两半,分别排序,然后合并。 6. **堆排序**(Heap ...
7. **归并排序**:归并排序也是分治策略的应用,它将数组分为两半,分别排序,然后合并两个已排序的部分。归并排序在所有情况下都有稳定的O(n log n)时间复杂度,但需要额外的存储空间。 8. **基数排序**:基数排序...
1. **排序算法**:如快速排序、归并排序、堆排序、冒泡排序、插入排序等,它们是处理大量数据时的基础,用于按照特定顺序排列元素。 2. **搜索算法**:包括二分查找、广度优先搜索(BFS)和深度优先搜索(DFS),在数据...
1. **排序算法**:包括冒泡排序、插入排序、选择排序、快速排序、归并排序等。这些是基础的算法,用于对数据进行有效排列,理解它们的工作原理有助于优化时间复杂度。 2. **查找算法**:如线性查找、二分查找。线性...
归并排序是另一种基于分治法的排序算法,它将数组分为两半,分别排序后再合并。归并排序总是保持稳定性和O(n log n)的时间复杂度,但需要额外的内存空间。 6. **堆排序(Heap Sort)** 堆排序利用了完全二叉树的...
5. 归并排序:归并排序是另一种基于分治策略的排序算法,它将大问题分解为小问题,再合并解决。归并排序始终保持稳定,并且无论数据初始状态如何,其时间复杂度总是O(n log n),但需要额外的空间O(n)。 在C#中实现...
- 各种排序算法如冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、基数排序和计数排序的时间复杂度。 - 排序算法的稳定性,例如快速排序是不稳定的,而归并排序是稳定的。 3. **字符串处理...
其中,分治法是一种将大问题分解为小问题解决的策略,常见的分治算法包括快速排序和归并排序。排序算法如冒泡排序、插入排序、选择排序以及更高效的算法如堆排序和快速排序,它们的时间复杂度各有不同。二维排名查找...
- **实现细节**:归并排序采用分治法,将数组分成越来越小的部分,直到每个部分只有一个元素,然后再将这些小部分合并起来形成有序数组。 ##### 7. 堆排序 - **复杂度**:时间复杂度为O(n log n),空间复杂度为O(1)...
2. **排序与搜索算法**:包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等,以及二分查找、哈希查找等搜索方法。 3. **分治策略**:如快速排序、归并排序、大整数乘法(Karatsuba和Toom-Cook算法)...
1. **排序算法**:如冒泡排序、选择排序、插入排序、快速排序、归并排序等,它们用于将一组数据按照特定顺序排列。 2. **搜索算法**:二分查找、广度优先搜索(BFS)和深度优先搜索(DFS)等,这些算法在数据结构中寻找...
1. **排序算法**:冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序等的原理、优缺点及适用场景。 2. **查找算法**:顺序查找、二分查找、哈希查找等的实现和效率。 3. **图论算法**:深度优先搜索、...
5. **排序算法**:教程深入剖析了各种排序算法,如冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序等,不仅讲解了每种算法的工作原理,还比较了它们的性能差异,使读者能在不同场景下灵活选择合适的排序...
1. **排序算法**:如快速排序、归并排序、冒泡排序、插入排序、选择排序、堆排序等。这些排序算法展示了不同的时间复杂度和空间复杂度,适用于不同规模的数据处理。 2. **查找算法**:如二分查找、线性查找、哈希...
2. **排序与搜索**:如冒泡排序、快速排序、归并排序、二分查找等经典算法,这些是数据处理的基础。 3. **图论**:包括图的遍历(深度优先搜索和广度优先搜索)、最短路径算法(如Dijkstra算法和Floyd算法)以及...
- **排序算法**:快速排序、归并排序、堆排序、冒泡排序、插入排序、选择排序等。 - **查找算法**:顺序查找、二分查找、哈希查找等。 5. **递归与递推**: - **递归**是函数自我调用的方法,如斐波那契数列、...
3. **排序算法**:排序算法是经典算法之一,可能会详细讲解各种排序算法,如冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等,以及它们的优缺点和适用场景。 4. **搜索算法**:这可能包括深度优先搜索...
归并排序是一种典型的分治法算法,用于对数组进行排序。归并排序的步骤如下: 1. **Divide(划分):** 将数组分为两个子数组。 2. **Conquer(征服):** 递归地对这两个子数组进行排序。 3. **Combine(合并):*...
1. **排序算法**:包括快速排序、归并排序、冒泡排序、插入排序、选择排序、堆排序等。这些排序算法各有特点,例如快速排序平均时间复杂度为O(nlogn),归并排序适合大数据量,而冒泡排序则适用于小规模数据。 2. **...