歸并排序
1. 不斷的將當(dāng)前序列，分割成兩個子序列,直到分割到一個元素不能分割為止
2. 不斷的將兩個子序列合并成一個有序序列，直到最后只剩下一個有序序列
代碼及注釋
看代碼里面的注釋
//
// SCXMergeSoft.m
// TestArithmetic
//
// Created by 孫承秀 on 2020/7/13.
// Copyright ? 2020 孫承秀. All rights reserved.
//
#import "SCXMergeSoft.h"
/*
1. 不斷的將當(dāng)前序列，分割成兩個子序列,直到分割到一個元素不能分割為止
2. 不斷的將兩個子序列合并成一個有序序列，直到最后只剩下一個有序序列
*/
@interface SCXMergeSoft()
@property (nonatomic , strong) NSMutableArray *softArr;
@property (nonatomic , strong) NSMutableArray *leftArr;
@end
@implementation SCXMergeSoft
- (NSArray *)soft:(NSArray<NSNumber *> *)arr{
NSMutableArray *soft = arr.mutableCopy;
self.softArr = soft;
self.leftArr = [NSMutableArray arrayWithCapacity:(soft.count) >> 1];
[self binary:0 end:soft.count];
return soft.copy;;
}
- (void)binary:(int)begin end:(int) end{
// 至少要有兩個元素
if (end - begin < 2) {
return;
}
int mid = (end + begin ) >> 1;
// 將左邊的不斷的拆分，直到拆分到一個元素
[self binary:begin end:mid];
// 將右邊的不斷的拆分，直到拆分到一個元素
[self binary:mid end:end];
// 不斷的將兩個元素合并
[self merge:begin mid:mid end:end];
}
/*
merge 的原理:
比如一個數(shù)組[1,6,2,7,3,8,4,9];
1.我們經(jīng)過不斷的拆分之后變成1,6 2,7 3,8 4,9 ,這樣的
2. 然后將上面拆分出來的一個一個數(shù)據(jù)，兩個連個再次合并到一起，[1,6],[2,7],[3,8],[4,9]
然后再變成[1,2,6,7],[3,4,8,9]
然后再變成[1,2,3,4,6,7,8,9];
這個流程
3.其實我們最終的目的其實就是將所有的元素合并到一個大數(shù)組里面，其實我們的最后[1,2,3,4,6,7,8,9];，一次，這個數(shù)據(jù)就是最終的大數(shù)組，而他是由之前的兩份數(shù)據(jù)得來的，所以我們可以將大數(shù)組拆分成一個小數(shù)組，然后每次將小數(shù)組的元素和當(dāng)前大數(shù)組剩余的元素作比較，然后依次比較添加，什么意思呢？
將 [1,2,3,4,6,7,8,9]; ，的左一半copy出來，其余元素不變，也就是
[1,2,3,4,6,7,8,9]; 和 [1,2,3,4,];
或者你可以理解為
[null,null,null,null,6,7,8,9]; 和 [1,2,3,4]; 最后將這兩個合并不就是 [1,2,3,4,6,7,8,9];嗎
*/
- (void)merge:(int)begin mid:(int)mid end:(int) end{
// 定義標(biāo)記,對應(yīng)于數(shù)組的索引
// 左邊的開始位置的標(biāo)記
int lb = 0;
// 左邊的結(jié)束位置的標(biāo)記
int le = mid - begin;
// 右邊開始位置的標(biāo)記
int rb = mid;
// 右邊結(jié)束位置的標(biāo)記
int re = end;
// 整個大數(shù)組的標(biāo)記
int ab = begin;
// 左邊備份的數(shù)組
for (int i = lb; i < le; i ++) {
self.leftArr[i] = self.softArr[begin + i];
}
NSLog(@"----%@",self.leftArr);
// 左右進行比對
while (lb < le) {
// 左邊沒有排完，就將左邊的依次放到大數(shù)組里面
// 如果左邊排完了，右邊不動就行
// 判斷如果左邊拿出來的元素比右邊拿出來的元素小，就放到大數(shù)組里面
NSNumber *left = self.leftArr[lb];
NSNumber *right = self.softArr[rb];
// 如果右邊的大或者右邊排完了，那么就跳出來這if，跑到下面去，因為右邊的大，肯定是將左邊放進去，或者右邊的所有元素都取完了，那么也跑到else里面
if (rb< re && left.intValue > right.intValue ) {
// 如果左邊的大于等于右邊的，就將右邊的放入大數(shù)組的前面
self.softArr[ab++] = right;
rb++;
} else {
// 如果右邊的比左邊大或者等于左邊當(dāng)前取出的，就將左邊的先取出來放到數(shù)組里面，這樣可以保證算法的穩(wěn)定性
self.softArr[ab++] = left;
lb++;
}
}
NSLog(@"~~~~~%@",self.softArr);
}
@end
重點分析
測試數(shù)據(jù)為
NSArray *arr = @[@5,@4,@7,@7,@1,@9,@8,@10];
SCXMergeSoft *soft = [[SCXMergeSoft alloc] init];
NSArray *res = [soft soft:arr];
我們這里看下 leftArr 的打印，來分析下原因
020-07-13 22:19:03.337475+0800 TestArithmetic[49631:5195808] ----(
5
)
2020-07-13 22:19:03.337651+0800 TestArithmetic[49631:5195808] ~~~~~(
4,
5,
7,
7,
1,
9,
8,
10
)
2020-07-13 22:19:03.337769+0800 TestArithmetic[49631:5195808] ----(
7
)
2020-07-13 22:19:03.337887+0800 TestArithmetic[49631:5195808] ~~~~~(
4,
5,
7,
7,
1,
9,
8,
10
)
2020-07-13 22:19:03.337998+0800 TestArithmetic[49631:5195808] ----(
4,
5
)
2020-07-13 22:19:03.338115+0800 TestArithmetic[49631:5195808] ~~~~~(
4,
5,
7,
7,
1,
9,
8,
10
)
2020-07-13 22:19:03.338212+0800 TestArithmetic[49631:5195808] ----(
1,
5
)
2020-07-13 22:19:03.338331+0800 TestArithmetic[49631:5195808] ~~~~~(
4,
5,
7,
7,
1,
9,
8,
10
)
2020-07-13 22:19:03.338426+0800 TestArithmetic[49631:5195808] ----(
8,
5
)
2020-07-13 22:19:03.338510+0800 TestArithmetic[49631:5195808] ~~~~~(
4,
5,
7,
7,
1,
9,
8,
10
)
2020-07-13 22:19:03.338574+0800 TestArithmetic[49631:5195808] ----(
1,
9
)
2020-07-13 22:19:03.338840+0800 TestArithmetic[49631:5195808] ~~~~~(
4,
5,
7,
7,
1,
8,
9,
10
)
2020-07-13 22:19:03.339062+0800 TestArithmetic[49631:5195808] ----(
4,
5,
7,
7
)
2020-07-13 22:19:03.344108+0800 TestArithmetic[49631:5195808] ~~~~~(
1,
4,
5,
7,
7,
8,
9,
10
)
其中---開頭的為leftaarr，~~~開頭的為總數(shù)據(jù)
第一次我們調(diào)用 binary 方法，進行二分拆分的時候，拆分到最小的時候，begin為0，end為2，mid為1，也就是說，[0,2),[2,4),這樣不能再拆分了，這時候我們調(diào)用 merge 方法，此時 leftArr的值為第一個元素為5，然后這時候會進行第二次merge，之后為[2,4),這時候也是一份元素，這時候leftArr的數(shù)組元素被替換成了[2,4)這個區(qū)間的第一個元素，所以這時候打印7，這時候原來大數(shù)組的總左區(qū)間已經(jīng)被拆分的不能拆分了，并且進行了兩次小合并，分別為[0,2),[2,4),兩個小區(qū)間分別的合并，這時候leftArr是總的元素的一半，所以只有一個元素，第二次替換了第一次的元素的值，所以最后為7，然后將[0,2),[2,4),合并起來，就是左半?yún)^(qū)間合并一共四個元素，而leftarr一半為連個元素，所以這時候打印，[4,5];排好序了，其實這時候總arr的數(shù)據(jù)應(yīng)該為[4,5,77],leftarr占一半，所以為【4,5】;,然后右邊同理，顯示[4,6),這時候?qū)⒋髷?shù)組的第五個元素放入到leftArr中，此時為1，因為leftarr已經(jīng)有[4,5];了，所以將第一個元素替換為1就為【1，5】；,然后，同理，將右半部分的右半部分，也就是[6,8)的元素，取出第一個放到leftarr，所以這時候?qū)1,5] 變成了[8,5];同理，接下來將右大半部分繼續(xù)進行merge，這時候右邊的數(shù)據(jù)應(yīng)該為[1,9,8,10];所以一半leftarr為[1,9],最后將整體數(shù)組排序，所以leftarr為[4577];
時間復(fù)雜度
T(n) = T(n/2)（折半拆分） + T(n/2)（折半拆分） + O(n)(merge 方法) = 2 * T(n/2) + O(n)
結(jié)論：時間復(fù)雜度為：O(nlogn)
