常用排序算法 - Objective-C

常用排序

1.冒泡排序
2.选择排序
3.快速排序
4.插入排序
5.希尔排序
6.归并排序
7.堆排序
8.桶排序

1.冒泡排序

思想

依次比较相邻的元素，如果前一个比后一个大(小)，就交换位置，把最大(小)的移动到数组待排序的最前(后)位置，循环比较直到所有元素有序。

动图效果

冒泡.gif

代码

-(void)sortBuddleArray:(NSMutableArray *)array{
    for (int i = 0; i< array.count - 1; i++) {
        for (int j = 0; j< array.count - i -1; j++) {
            NSNumber *a = array[j];
            NSNumber *b = array[j+1];
            if (a.intValue > b.intValue) {
                [array exchangeObjectAtIndex:j withObjectAtIndex:j+1];
            }
        }
    }
}

2.选择排序

思想

依次查找数组中最大(小)的元素，把最大(小)的元素移动到数组的待排序的最前(后)位置，循环比较移动直到所有元素有序。

动图效果

选择.gif

代码

-(void)sortSelectArray:(NSMutableArray *)array{
    for (int i = 0; i< array.count; i++) {
        int maxIndex = i;
        for (int j = i+1; j< array.count; j++) {
            NSNumber *maxValue = array[maxIndex];
            NSNumber *b = array[j];
            if (maxValue.longValue < b.longValue) {
                maxIndex = j;
            }
        }
        [array exchangeObjectAtIndex:i withObjectAtIndex:maxIndex];
    }
}

3.快速排序

思想

快速排序的思路是把数组元素分为以基准元素为界限的两部分，左右两边分别为大于和小于基准元素的元素，再递归分别对左右两部分未排序的元素进行排序。直到数组中所有元素都有序。

动图效果

快速.gif

代码

- (void)quickSortArray:(NSMutableArray *)array fromIndex:(NSInteger)fromIndex toIndex:(NSInteger)toIndex
{
    if (fromIndex >= toIndex) {//数组个数<= 1 直接返回
        return ;
    }
    NSInteger i = fromIndex;//起止点
    NSInteger j = toIndex;//终止点
    //比较基准数
    NSInteger target = [array[i] integerValue];
    while (i < j) {
        // 首先从右边j开始查找比基准数小的值
        while (i < j && [array[j] integerValue] >= target) {//如果比基准数大，继续查找
            j--;
        }
        //如果比基准数小，则将查找到的小值调换到i的位置
        array[i] = array[j];
        // 当在右边查找到一个比基准数小的值时，就从i开始往后找比基准数大的值
        while (i < j && [array[i] integerValue] <= target) {//如果比基准数小，继续查找
            i++;
        }
        //如果比基准数大，则将查找到的大值调换到j的位置
        array[j] = array[i];
    }
    //将基准数放到正确位置
    array[i] = @(target);
    // 按基准数分左右两部分，然后左右两边分别递归再排序
    //排序基准数左边的
    [self quickSortArray:array fromIndex:fromIndex toIndex:i - 1];
    //排序基准数右边的
    [self quickSortArray:array fromIndex:i + 1 toIndex:toIndex];
}

4.插入排序

思想

插入排序的思想就是把待排序元素依次插入到已排序元素中对应位置，直到所有元素都有序。

动图效果

插入.gif

代码

-(void)insertSortArray:(NSMutableArray *)array{
    for (long i = 0; i< array.count; i++) {
        long j = i-1;
        long target = i;
        while (j >= 0 && [array[j] longValue] > [array[target] longValue]) {
            [array exchangeObjectAtIndex:target withObjectAtIndex:j];
            target = j;
            j--;
        }
    }
}

5.希尔排序

思想

希尔排序是对插入排序的优化，看4.插入排序的动图，能够很直观的看到，如果元素位置和排序位置相反，则需要比较和移动的次数较多，希尔排序先进行几次大步调的插入排序，从而让整个数组大致有序，整体顺序接近最终顺序，然后再最后进行一次插入排序，这样能大幅降低比较和移动的次数。提升排序效率

动图效果

希尔.gif

代码

-(void)shellSortArray:(NSMutableArray *)array{
    long d = (array.count-1)/2;
    while (d>0) {
        for (long m = 0;m < d;m++) {
            for (long i = m; i < array.count; i = i+d) {
                long j = i-d;
                long target = i;
                while (j >= 0 && [array[j] longValue] > [array[target] longValue]) {
                        [array exchangeObjectAtIndex:target withObjectAtIndex:j];
                        target = j;
                    j = j - d;
                }
            }
        }
        d = d/2;
    }
}

6.归并排序

思想

