iOS实现冒泡排序、快速排序、选择排序、希尔排序、插入排序等算法

1、冒泡排序

图解：

图片.png

/**
 冒泡排序
 */
void maoPaoPaixu(void) {
    NSMutableArray *arr = [NSMutableArray arrayWithObjects:@"17",@"29",@"35",@"14",@"40", nil];
    for (int i = 0; i < arr.count; i++) {
        for (int j = 0; j < arr.count - 1 - i; j++) {
            if ([arr[j] intValue] > [arr[j+1] intValue]) {
                int temp = [arr[j] intValue];
                arr[j] = arr[j + 1];
                arr[j+ 1] = [NSString stringWithFormat:@"%d",temp];
            }
        }
    }
    
    NSLog(@"%@",arr);
}

2、选择排序

图解：

1024555-20161126001352300-2027386210.png

/**
 选择排序
 */
void xuanzePaixu() {
    NSMutableArray *arr = [NSMutableArray arrayWithObjects:@"17",@"29",@"35",@"14",@"40", nil];
    for (int i = 0; i < arr.count - 1; i++) {
        for (int j = i + 1; j < arr.count; j++) {
            if ([arr[i] intValue] > [arr[j] intValue]) {
                int temp = [arr[j] intValue];
                arr[j] = arr[i];
                arr[i] = [NSString stringWithFormat:@"%d",temp];
            }
        }
    }
     NSLog(@"%@",arr);
}

3、快速排序

图解：

图片.png

/**
 快速排序
 */
void ksPaixu(NSMutableArray *arr,NSInteger left,NSInteger right) {
    if(left == right) return;
    NSInteger i = left;
    NSInteger j = right;
    NSInteger key = [arr[left] integerValue];
    while (i < j) {
        while (i < j && key <= [arr[j] integerValue]) {
            j--;
        }
        arr[i] = arr[j];
        while (i<j && key >= [arr[i] integerValue]) {
            i++;
        }
        arr[j] = arr[i];
    }
    arr[i] = [NSString stringWithFormat:@"%ld",(long)key];
    ksPaixu(arr, left, i-1);
    ksPaixu(arr, i+1, right);
}
void kuaisuPaixu() {
    NSMutableArray *arr = [NSMutableArray arrayWithObjects:@"17",@"29",@"35",@"14",@"40", nil];
    ksPaixu(arr, 0, arr.count-1);
    NSLog(@"%@",arr);
}

4、插入排序

图解:

图片.png

/**
 插入排序
 */
void charuPaixu() {
    NSMutableArray *arr = [NSMutableArray arrayWithObjects:@"17",@"29",@"35",@"14",@"40", nil];
    for (int i = 1; i<arr.count; i++) {
        int j = i;
        NSInteger temp = [arr[i] integerValue];
        while (j > 0 && temp < [arr[j-1] integerValue]) {
            [arr replaceObjectAtIndex:j withObject:arr[j-1]];
            j--;
        }
        [arr replaceObjectAtIndex:j withObject:[NSString stringWithFormat:@"%ld",(long)temp]];
    }
    NSLog(@"%@",arr);
}

5、希尔排序

图解:

图片.png

/**
 希尔排序
 */
void xierPaixu() {
    NSMutableArray *arr = [NSMutableArray arrayWithObjects:@"17",@"29",@"35",@"14",@"40", nil];
    int gap = arr.count / 2.0;
    while (gap >= 1) {
        for (int i = gap; i < arr.count; i++) {
            NSInteger temp = [arr[i] integerValue];
            int j = i;
            while (j >= gap && temp < [arr[j- gap] integerValue]) {
                [arr replaceObjectAtIndex:j withObject:arr[j-gap]];
                j-=gap;
            }
            [arr replaceObjectAtIndex:j withObject:[NSString stringWithFormat:@"%ld",(long)temp]];
        }
        gap = gap / 2.0;
    }
    NSLog(@"%@",arr);
}

6、二分查找

图解:

图片.png

/**
 二分查找

 @param ary
 @param findNum
 @return
 */
NSInteger efChazhao(NSArray *ary,NSInteger findNum) {
    NSInteger mid = (ary.count - 1) / 2.0;
    if (mid == 0) {
        return -1; //找不到
    }
    if (findNum == [ary[mid] integerValue]) {
        return mid;//返回所在的序列号
    }
    else if(findNum > [ary[mid] integerValue]) {
        return efChazhao([ary subarrayWithRange:NSMakeRange(mid + 1, ary.count - mid - 1)], findNum);
    }
    else {
        return efChazhao([ary subarrayWithRange:NSMakeRange(0, mid + 1)], findNum);
    }
}
void erfenChazhao() {
    //二分查找一定是有序的数组
    NSMutableArray *arr = [NSMutableArray arrayWithObjects:@"17",@"29",@"35",@"14",@"40", nil];
    NSInteger mid = efChazhao(arr,15);
    NSLog(@"%ld",(long)mid);
}