归并排序
百度上的解释：归并排序：是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
学习归并排序之前，需要理解一下分治思想。
分治思想：
a.将大问题划分为N个小问题，
b.解决每个小问题，
c.将解决完的小问题合并起来，形成一个整体，就把原来的大问题解决好了。
应用：
（1）二分法（二分查找），可以提高效率
(2)小例子：找假硬币 （在8个硬币中有一个是假的，问假币是清的，还是重的）
解决：将硬币均分为两堆（A与B） ，对比重量，这时候A与B会不相等， 然后再分别将A与B均分 （c、 d 与 e、 f），然后一次，比较 c与d ，e与f ,此时，哪一组的重量不相等 ，假币就在哪一组。假设A 比B重，然后 ，A 中的c与d 不相等，则假币是重了， 反之就是轻了。（用这个方法再推算下去，可以得到哪个是假币）。
归并排序的两种方式 ：（1）for循环 （本文主要是介绍以for循环的方式） （2）递归
for循环方式：讲数组分为 2个数组 -->4个--> 8个-->...知道长度为1的数组结束
然后开始两两归并，直到得到有序数组
相比于递归的方式的好处是减少栈空间的大小。
例子： A[] = [ 5,3,6,2,7]
分析：将这个数组拆分 [{5},{3},{6},{2},{7}]
归并 两两相邻归并-->[{5},{3}, | {6},{2},{7}] ==>
[3, 5] , [2,6] ,[7] --> [3, 5] , [2,6] | ,[7] ==>
[2 ,3,5,6],[7] -->[2 ,3,5,6],| [7] ==>
[2,3,5,6,7]
代码实现：（要注意对边界值的分析）
将数组分开，取一个中间值 划分为两个部分
startIndex -- middle-- endInden
划分 ：
前一部分 ：startIndex --middle
后一部分：middle + 1 -- endIndex
判断当 startIndex == endIndex -->数组问有序状态
然后归并：（前后两部分，分别完成之后在执行）
前一部分起始： preIndex
后一部分起始: nextIndex:
preIndex的范围是在0 到middle nextIndex的范围是在middle +1 到end
#pragma mark -for循环方式
+(void)sortCArray:(int*)a to:(int*)b length:(int)length groupLength:(int)groupLength{
intstartIndex =0;
while(startIndex < length) {
intpreIndex = startIndex;
intnextIndex = startIndex +groupLength;
inti = startIndex;
while(preIndex != startIndex + groupLength && nextIndex != startIndex +groupLength*2&& nextIndex< length) {
//当preIndex <= nextIndex的时候
//b[i]= a[preIndex]
if(a[preIndex] <= a[nextIndex]) {
b[i++] = a[preIndex++];
}else{
//当preIndex > nextIndex的时候
//b[i] = a[nextIndex]
b[i++] = a[nextIndex ++];
}
}
//判读最后升一下一个的情况 a .如果是前一部分没有完成 就归到前一部分
while(preIndex != startIndex +groupLength && i < length) {
b[i++]= a[preIndex++];
}
//b.如果是后一部分没有完成，就归到后一部分
while(nextIndex !=startIndex + groupLength*2&& i< length) {
b[i++]= a[nextIndex ++];
}
startIndex += groupLength *2;
}
}
得到 b是有序的，a是无序的数组
然后 讲b拷贝到a数组
在举个例子解释一下实现过程 数组 a[] = [5,3,2,4,7] （P表示preIndex N表示nextIndex ）
5, 3, 2,4, 7
...(省略中间部分)
[2 ,3 ,5] | [4,7]
b[0] -->2 2 与4 比较
b[1] -->3 3 与 4比较
b[2] -->4 5与4 比较
b[3] --> 5 5与7比较
到这里比较完一轮 但是7还没有比较完出来
在进行下一轮比较 由于7在后一部分 所以b[4]--7
扩展性：
归并类属于外排序
稳定性：
相等两个元素，比较，相对文字发生改变，者是不稳定，反之，是稳定的
例子 [ 2, 7 , 5, 3,5] 排序结果是[2,3,5,5,7]
如果是 5>=5 交换位置 则是不稳定 反之则是稳定
稳定排序 ：归并排序 、插入排序
不稳定排序： 选择排序，快速排序，堆排序；二叉树排序
最后说一个题目 （主要也是归并的运用）
1.有n个不相等，且元素个数小雨1000000请用一种最快的方式排序
解决方式有很多种，但是题目强调是最快，就是要循环的次数比较小
用比特位在完全二叉树下，讲每个数组下标来表示元素，同事让数组最小。
所以使用char类型的数组，或者更小的bit数组
char b[1000000] = {}
假设 a []= [6,3,1,7];
b为b[]的下标 即b[]= [0,1,2,3,4,5,6,7,8,......]
对比a[]与b[]
得到[0,1,0,1,0,0,1,1,0,.....],
得到新的b下标对应数组[1,3,6,7] 就是所求的的结果
网友评论