归并排序思想就是递归调用，将两个已经有序的数组合并起来，如果数组无序，继续拆分，直到只剩一个元素。

动图效果

归并.gif

代码

-(NSArray *)mergeSortTotalArray:(NSArray *)array{
    long d = array.count/2;
    if (d > 0) {
        NSArray *array1 = [array subarrayWithRange:NSMakeRange(0, d)];
        NSArray *array2 = [array subarrayWithRange:NSMakeRange(d, array.count - d)];
        return [self mergeSortArray1:array1 array2:array2];
    }
    return array;
}
//归并排序
-(NSMutableArray *)mergeSortArray1:(NSArray *)array1 array2:(NSArray *)array2{
    NSArray *arr1 = [self mergeSortTotalArray:array1];
    NSArray *arr2 = [self mergeSortTotalArray:array2];
    NSMutableArray *newArray = [[NSMutableArray alloc] init];
    long i = 0;
    long j = 0;
    while (i< arr1.count && j < arr2.count) {
        if ([arr1[i] longValue] <= [arr2[j] longValue]) {
            [newArray addObject:arr1[i]];
            i++;
        }else{
            [newArray addObject:arr2[j]];
            j++;
        }
    }
    for (long m = i; m < arr1.count; m++) {
        [newArray addObject:arr1[m]];
    }
    for (long m = j; m < arr2.count; m++) {
        [newArray addObject:arr2[m]];
    }
    return newArray;
}

7.堆排序

思想

堆排序和选择排序类似，都是依次把待排序最大(小)元素放到最后面，选择排序是遍历查找最大(小)值，而堆排序是通过构造大(小)顶堆来查找最值。

动图效果

堆排序.gif

代码

/*
 * 堆排序
 */
-(void)heapSortArray:(NSMutableArray *)array{
    for (long i = 0; i< array.count; i++) {
        [self makeMaxHeap:array toIndex:array.count-i -1];
        [array exchangeObjectAtIndex:0 withObjectAtIndex:array.count-i -1];
    }
}

/*
* 构造大顶堆
*/
-(void)makeMaxHeap:(NSMutableArray *)array toIndex:(long)index{
    for (long i = (index-1)/2; i>= 0 ; i--) {
        if (2*i+1 <= index && [array[2*i+1] longValue] > [array[i] longValue] ) {
            [array exchangeObjectAtIndex:2*i+1 withObjectAtIndex:i];
        }
        if (2*i+2 <= index && [array[2*i+2] longValue] > [array[i] longValue] ) {
            [array exchangeObjectAtIndex:2*i+2 withObjectAtIndex:i];
        }
    }
}

8.桶排序

思想

桶排序的思想是，先按照最大-最小值的差定义一批桶（数组），按照值域把待排序元素放入对应的桶中，桶中元素各自排序，然后依次取出桶中的元素即可。

动图效果

桶排序.gif

代码

-(void)bucketSortArray:(NSMutableArray *)array{
    long max = [array[0] longValue];
    long min = [array[0] longValue];
    for (long i = 0; i< array.count ; i++) {
        max = [array[i] longValue] > max ? [array[i] longValue] : max;
        min = [array[i] longValue] < min ? [array[i] longValue] : min;
    }
//构造桶，d为桶的大小 值范围大小
    long dm = (max - min)%4 > 0 ? 1 : 0;
    long d = (max - min)/4 + dm;
    NSMutableArray *bucketArray = [NSMutableArray new];
    for (long i = 0; i < 5; i++) {
        NSMutableArray *arr = [NSMutableArray new];
        [bucketArray addObject:arr];
    }
//遍历待排序数组，把元素放到对应的桶中
    for (long i = 0; i < array.count; i++) {
        long arrIndex = ([array[i] longValue] - min)/d;
        NSMutableArray *arr = bucketArray[arrIndex];
        [arr addObject:array[i]];
    }
//合并取出所有桶中元素，放回元素组
    long index = 0;
    for (long i = 0; i < 5; i++) {
        NSMutableArray *arr = bucketArray[i];
        [self sortPaoArray:arr];
        for (long j = 0; j < arr.count; j++) {
            array[index] = arr[j];
            index++;
        }
    }
}

/*
 * 冒泡排序（桶中元素排序的方式随意选择都可）
 */
-(void)sortPaoArray:(NSMutableArray *)array{
    if (array.count <= 1) {
        return;
    }
    for (int i = 0; i< array.count - 1; i++) {
        for (int j = 0; j< array.count - i -1; j++) {
            NSNumber *a = array[j];
            NSNumber *b = array[j+1];
            if (a.intValue > b.intValue) {
                [array exchangeObjectAtIndex:j withObjectAtIndex:j+1];
            }
        }
    }
}