排序算法

冒泡排序

- (void)bubblingSortAlgorithm{
    for (int i = 0; i < self.array.count; i ++) {
        for (int j = i + 1; j < _array.count; j ++) {
            NSComparisonResult result = [_array[i] compare:_array[j]];
            if (result == NSOrderedDescending) {
                [self swapValueOfIndex:i index2:j];
            }
        }
    }
    NSLog(@"冒泡排序的结果是:%@",[_array valueForKeyPath:@"@unionOfObjects.self"]);
}

选择排序

- (void)chooseSortAlgorithm{
    for (int i = 0; i < self.array.count; i ++) {
        int minIndex = i;
        for (int j = i + 1; j < _array.count; j ++) {
            NSComparisonResult result = [_array[minIndex] compare:_array[j]];
            if (result == NSOrderedDescending) {
                [self swapValueOfIndex:minIndex index2:j];
                minIndex = j;
            }
        }
    }
    NSLog(@"选择排序的结果是:%@",[_array valueForKeyPath:@"@unionOfObjects.self"]);
}

插入排序

// 插入排序  想象新元素不在此位置，而是在全局位置（上帝之眼），因此老数据可以直接占据新位置
- (void)insetSort{
    for (int i = 1 ; i < self.array.count ; i ++) {
        NSNumber *insertValue = _array[i];
        int j = i - 1;
        while (j >= 0 && [_array[j] compare:insertValue] == NSOrderedDescending) {
            //如果已经排好序的序列中元素大于新元素，则将该元素往右移动一个位置
            [_array replaceObjectAtIndex:(j+1) withObject:_array[j]];
            j -- ;
        }
        [_array replaceObjectAtIndex:(j+1) withObject:insertValue];
    }
    NSLog(@"插入排序的结果是:%@",[_array valueForKeyPath:@"@unionOfObjects.self"]);
}

快速排序

- (void)quickySorti:(int)leftIndex j:(int)rightIndex withArray:(NSMutableArray *)arr{
    if (leftIndex >= rightIndex) {
        return;
    }
    int i = leftIndex,j = rightIndex;
    NSNumber *pivot = arr[i];
    while (i != j) {
        while (i < j && [arr[j] compare:pivot] == NSOrderedDescending) { // arr[j] 大
            j --;
        }
         [arr replaceObjectAtIndex:i withObject:arr[j]];
        while (i < j && [arr[i] compare:pivot] == NSOrderedAscending) {
            i ++;
        }
        [arr replaceObjectAtIndex:j withObject:arr[i]];
    }
    [arr replaceObjectAtIndex:i withObject:pivot];
    
    NSLog(@"快速排序的结果是:%@",[arr valueForKeyPath:@"@unionOfObjects.self"]);

    [self quickySorti:leftIndex j:i - 1 withArray:arr];
    [self quickySorti:i + 1 j:rightIndex withArray:arr];
}

堆排序

• 完全二叉树： 除了最后一层之外的其他每一层都被完全填充，并且所有结点都保持向左对齐。
• 满二叉树：除了叶子结点之外的每一个结点都有两个孩子，每一层(当然包含最后一层)都被完全填充。
• 完满二叉树：除了叶子结点之外的每一个结点都有两个孩子结点。

二叉树的遍历

• 前序遍历：根结点 ---> 左子树 ---> 右子树
• 中序遍历：左子树 ---> 根结点 ---> 右子树
• 后序遍历：左子树 ---> 右子树 ---> 根结点