部分简单排序

调用测试

//test
    NSMutableArray *arr = [@[@"3", @"5", @"4", @"2", @"6"] mutableCopy];
//    arr = [[self insertionSortWithArray:arr] mutableCopy];
//    arr = [[self BInsertSortWithArray:arr] mutableCopy];
//    arr = [self shellSortWithArray:arr];
//    arr = [self bubbleSortWithArray:arr];
    arr = [self heapSortWithArray:arr];
    NSLog(@"result = %@", arr);

插入排序

/**
 * 方法名：insertionSort 说明：插入排序 时间复杂度O(N^2)
 * 升序
 */
- (NSMutableArray *)insertionSortWithArray:(NSMutableArray *)array {
    for (int i = 1; i < array.count; i++) {
        NSString *temp = [NSString stringWithFormat:@"%@", array[i]];
        int j = i - 1;
        while (j >= 0 && [temp compare:array[j]] == NSOrderedAscending) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = temp;
    }
    return array;
}

二分插入排序

/**
 * 方法名：BInsertSort 说明：二分插入排序 时间复杂度O(N^2) 因为插入排序的前i - 1个元素是排好序的
 * 所有将第i个元素插入到前面查到元素的时候 可以用二分查找
 * 升序
 */
- (NSMutableArray *)BInsertSortWithArray:(NSMutableArray *)array {
    for (int i = 1; i < array.count; i++) {
        int low = 0;
        NSString *temp = [NSString stringWithFormat:@"%@", array[i]];
        int high = i - 1;
        int position = 0;
        // 二分找不到时 low 的位置是大于key的最小元素，high是小于key的最大元素
        while (low <= high) {
            int mid = (low + high) / 2;
            if ([array[mid] compare:temp] == NSOrderedAscending) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
            position = high;
            for (int j = i; j > position && j > 0; j--) {
                array[j] = array[j - 1];
            }
            array[position + 1] = temp;
        }
    }
    return array;
}

希尔排序

/**
 * 方法名：shellSort 说明：希尔排序 时间复杂度(N^2) 利用增量序列 对用增量分组得到的序列进行插入排序。
 * 升序
 */
- (NSMutableArray *)shellSortWithArray:(NSMutableArray *)array {
    for (int gap = (int)array.count / 2; gap > 0; gap /= 2) {
        for (int i = 0; i < gap; i++) {
            for (int j = i + gap; j < array.count; j += gap) {
                NSString *temp = array[j];
                if ([temp compare:array[j - gap]] == NSOrderedAscending) {
                    int k = j - gap;
                    while (k >= 0 && [array[k] compare:temp] == NSOrderedDescending) {
                        array[k + gap] = array[k];
                        k -= gap;
                    }
                    array[k + gap] = temp;
                }
            }
        }
    }
    return array;
}

冒泡排序

/**
 * 方法名：bubbleSort 说明：冒泡排序 时间复杂度O(N^2)
 * 升序
 */
- (NSMutableArray *)bubbleSortWithArray:(NSMutableArray *)array {
    for (int i = 0; i < array.count; i++)
        for (int j = i + 1; j < array.count; j++) {
            if ([array[i] compare:array[j]] == NSOrderedDescending) {
                NSString *temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
    return array;
}