归并排序

归并排序的核心思路

• 归并排序利用了分治算法的思想。将待排序的数组从中间分解成前后两个部分，然后再对前后两个部分从中间分解成前后两个部分，重复这样的操作，直到分解的两个部分为1个元素。然后再将相邻的两个部分合并为有序数组。重复这样的操作，直到合并为一整个数组，排序就结束了。

归并排序的操作流程。

• 归并排序主要分为两个步骤。一个是分解，一个是合并。
• 假如我们要对一个数组a[12]进行从小到大的排序。则首先将数组从中间分为a[0..5]和a[6..11]两个数组，再将数组a[0..5]从中间分为a[0..2]和a[3..5]。将数组a[6...11]从中间分为a[6..8]和a[9..11]。按照此法依次分解数组。分解到都是一个元素为止。
• 创建一个和总的数组长度一样的临时数组temp，用于存储合并的结果。
• 然后再分别合并相邻的两个数组。比如将a[0]和a[1]比较大小排序按照顺序放入到temp中，再将a[2]和a[3]比较大小排序按照顺序放入到temp中。第一次合并操作都做完后，就剩下a[0..1],a[2..3],a[4..5],a[6..7],a[7..8],a[9..10],a[11..12]这6个子数组排序问题了，再重复上述操作依次合并数组，合并时依次取出两个相邻数组元素，比较大小，将较小的元素放到temp的对应下标位置，再从这个元素的数组中取下一个数据与之前较大的元素比较。依次进行，直到某一个数组中的数据为空，则直接将另一个数组中的数组直接按顺序放入temp的对应位置。
• 直到将数组中所有的元素都比较排序并放入合并成一个整个的数组temp中。将temp的元素依次赋值给a[12],排序就结束了。

归并排序算法的相关

• 归并排序不是原地排序算法，是稳定排序算法。
• 归并排序的平均时间复杂度为O(nlogn)。
• 归并排序的优点是稳定算法。缺点就是合并两个有序数组为一个有序数组时，需要借助一个非常量级的额外的存储空间，即临时数组temp。

归并排序的代码简单实现

//归并排序
- (void)mergeSort
{
    NSMutableArray *numberArray = [NSMutableArray arrayWithArray:@[@5,@1,@6,@2,@4,@3]];
    
    NSLog(@"排序之前的结果:%@",numberArray);
    
    NSMutableArray *numberArrayTemp = [NSMutableArray arrayWithArray:@[@5,@1,@6,@2,@4,@3]];
    
    [self mergeSortwithArry:numberArray withTempArray:numberArrayTemp withleftIndex:0 withRightIndex:(int)numberArray.count-1];
    
    
    NSLog(@"排序之后的结果:%@",numberArray);
}

- (void)mergeSortwithArry:(NSMutableArray *)array withTempArray:(NSMutableArray *)arrayTemp withleftIndex:(int)left withRightIndex:(int)right
{
    int mid;
    
    if (left < right) {
        
        mid = left + (right-left)/2;
        
        [self mergeSortwithArry:array withTempArray:arrayTemp withleftIndex:left withRightIndex:mid];
        
        [self mergeSortwithArry:array withTempArray:arrayTemp withleftIndex:mid+1 withRightIndex:right];
        
        [self mergewithArry:array withTempArray:arrayTemp withleftIndex:left withRightIndex:right withMidIndex:mid];
    }
}

- (void)mergewithArry:(NSMutableArray *)array withTempArray:(NSMutableArray *)arrayTemp withleftIndex:(int)left withRightIndex:(int)right withMidIndex:(int)mid
{
    int i = left;
    
    int j = mid+1;
    
    int k = left;
    
    while (i != mid+1 && j != right+1) {
        
        if ([array[i] intValue] > [array[j] intValue]) {
            arrayTemp[k++] = array[j++];
        }else {
            arrayTemp[k++] = array[i++];
        }
    }
    
    while (i != mid+1) {
        arrayTemp[k++] = array[i++];
    }
    
    while (j != right+1) {
        arrayTemp[k++] = array[j++];
    }
    
    for (int a = left; a<=right; a++) {
        array[a] = arrayTemp[a];
    }
    
}