归并排序
- 1.不断地将当前序列平均分割成2个子序列，直到不能在分割（每个序列中只剩下一个元素）
- 2.不断地将两个子序列合并成一个有序序列，直到最终剩下一个有序序列
- 3.归并排序要比（冒泡排序，选择排序，插入排序）效率要高
//归并排序
- (void)mergeSortWithArray:(NSMutableArray *)array
{
[self sortWithBegin:0 end:(int)array.count array:array];
}
- (void)sortWithBegin:(int)begin end:(int)end array:(NSMutableArray *)array
{
if (end - begin < 2) return;
int mid = (begin + end) >> 1;
[self sortWithBegin:begin end:mid array:array];
[self sortWithBegin:mid end:end array:array];
[self mergeWithBegin:begin mid:mid end:end array:array];
}
- (void)mergeWithBegin:(int)begin mid:(int)mid end:(int)end array:(NSMutableArray *)array
{
//两个数组
//begin：需要合并的开始位置
//mid：需要合并的中间位置
//end：需要合并的结束位置
//leftArray：从array中分割出来的左半部分
//array：总数组
int li = 0;//左部分数组开始索引
int le = mid - begin;//左部分结束索引
int ai = begin;//插入位置索引
int ri = mid;//右半部分开始索引
int re = end;//右半部分结束索引
NSMutableArray *leftArray = [[NSMutableArray alloc] init];
for (int i = 0; i < le; i ++) {
leftArray[i] = array[begin + i];
}
while (li < le) {
NSNumber *lV = leftArray[li];
NSNumber *rV = @0;
if (ri < re) {
rV = array[ri];
}
if (ri < re && [lV integerValue] > [rV integerValue]) {
array[ai] = array[ri];
ai ++;
ri ++;
}else{
array[ai] = leftArray[li];
ai ++;
li ++;
}
}
//不用做任何操作
}
