您的位置: 首页  >  文章  >  oc归并算法实现

oc归并算法实现

分类: 文章 • 2025-02-25 09:24:22

合并算法Merge Sort

给定整数数组，使用Merge Sort算法对数组进行排序。
示例：
数组：12,35,87,26,9,28,7 
输出：7,9,12,26,28,35,87

  • 算法/洞察

Merge sort是一种基于比较的算法，它使用分而治之的方法在O（n logn）时间内对数组进行排序。
合并排序是一种稳定排序，即它在排序后保留相同数组元素的顺序。

合并排序算法是：
步骤1.递归地将数组分成两半。
步骤2.按排序顺序合并分割的部分。

下面是一个解释算法的例子：

oc归并算法实现

首先，数组{12,35,87,26,9,28,7}被分为子阵列{12,35,87,26}和{9,28,7}如上图所示。
然后{12,35,87,26}分为{12,35}和{87,26}。
下一页{12,35}分为{12}和{35}
在此步骤中，单个元素阵列{12}和{35}无法进一步划分。
下一步是按排序顺序合并这些数组以获得{12,35} 

Next {87,26}分为{87}和{26} 
类似于上面，我们按排序顺序合并这些单个元素数组以获得{26} ，87} 

现在我们处于{12,35}和{26,87}的阶段。我们按排序顺序合并这些子数组以形成排序数组：{12,26,35,87} 

同样，{9,28,7}也首先递归划分，然后按排序顺序合并以获得排序数组{7,9， 28} 

最后，我们合并排序的子阵列{12，26，35，87}和{7,9，28}以排序的顺序，以获得排序后的数组{7,9，12，26，28，35，87}。

以下是合并代码片段中给出的合并排序算法使用的2个排序数组的算法：
1。创建临时数组temp1和temp2。
2.将第一个子数组的元素复制到temp1。所以，temp1 = {12,26,35,87} 
3.将第二个子阵列的元素复制到temp2。所以，temp2 = {7,9,28} 
4.现在将temp1和temp2中的元素按排序顺序复制到原始数组：
   a。遍历数组temp1和temp2：
   b。如果temp1 [i] <= temp2 [j]，则将temp1 [i]复制到原始数组并将i移动到temp1中的下一个元素。
   C。否则将temp2 [j]复制到原始数组并将j移动到temp2中的下一个元素。
   d。如果到达一个临时数组的末尾，则以相同的顺序将另一个临时数组的元素复制到原始数组。

 

oc合并算法实现：

#import "PSAlgorithmVM.h"

@implementation PSAlgorithmVM
+ (PSAlgorithmVM *)shareClient
{
    static PSAlgorithmVM *_shareClient = nil;
    static dispatch_once_t onceToken;
    dispatch_once(&onceToken, ^{
        _shareClient = [[PSAlgorithmVM alloc] init];
        
    });
    return _shareClient;
}

/*
 合并排序算法是：
 步骤1.递归地将数组分成两半。
 步骤2.按排序顺序合并分割的部分。
 */
/*
1。创建临时数组temp1和temp2。
2.将第一个子数组的元素复制到temp1。所以，temp1 = {12,26,35,87}
3.将第二个子阵列的元素复制到temp2。所以，temp2 = {7,9,28}
4.现在将temp1和temp2中的元素按排序顺序复制到原始数组：
a。遍历数组temp1和temp2：
b。如果temp1 [i] <= temp2 [j]，则将temp1 [i]复制到原始数组并将i移动到temp1中的下一个元素。
C。否则将temp2 [j]复制到原始数组并将j移动到temp2中的下一个元素。
d。如果到达一个临时数组的末尾，则以相同的顺序将另一个临时数组的元素复制到原始数组。
 */
/*
 最终归并位置：k
 归并前数组1位置：i
 归并后数组2位置：j
 
 最左边元素：start
 最右边元素：end
 中间位置：middle
 */
- (void)mergeSort:(NSMutableArray *)arr
{
    [self beginMergeSort:arr
              start:0
                end:arr.count-1];
}
- (void)beginMergeSort:(NSMutableArray *)arr
            start:(NSInteger)start
              end:(NSInteger)end
{
    if (start<end) {
        NSInteger mid = (start+end)/2;
        //递归划分
        [self beginMergeSort:arr start:start end:mid];
        [self beginMergeSort:arr start:mid+1 end:end];
        [self mergeWithArr:arr start:start mid:mid end:end];
    }
}
//按顺序合并分割部分
- (void)mergeWithArr:(NSMutableArray *)arr
               start:(NSInteger)start
                 mid:(NSInteger)mid
                 end:(NSInteger)end
{
    NSInteger n1 = mid-start+1;
    NSInteger n2 = end-mid;
    NSMutableArray *tempArr1 = [NSMutableArray arrayWithCapacity:n1];
    NSMutableArray *tempArr2 = [NSMutableArray arrayWithCapacity:n2];

    for (int i=0;i< n1;i++) {
        [tempArr1 addObject:arr[start+i]];
    }

    for (int j=0;j<n2;j++) {
        [tempArr2 addObject:arr[mid+j+1]];
    }

    NSInteger i = 0;//归并前数组1元素位置
    NSInteger j = 0; //归并后数组2元素位置
    NSInteger k = start; //最终归并位置

    while (i<n1 && j<n2) {
        if ([tempArr1[i] integerValue]<=[tempArr2[j] integerValue]) {
            //两组元素比较，如果位置i的元素比较小 i元素放在k位置,并且i往后推
            arr[k] = tempArr1[i];
            i++;
        }
        else{
            arr[k] = tempArr2[j];
            j++;
        }
        k++;
    }

    //分别各剩下一组元素时
    while (i<n1) {
        arr[k] = tempArr1[i];
        i++;
        k++;
    }

    while (j<n2) {
        arr[k] = tempArr2[j];
        j++;
        k++;
    }

    NSLog(@"1:排序后：%@",arr);
}

@end

 

相关推荐