排序
排序是iOS算法中提及最多的話題，比較有名的有八大排序算法。
image.png
數(shù)據(jù)結(jié)構(gòu)常見的八大排序算法（詳細整理）
1.快速排序
這個是曝光率最高的排序算法，基本思想：挖坑填數(shù)+分治法
從序列當中選擇一個基準數(shù)(pivot)，在這里我們選擇序列當中第一個數(shù)最為基準數(shù)；
將序列當中的所有數(shù)依次遍歷，比基準數(shù)大的位于其右側(cè)，比基準數(shù)小的位于其左側(cè)；
遞歸，左右兩邊分別進行以上步驟；退出條件：未排序序列長度為0；
快速排序的
Object-C代碼如下：
- (void)quickSort:(NSMutableArray *)mutableArray start:(NSInteger)start end:(NSInteger)end {
// 遞歸函數(shù)退出條件：只有1個元素或者沒有元素
if (start >= end) {
return;
}
// 取第一個元素為基準元素
id pivot = mutableArray[start];
// 設(shè)置可以移動的下標
NSInteger i = start;
NSInteger j = end;
// 不斷重復(fù)，將小于基準pivot的移到左邊；將大于基準pivot的移到右邊；形成兩個子數(shù)組；
while (i < j) {
// 從右開始向左尋找第一個小于pivot的值；(對于本來就大于或者等于基準的數(shù)，保持不動)
while ((i < j) && ([mutableArray[j] hash] >= [pivot hash])) {
j--;
}
// 將小于pivot的值移到左邊;填坑mutableArray[I]
if (i < j) {
mutableArray[i] = mutableArray[j];
}
// 從左開始向右尋找第一個大于pivot的值;(對于本來就小于或者等于基準的數(shù)，保持不動)
while ((i < j) && ([mutableArray[i] hash] <= [pivot hash])) {
I++;
}
// 將大于pivot的值移到右邊; 填坑mutableArray[j]；(mutableArray[j]上一步已經(jīng)移到左邊，現(xiàn)在已經(jīng)是坑了)
if (i < j) {
mutableArray[j] = mutableArray[I];
}
}
// 循環(huán)結(jié)束后，說明 i==j，此時左邊的值全都小于pivot,右邊的值全都大于pivot
// 將一開始就挖出的基準pivot放回兩個子數(shù)組的中間位置
mutableArray[i] = pivot; // 這個時候i == j；用mutableArray[j] = pivot;也是可以的
// 遞歸，對左右兩個子數(shù)組繼續(xù)進行“挖坑填數(shù)”操作; 這個時候i==j； i或者j的位置是基準數(shù)，已經(jīng)排好，不需要再參加排序
// 左側(cè)序列繼續(xù)排序
[self quickSort:mutableArray start:start end:(i-1)];
// 右側(cè)序列繼續(xù)排序
[self quickSort:mutableArray start:(j+1) end:end];
}
由于
iOS中數(shù)組成員是對象，所以取hash值進行比較。注意：對象不能直接用"<、 =、 >"等進行比較，否則可能會出現(xiàn)@88 > @89的情況。實際試驗，對于NSString和NSNumber，采用hash值比較，效果很不錯。
- 封裝：實現(xiàn)算法的時候，以可變數(shù)組為參數(shù)，排序之后，可變數(shù)組參數(shù)內(nèi)容被改變。在實際使用中，改變傳入?yún)?shù)內(nèi)容的做法很不好。所以封裝一層，不改變使用者給的參數(shù)，將排序結(jié)果，以一個新數(shù)組的形式返回，保持“純函數(shù)”的特性。
/**
排序算法名稱
*/
typedef NS_ENUM(NSInteger,SortType) {
// 快速排序
SortTypeQuick = 1,
};
// 統(tǒng)一封裝，以返回值的形式給出排序結(jié)果，不改變用戶給出的參數(shù)，保持“純函數(shù)”特性
- (nullable NSArray *)sort:(nullable NSArray *)array type:(SortType)type {
// 參數(shù)檢查
if ((array == nil) || (array.count <= 1)) {
return nil;
}
// 使用可變數(shù)組進行操作，不改變輸入?yún)?shù)
NSMutableArray *tempArray = [NSMutableArray arrayWithArray:array];
// 根據(jù)SortType參數(shù)選擇不同的排序算法
switch (type) {
case SortTypeQuick:
[self quickSort:tempArray start:0 end:(tempArray.count-1)];
break;
default:
break;
}
// 返回排序后的數(shù)組
return [tempArray copy];
}
- 測試：可以用一個數(shù)字和字符的混合數(shù)組進行測試：
//
//
// 統(tǒng)一的測試代碼
//
//
- (void)sortTest:(SortType)type {
NSArray *arrayBeforeSort = [NSMutableArray arrayWithObjects:@89,@"hello",@22,@95,@"Hello",@66,@22,@"world",@57, nil];
NSLog(@"快速排序之前：%@", arrayBeforeSort);
NSArray *arrayAfterSort = [self sort:arrayBeforeSort type:type];
NSLog(@"快速排序之后：%@", arrayAfterSort);
}
企業(yè)微信截圖_d4a70aab-e5ef-4bed-ad68-cabf71fbd223.png
2. 冒泡排序
- 將序列當中的左右元素，依次比較，保證右邊的元素始終大于左邊的元素；
（ 第一輪結(jié)束后，序列最后一個元素一定是當前序列的最大值；） - 對序列當中剩下的n-1個元素再次執(zhí)行步驟1。
- 對于長度為n的序列，一共需要執(zhí)行n-1輪比較
- (void)bubbleSort:(NSMutableArray *)mutableArray {
// 執(zhí)行n-1輪，最后一個元素不需要比較
for (NSInteger i = 0; i < (mutableArray.count - 1); i++) {
for (NSInteger j = 0; j < (mutableArray.count - i - 1); j++) {
// 如果比旁邊的元素大，就交互
if ([mutableArray[j] hash] > [mutableArray[j+1] hash]) {
id temp = mutableArray[j];
mutableArray[j] = mutableArray[j+1];
mutableArray[j+1] = temp;
}
}
}
}
3. 選擇排序
從當前序列選出最小的元素，排在第1位；
從余下的n-1個元素中選出最小值，排在第2位；
.... 進行n-1輪，就排好了。
- (void)selectSort:(NSMutableArray *)mutableArray {
// 執(zhí)行n-1輪，最后一個元素不需要比較
for (NSInteger i = 0; i < (mutableArray.count - 1); i++) {
// 最小值默認是本輪第1個
NSInteger minIndex = I;
// 將余下的逐個比較，記下最小值的下標
for (NSInteger j = i; j < mutableArray.count; j++) {
if ([mutableArray[j] hash] < [mutableArray[minIndex] hash]) {
minIndex = j;
}
}
// 將最小值和當前位置交換
if (minIndex != i) {
id temp = mutableArray[I];
mutableArray[i] = mutableArray[minIndex];
mutableArray[minIndex] = temp;
}
}
}
4. 堆排序
- 首先將序列構(gòu)建稱為"大頂堆"；
（這樣滿足了大頂堆那條性質(zhì)：位于根節(jié)點的元素一定是當前序列的最大值）
image.png
- 取出當前大頂堆的根節(jié)點，將其與序列末尾元素進行交換；
（此時：序列末尾的元素為已排序的最大值；由于交換了元素，當前位于根節(jié)點的堆并不一定滿足大頂堆的性質(zhì)）
image.png
交換后，排好了一個元素，但是堆被破壞了。接下來仍然需要先創(chuàng)建“大頂堆”，然后交換
- .... 繼續(xù)重復(fù)n-1次，全部排好。
// 大頂堆調(diào)整
- (void)maxHeapAdjust:(NSMutableArray *)mutableArray start:(NSInteger)start end:(NSInteger)end {
// 建立父節(jié)點指標和子節(jié)點下標
NSInteger dadIndex = start;
NSInteger sonIndex = 2 * dadIndex + 1;
// 在范圍內(nèi)，進行比較和交互，保證父節(jié)點比兩個子節(jié)點都大
while (sonIndex <= end) {
// 兩個子節(jié)點比較，取大的那個
if (((sonIndex + 1) <= end) && ([mutableArray[sonIndex + 1] hash] > [mutableArray[sonIndex] hash])) {
sonIndex++;
}
// 父節(jié)點大于子節(jié)點，調(diào)整完成
if ([mutableArray[dadIndex] hash] > [mutableArray[sonIndex] hash]) {
return;
} else {
// 父節(jié)點小于子節(jié)點，交互兩個值
id temp = mutableArray[dadIndex];
mutableArray[dadIndex] = mutableArray[sonIndex];
mutableArray[sonIndex] = temp;
// 父節(jié)點較小，和子節(jié)點交互完畢后，繼續(xù)與孫子節(jié)點比較
dadIndex = sonIndex;
sonIndex = 2 * dadIndex + 1;
}
}
}
// 堆排序
- (void)heapSort:(NSMutableArray *)mutableArray {
// 初始化，創(chuàng)建大頂推；
// 最后一個有孩子的節(jié)點的位置 i = (length -1) / 2
for (NSInteger i = (mutableArray.count - 1) / 2; i >= 0; i--) {
[self maxHeapAdjust:mutableArray start:i end:(mutableArray.count - 1)];
}
// 重復(fù)n次； 1.把根節(jié)點（第一個元素，也就是最大的元素）和當前排列的元素交換，排好一個；2，將剩余的元素調(diào)整為大頂推
for (NSInteger j = (mutableArray.count - 1); j > 0; j--) {
// 交換根節(jié)點，也就是0號元素和當前位置
id temp = mutableArray[0];
mutableArray[0] = mutableArray[j];
mutableArray[j] = temp;
// 調(diào)整剩余的元素為大頂堆
[self maxHeapAdjust:mutableArray start:0 end:(j-1)];
}
}
5. 插入排序
插入排序的基本思想是：每步將一個待排序的記錄，按其關(guān)鍵碼值的大小插入前面已經(jīng)排序的文件中適當位置上，直到全部插入完為止
// 插入排序
- (void)insertSort:(NSMutableArray *)mutableArray {
// 遍歷數(shù)組中的所有元素，其中0號索引元素默認已排序，因此從1開始
for (NSInteger i = 1; i < mutableArray.count; i++) {
// 要找插入位置，前面已經(jīng)排好的序列要往后面挪一個位置，所以要先把當前的待插入元素先保存起來
id temp = mutableArray[I];
// 從已經(jīng)排好的序列尾部往前找，第一個數(shù)也要參與比較
for (NSInteger j = i; j > 0; j--) {
if ([mutableArray[j-1] hash] > [temp hash]) {
// 前面的元素比現(xiàn)在的大，就往后挪一格；
mutableArray[j] = mutableArray[j-1];
// 如果第0號元素都比當前元素大，那么當前元素要插入第0號位置
if ((j-1) == 0) {
mutableArray[0] = temp;
break;
}
} else {
// 后面的元素比當前的大，就說明找到位置了，插入，完成此輪排序
mutableArray[j] = temp;
break;
}
}
}
}
未完待續(xù).....
希爾排序，歸并排序，基數(shù)排序這三種，看了參考文章，不是很理解，暫時就不實踐了。
二叉搜索樹
樹： 每個結(jié)點有零個或多個子結(jié)點；沒有父結(jié)點的結(jié)點稱為根結(jié)點；每一個非根結(jié)點有且只有一個父結(jié)點；
二叉樹： 是每個結(jié)點最多有兩個子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。
一棵深度為k，且有2^k-1個節(jié)點的二叉樹，稱為滿二叉樹。這種樹的特點是每一層上的節(jié)點數(shù)都是最大節(jié)點數(shù)。
在一棵二叉樹中，除最后一層外，若其余層都是滿的，并且最后一層或者是滿的，或者是在右邊缺少連續(xù)若干節(jié)點，則此二叉樹為完全二叉樹。二叉查找樹（Binary Search Tree），（又：二叉搜索樹，二叉排序樹： 它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：
- 若它的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值，（大頂堆）；
- 若它的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值，（小頂堆）；
- 它的左、右子樹也分別為二叉排序樹。
- 沒有鍵值相等的節(jié)點。
二叉樹遍歷：以跟為參考來說。前序：根-》左-》右；中序：左-》根-》右；后序：左-》右-》根
二叉樹算法主要是遞歸的思想
二叉搜索樹的Model
對于二叉搜索樹這種數(shù)據(jù)類型，用簡單的數(shù)組來表示是不適合的。所以要建立一個模型：
值： 就用最簡單的整數(shù)來表示，實際使用中，這個整型值也是必不可少的，可以單做key來用，這是二叉搜索樹排序的憑證。
左子樹： 用一個同類型的指針表示
右子樹： 用一個同類型的指針表示
以上3個是二叉搜索樹必不可少的屬性，
@interface BinaryTreeNode : NSObject
// 值；當做key來用，是排序用的憑證
@property (assign, nonatomic) NSInteger value;
// 左子樹
@property (strong, nonatomic) BinaryTreeNode *leftChild;
// 右子樹
@property (strong, nonatomic) BinaryTreeNode *rightChild;
// ... 添加其他需要的屬性成員
@end
添加節(jié)點
與鏈表類似，一個根節(jié)點
*rootNode就代表一棵樹。要添加節(jié)點，就要從這個根節(jié)點*rootNode開始。采用“遞歸”的思想，就很簡單：如果節(jié)點還不存在，那么就新建節(jié)點，添加完成，這也是“遞歸”的退出條件。如果值偏小，那么就去“左子樹”；如果值偏大，那么就去“右子樹”；如果值相等，就忽略。
到了“左子樹”或者“右子樹”，重復(fù)上面的過程就可以了。這就是“遞歸”。
最后，返回根節(jié)點
*rootNode，這代表了一棵樹。
/**
* 向二叉排序樹節(jié)點添加一個節(jié)點
*
* @param rootNode 根節(jié)點
* @param value 值
*
* @return 根節(jié)點
*/
+ (BinaryTreeNode *)addNode:(BinaryTreeNode *)rootNode value:(NSInteger)value {
// 根節(jié)點不存在，創(chuàng)建節(jié)點
if (rootNode == nil) {
rootNode = [[BinaryTreeNode alloc] init];
rootNode.value = value;
NSLog(@"node:%@", @(value));
} else if (value < rootNode.value) {
NSLog(@"to left");
// 值小于根節(jié)點，則插入到左子樹；這是遞歸，左子樹將做同樣的事
rootNode.leftChild = [BinaryTree addNode:rootNode.leftChild value:value];
} else if (value > rootNode.value) {
NSLog(@"to right");
// 值大于根節(jié)點，則插入到右子樹；這是遞歸，右子樹將做同樣的事
rootNode.rightChild = [BinaryTree addNode:rootNode.rightChild value:value];
} else {
NSLog(@"二叉排序樹沒有鍵值相等的節(jié)點，值%@已存在，不能插入", @(value));
}
return rootNode;
}
創(chuàng)建二叉搜索樹
反復(fù)調(diào)用添加節(jié)點方法就可了。
/**
* 創(chuàng)建二叉排序樹
* 二叉排序樹：左節(jié)點值全部小于根節(jié)點值，右節(jié)點值全部大于根節(jié)點值
*
* @param values 數(shù)組
*
* @return 二叉樹根節(jié)點
*/
+ (BinaryTreeNode *)createTreeWithValues:(NSArray<NSNumber *> *)values {
BinaryTreeNode *rootNode = nil;
for (NSNumber *number in values) {
NSInteger value = [number integerValue];
rootNode = [BinaryTree addNode:rootNode value:value];
}
return rootNode;
}
- 測試一下，新建一個
Controller，用一個屬性持有這個二叉搜索樹。
@interface TreeViewController ()
// 二叉搜索樹的根節(jié)點，代表一棵樹
@property (strong, nonatomic) BinaryTreeNode *rootNode;
@end
輸入用一串值，得到一顆二叉搜索樹
// 創(chuàng)建樹
- (IBAction)createButtonTouched:(id)sender {
NSArray *values = @[@200, @23, @456, @89, @23, @670, @5674, @15];
self.rootNode = [BinaryTree createTreeWithValues:values];
}
用斷點，查看“鏈式”結(jié)構(gòu)，同時通過log可以看出創(chuàng)建過程。
企業(yè)微信截圖_ff493fa9-63a7-44ce-87d0-5d7ee4a0f872.png
二叉搜索樹的例子.jpg
遍歷
/**
* 先序遍歷：先訪問根，再遍歷左子樹，再遍歷右子樹。典型的遞歸思想。
*
* @param rootNode 根節(jié)點
* @param handler 訪問節(jié)點處理函數(shù)
*/
+ (void)preOrderTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^)(BinaryTreeNode *treeNode))handler {
if (rootNode) {
// 先訪問
if (handler) {
handler(rootNode);
}
// 再遍歷左右子樹
[BinaryTree preOrderTraverseTree:rootNode.leftChild handler:handler];
[BinaryTree preOrderTraverseTree:rootNode.rightChild handler:handler];
}
}
/**
* 中序遍歷
* 先遍歷左子樹，再訪問根，再遍歷右子樹
*
* @param rootNode 根節(jié)點
* @param handler 訪問節(jié)點處理函數(shù)
*/
+ (void)inOrderTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^) (BinaryTreeNode *treeNode))handler {
if (rootNode) {
// 先遍歷左子樹
[BinaryTree inOrderTraverseTree:rootNode.leftChild handler:handler];
// 訪問節(jié)點
if (handler) {
handler(rootNode);
}
// 最后遍歷右子樹
[BinaryTree inOrderTraverseTree:rootNode.rightChild handler:handler];
}
}
/**
* 后序遍歷
* 先遍歷左子樹，再遍歷右子樹，再訪問根
*
* @param rootNode 根節(jié)點
* @param handler 訪問節(jié)點處理函數(shù)
*/
+ (void)postOrderTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^)(BinaryTreeNode *treeNode))handler {
if (rootNode) {
// 先遍歷左右子樹
[BinaryTree postOrderTraverseTree:rootNode.leftChild handler:handler];
[BinaryTree postOrderTraverseTree:rootNode.rightChild handler:handler];
// 最后訪問節(jié)點
if (handler) {
handler(rootNode);
}
}
}
測試一下：
// 先序遍歷
- (IBAction)preOrderButtonTouched:(id)sender {
NSMutableArray<NSNumber *> *preArray = [NSMutableArray array];
[BinaryTree preOrderTraverseTree:self.rootNode handler:^(BinaryTreeNode * _Nonnull treeNode) {
[preArray addObject:[NSNumber numberWithInteger:treeNode.value]];
}];
NSLog(@"先序遍歷：%@", preArray);
}
// 中序遍歷
- (IBAction)inOrderButtonTouched:(id)sender {
NSMutableArray<NSNumber *> *inArray = [NSMutableArray array];
[BinaryTree inOrderTraverseTree:self.rootNode handler:^(BinaryTreeNode * _Nonnull treeNode) {
[inArray addObject:[NSNumber numberWithInteger:treeNode.value]];
}];
NSLog(@"中序遍歷：%@", inArray);
}
// 后序遍歷
- (IBAction)postOrderButtonTouched:(id)sender {
NSMutableArray<NSNumber *> *postArray = [NSMutableArray array];
[BinaryTree postOrderTraverseTree:self.rootNode handler:^(BinaryTreeNode * _Nonnull treeNode) {
[postArray addObject:[NSNumber numberWithInteger:treeNode.value]];
}];
NSLog(@"后序遍歷：%@", postArray);
}
根據(jù)二叉樹的圖，可以查看log中的遍歷順序是否符合：
企業(yè)微信截圖_aee2f449-badd-4332-a0c5-9f00bbb7b2fe.png
翻轉(zhuǎn)
/**
* 翻轉(zhuǎn)二叉樹（又叫：二叉樹的鏡像）
*
* @param rootNode 根節(jié)點
*
* @return 翻轉(zhuǎn)后的樹根節(jié)點（其實就是原二叉樹的根節(jié)點）
*/
+ (BinaryTreeNode *)invertBinaryTree:(BinaryTreeNode *)rootNode {
// 空節(jié)點
if (!rootNode) {
return nil;
}
// 沒有子節(jié)點
if (!rootNode.leftChild && !rootNode.rightChild) {
return rootNode;
}
// 左右子樹遞歸
[BinaryTree invertBinaryTree:rootNode.leftChild];
[BinaryTree invertBinaryTree:rootNode.rightChild];
// 左右節(jié)點交換
BinaryTreeNode *tempNode = rootNode.leftChild;
rootNode.leftChild = rootNode.rightChild;
rootNode.rightChild = tempNode;
return rootNode;
}
測試：將一開始創(chuàng)建的二叉搜索樹翻轉(zhuǎn)，然后畫出圖，與原圖比較
企業(yè)微信截圖_dfc9287b-de1e-43ec-bb82-51668d97a0b1.png
二叉搜索樹翻轉(zhuǎn).jpg
