排序算法(冒泡、选择、插入、快速)

一、冒泡排序

arr[j] 和 arr[j+1] 比较，如果arr[j] > arr[j+1]则交换arr[j]、arr[j+1]的值

- (void)bubbleSortArray{

    NSMutableArray *dataArr = [[NSMutableArray alloc]initWithObjects:@(2),@(1),@(6),@(4),@(3),@(5),nil];
    
    for (NSInteger i=0; i<dataArr.count-1; i++) {
        
        for (NSInteger j=0; j<dataArr.count-1-i; j++) {
            
            if ([dataArr[j] integerValue] > [dataArr[j+1] integerValue]) {
                NSNumber *temp = dataArr[j];
                dataArr[j] = dataArr[j+1];
                dataArr[j+1] = temp;
            }
        }
    }
    
    for (NSNumber *number in dataArr) {
        NSLog(@"冒泡 number = %@",number);
    }
}

2019-01-15 16:11:51.807953+0800 Demo[8960:1072997] 冒泡 number = 1
2019-01-15 16:11:51.808144+0800 Demo[8960:1072997] 冒泡 number = 2
2019-01-15 16:11:51.808298+0800 Demo[8960:1072997] 冒泡 number = 3
2019-01-15 16:11:51.808400+0800 Demo[8960:1072997] 冒泡 number = 4
2019-01-15 16:11:51.808472+0800 Demo[8960:1072997] 冒泡 number = 5
2019-01-15 16:11:51.808531+0800 Demo[8960:1072997] 冒泡 number = 6

二、选择排序

arr[i] 和 arr[j] 比较，如果arr[i] > arr[j]则交换arr[i]、arr[j]的值。而且j从j=i+1开始。

- (void)selectSortArray{

    NSMutableArray *dataArr = [[NSMutableArray alloc]initWithObjects:@(2),@(1),@(6),@(4),@(3),@(5),nil];
    
    for (NSInteger i=0; i<dataArr.count-1; i++) {
        for (NSInteger j=i+1; j<dataArr.count; j++) {
            if ([dataArr[i] integerValue] > [dataArr[j] integerValue]) {
                NSNumber *temp = dataArr[i];
                dataArr[i] = dataArr[j];
                dataArr[j] = temp;
            }
        }
    }
    for (NSNumber *number in dataArr) {
        NSLog(@"选择 number = %@",number);
    }
}

2019-01-15 16:11:51.808697+0800 Demo[8960:1072997] 选择 number = 1
2019-01-15 16:11:51.808767+0800 Demo[8960:1072997] 选择 number = 2
2019-01-15 16:11:51.808836+0800 Demo[8960:1072997] 选择 number = 3
2019-01-15 16:11:51.808910+0800 Demo[8960:1072997] 选择 number = 4
2019-01-15 16:11:51.808977+0800 Demo[8960:1072997] 选择 number = 5
2019-01-15 16:11:51.809047+0800 Demo[8960:1072997] 选择 number = 6

三、插入排序

每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。

- (void)insertSortArray{

    NSMutableArray *dataArr = [[NSMutableArray alloc]initWithObjects:@(2),@(1),@(6),@(4),@(3),@(5),nil];
    
    for (NSInteger i=1; i<dataArr.count; i++) {
        for (NSInteger j=i; j>0 && ([dataArr[j] integerValue] < [dataArr[j-1] integerValue]) ; j--) {
            NSNumber *temp = dataArr[j];
            dataArr[j] = dataArr[j-1];
            dataArr[j-1] = temp;
        }
    }
    for (NSNumber *number in dataArr) {
        NSLog(@"插入排序 number = %@",number);
    }
}

2019-01-15 16:11:51.809183+0800 Demo[8960:1072997] 插入排序 number = 1
2019-01-15 16:11:51.809282+0800 Demo[8960:1072997] 插入排序 number = 2
2019-01-15 16:11:51.809422+0800 Demo[8960:1072997] 插入排序 number = 3
2019-01-15 16:11:51.809564+0800 Demo[8960:1072997] 插入排序 number = 4
2019-01-15 16:11:51.812314+0800 Demo[8960:1072997] 插入排序 number = 5
2019-01-15 16:11:51.812470+0800 Demo[8960:1072997] 插入排序 number = 6

四、快速排序

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

- (void)quickSortArray{
    
    NSMutableArray *dataArr = [[NSMutableArray alloc]initWithObjects:@(2),@(1),@(6),@(4),@(3),@(5),nil];
    
    [self quickSortWithArr:dataArr low:0 high:dataArr.count-1];
    
    for (NSNumber *number in dataArr) {
        NSLog(@"快速排序 number = %@",number);
    }
}

- (void)quickSortWithArr:(NSMutableArray *)arr low:(NSInteger)low high:(NSInteger)high{
    
    NSInteger pivotKey = 0;
    if (low < high) {
        
        pivotKey = [self partTionWithArr:arr low:low high:high];
        [self quickSortWithArr:arr low:low high:pivotKey-1];
        [self quickSortWithArr:arr low:pivotKey + 1 high:high];
    }
}

- (NSInteger)partTionWithArr:(NSMutableArray *)arr low:(NSInteger)low high:(NSInteger)high{
    
    NSInteger pivotValue = [arr[low] integerValue];
    
    while (low < high) {
        while ((low < high) && [arr[high] integerValue] >= pivotValue) {
            high--;
        }
        arr[low] = arr[high];
        while (low < high && [arr[low] integerValue] <= pivotValue) {
            low++;
        }
        arr[high] = arr[low];
    }
    
    arr[low] = @(pivotValue);
    return low;
}

2019-01-15 16:11:51.812618+0800 Demo[8960:1072997] 快速排序 number = 1
2019-01-15 16:11:51.812702+0800 Demo[8960:1072997] 快速排序 number = 2
2019-01-15 16:11:51.812782+0800 Demo[8960:1072997] 快速排序 number = 3
2019-01-15 16:11:51.812857+0800 Demo[8960:1072997] 快速排序 number = 4
2019-01-15 16:11:51.812919+0800 Demo[8960:1072997] 快速排序 number = 5
2019-01-15 16:11:51.812992+0800 Demo[8960:1072997] 快速排序 number = 6