排序算法

1、冒泡排序

//两两比较相邻的关键字，如果反序则交换，直到没有反序的记录为止
- (void)bubbleSort:(NSMutableArray *)array {
    for (int i = 0; i < array.count; i++) {
        for (int j = 0; j < array.count - i - 1; j++) {
            if ([array[j] intValue] > [array[j+1] intValue]) {
                int tmp = [array[j] intValue];
                array[j] = array[j+1];
                array[j+1] = [NSString stringWithFormat:@"%d", tmp];
            }
        }
    }
}

2、选择排序

//通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i(1≤i≤n)个记录交换之
- (void)simpleSelectionSortSort:(NSMutableArray *)array {
    for (int i = 0; i < array.count; i++) {
        for (int j = i+1; j < array.count; j++) {
            if ([array[i] intValue] > [array[j] intValue]) {
                int tmp = [array[i] intValue];
                array[i] = array[j];
                array[j] = [NSString stringWithFormat:@"%d", tmp];
            }
        }
    }
}

3、插入排序

//从第二个开始，取出该位置的值为临时值temp，位置为j，此时j的位置为空，叫做坑，然后temp依次往前比较，直到找到比temp小，把temp插入该的位置，完成一次循环
- (void)straightInsertionSort:(NSMutableArray *)array{
    for (int i = 1; i < array.count; i++) {
        int tmp = [array[i] intValue];
        int j = i;
        while (j > 0 && tmp < [array[j -1] intValue]) {
            array[j] = array[j -1];
            j--;
        }
        array[j] = [NSString stringWithFormat:@"%d", tmp];
    }
}

4、希尔排序

//希尔排序
- (void)shellSort:(NSMutableArray *)array {
    int gap = (int)array.count / 2;
    while (gap >= 1) {
        for (int i = gap; i < array.count; i++) {
            int tmp = [array[i] intValue];
            int j = i;
            while (j >= gap && tmp < [array[j-gap] intValue]) {
                array[j] = array[j-gap];
                j -= gap;
            }
            array[j] = [NSString stringWithFormat:@"%d", tmp];
        }
        gap = gap/2;
    }
}

5、堆排序

//堆排序
- (void)heapSort:(NSMutableArray *)array {
    NSInteger size = array.count;
    //将现在的待排序序列构建成一个大顶堆
    for (NSInteger i = size/2; i >= 0; i--) {
        [self createBiggerHeap:array withSize:size beIndex:i];
    }
    //逐步将每个最大值的根节点与末尾元素交换，并再调整其成为一个大顶堆
    while (size > 0) {
        [array exchangeObjectAtIndex:size - 1 withObjectAtIndex:0];
        size--;
        [self createBiggerHeap:array withSize:size beIndex:0];
    }
}
- (void)createBiggerHeap:(NSMutableArray *)array withSize:(NSInteger)size beIndex:(NSInteger)index {
    NSInteger leftChild = index*2 + 1;
    NSInteger rightChild = leftChild + 1;
    while (rightChild < size) {
        if ([array[index] intValue] >= [array[leftChild] intValue] && [array[index] intValue] >= [array[rightChild] intValue]) {
            return;
        }
        if ([array[leftChild] intValue] > [array[rightChild] intValue]) {
            [array exchangeObjectAtIndex:index withObjectAtIndex:leftChild];
            index = leftChild;
        } else {
            [array exchangeObjectAtIndex:index withObjectAtIndex:rightChild];
            index = rightChild;
        }
        leftChild = index*2 + 1;
        rightChild = leftChild + 1;
    }
    
    //只有左子树且左子树大于自己
    if (leftChild < size && [array[leftChild] intValue] > [array[index] intValue]) {
        [array exchangeObjectAtIndex:leftChild withObjectAtIndex:index];
    }
}

6、归并排序

- (NSArray *)mergeSort:(NSArray *)array {
    NSMutableArray *resultArr = [NSMutableArray array];
    for (NSNumber *num in array) {
        NSMutableArray *subArr = [NSMutableArray array];
        [subArr addObject:num];
        [resultArr addObject:subArr];
    }
    while (resultArr.count > 1) {
        NSInteger i = 0;
        while (i < resultArr.count -1) {
            resultArr[i] = [self mergeFirstArr:resultArr[i] withSecondArr:resultArr[i+1]];
            [resultArr removeObjectAtIndex:i+1];
            i++;
        }
    }
    return resultArr;
}

- (NSArray *)mergeFirstArr:(NSArray *)firstArr withSecondArr:(NSArray *)secondArr {
    NSMutableArray *resultArr = [NSMutableArray array];
    NSInteger firstIndex = 0;
    NSInteger secondIndex = 0;
    while (firstIndex < firstArr.count && secondIndex < secondArr.count) {
        if ([firstArr[firstIndex] integerValue] < [secondArr[secondIndex] integerValue]) {
            [resultArr addObject:firstArr[firstIndex]];
            firstIndex++;
        } else {
            [resultArr addObject:secondArr[secondIndex]];
            secondIndex++;
        }
    }
    while (firstIndex < firstArr.count) {
        [resultArr addObject:firstArr[firstIndex]];
        firstIndex++;
    }
    while (secondIndex < secondArr.count) {
        [resultArr addObject:secondArr[secondIndex]];
        secondIndex++;
    }
    return resultArr;
}

7、快速排序

//数组选第一个数，把比数小的放到数的左边，比数大的放到右边，重复操作
- (void)quickSortArray:(NSMutableArray *)array withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex {
    if (leftIndex >= rightIndex) {
        return;
    }
    NSInteger i = leftIndex;
    NSInteger j = rightIndex;
    NSInteger key = [array[i] integerValue];
    while (i < j) {
        while (i < j && [array[j] integerValue] >= key) {
            j--;
        }
        array[i] = array[j];
        while (i < j && [array[i] integerValue] <= key) {
            i++;
        }
        array[j] = array[i];
    }
    array[i] = [NSString stringWithFormat:@"%ld", (long)key];
    [self quickSortArray:array withLeftIndex:leftIndex andRightIndex:i-1];
    [self quickSortArray:array withLeftIndex:i+1 andRightIndex:rightIndex];
}