美文网首页
iOS:归并排序

iOS:归并排序

作者: 街角仰望 | 来源:发表于2020-05-22 15:52 被阅读0次

    归并排序算法

    归并排序(Merging Sort) 就是利用归并的思想实现的排序方法。它的原理是假设初始序列含有n个记录,则可以看成是n个有序的子序列,每个子序列的长度为1,然后两两归并,得到n/2个长度为2或者1的有序子序列;再两两归并,......,如此反复,直到得到一个长度为n的有序序列为止,这种排序方法称为归并排序。

    示例图如下:

    通俗点解释:把数组元素拆分开,两两循环排序,例如[4,3,2,1]。先是4和3排序 -> [3,4], 2和1排序 -> [1,2]。最后[3,4]和[1,2]排序 -> [1,2,3,4]。

    代码如下

    - (void)megerSortAscendingOrderSort:(NSMutableArray *)ascendingArr
    {
        //tempArray数组里存放ascendingArr个数组,每个数组包含一个元素
        NSMutableArray *tempArray = [NSMutableArray arrayWithCapacity:1];
        for (NSNumber *num in ascendingArr) {
            NSMutableArray *subArray = [NSMutableArray array];
            [subArray addObject:num];
            [tempArray addObject:subArray];
        }
        //开始合并为一个数组
        while (tempArray.count != 1) {
            NSInteger i = 0;
            while (i < tempArray.count - 1) {
                tempArray[i] = [self mergeArrayFirstList:tempArray[i] secondList:tempArray[i + 1]];
                [tempArray removeObjectAtIndex:i + 1];//这里 tempArray[i] 重置后,tempArray[i + 1]数据已加入到tempArray[i],所以要删除
                i++;
            }
        }
        NSLog(@"归并升序排序结果:%@", tempArray[0]);
    }
     
    - (NSArray *)mergeArrayFirstList:(NSArray *)array1 secondList:(NSArray *)array2 {
        NSMutableArray *resultArray = [NSMutableArray array];
        NSInteger firstIndex = 0, secondIndex = 0;
        while (firstIndex < array1.count && secondIndex < array2.count) {
            if ([array1[firstIndex] floatValue] < [array2[secondIndex] floatValue]) {
                [resultArray addObject:array1[firstIndex]];
                firstIndex++;
            } else {
                [resultArray addObject:array2[secondIndex]];
                secondIndex++;
            }
        }
        while (firstIndex < array1.count) {
            [resultArray addObject:array1[firstIndex]];
            firstIndex++;
        }
        while (secondIndex < array2.count) {
            [resultArray addObject:array2[secondIndex]];
            secondIndex++;
        }
        return resultArray.copy;
    }
    

    复杂度分析

    我们来分析一下时间复杂度,一趟归并需要将1~n个相邻的元素进行两两归并,需要的时间为O(n),整个归并排序需要进行log₂n次,因此总的时间复杂度为O(nlogn)。 这是该算法中最好、最坏和平均的时间性能。

    由于在归并过程中需要原始序列同样数量的存储空间n和递归时深度为logn的栈空间,因此空间复杂度为O(n+logn)。

    因为是两两比较,不存在跳跃,因此是一种稳定的排序算法。虽然占用内存比较多,但却是一种效率高的算法。

    参考:https://blog.csdn.net/minggeqingchun/article/details/78393361

    相关文章

      网友评论

          本文标题:iOS:归并排序

          本文链接:https://www.haomeiwen.com/subject/jevcohtx.html