排序算法

常见的排序算法

常见排序算法

性能比较

性能

直接插入排序

思路：
取数组中第i（i >= 1）个元素和第i-1个元素对比，若第i个元素小于第i-1个元素则交换i和i-1元素的位置，否则不交换。直至整个数组有序。

直接插入排序
插入排序

示例：

#pragma mark - 插入升序排序
- (void)insertionAscendingOrderSort:(NSMutableArray *)ascendingArr{
    for (int i = 1; i < ascendingArr.count; i++) {
        NSInteger temp = [ascendingArr[i] integerValue];
        for (int j = i-1; j >= 0 && temp < [ascendingArr[j] integerValue]; j--) {
            ascendingArr[j+1] = ascendingArr[j];
            ascendingArr[j] = [NSNumber numberWithInteger:temp];
        }
    }
    NSLog(@"插入升序排序结果：%@",ascendingArr);
}

希尔排序

思路：将待排序数组按照步长 gap 进行分组，然后将每组的元素利用直接插入排序的方法进行排序；每次将 gap 折半减小，循环上述操作；当 gap=1 时，利用直接插入，完成排序。

希尔排序
希尔排序

示例：

#pragma mark - 希尔排序
-(void)shellSort:(NSMutableArray *)list{
    //起始间隔值 gap 设置为总数的一半，直到 gap==1 结束
    int gap = (int)list.count/2;
    while (gap >= 1) {
        for(int i = gap ; i < [list count]; i++){
            NSInteger temp = [[list objectAtIndex:i] intValue];
            int j = i;
            while (j >= gap && temp < [[list objectAtIndex:(j - gap)] intValue]) {
                [list replaceObjectAtIndex:j withObject:[list objectAtIndex:j-gap]];
                j -= gap;
            }
            [list replaceObjectAtIndex:j withObject:[NSNumber numberWithInteger:temp]];
        }
        gap = gap / 2;
    }
    NSLog(@"希尔升序排序结果：%@", list);
}

简单选择排序

思路：比较+交换。
每次循环从待排序列中找到最小元素放在已排序列尾部，直至循环结束。

简单选择排序
选择排序

示例：

#pragma mark - 选择升序排序
- (void)ascendingOrderSortWithArray:(NSMutableArray *)ascendingArr{
    for (int i = 0; i < ascendingArr.count; i++) {
        int k = i;
        for (int j = i+1;j < ascendingArr.count; j++) {
            if ([ascendingArr[k] integerValue] > [ascendingArr[j] integerValue]) {
                k = j;
            }
        }
        [ascendingArr exchangeObjectAtIndex:i withObjectAtIndex:k];
    }
    NSLog(@"选择升序排序后结果：%@", ascendingArr);
}

堆排序

思路：堆排序就是利用堆这种数据结构特性即子结点的键值或索引总是小于（或者大于）它的父节点，所设计的一种排序算法。
它的基本思想是，将待排序的序列构成一个大顶堆。此时，整个序列的最大值就是堆顶的根节点。将堆顶元素与堆数组的末尾元素交换，此时末尾元素就是最大值。然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n-1个元素中的最大值。如此反复执行，便能得到一个有序序列了。

堆排序

示例：

#pragma mark - 堆排序
- (void)heapSort:(NSMutableArray *)list{
    NSInteger i ,size;
    size = list.count;
    //找出最大的元素放到堆顶，构建大顶堆
    for (i= list.count/2-1; i>=0; i--) {
        [self createBiggesHeap:list withSize:size beIndex:i];
    }
    while(size > 0){
        [list exchangeObjectAtIndex:size-1 withObjectAtIndex:0]; //将根(最大) 与数组最末交换
        size -- ;//树大小减小
        [self createBiggesHeap:list withSize:size beIndex:0];
    }
    NSLog(@"%@",list);
}

- (void)createBiggesHeap:(NSMutableArray *)list withSize:(NSInteger) size beIndex:(NSInteger)element{
    NSInteger lchild = element *2 + 1,rchild = lchild+1; //左右子树
    while (rchild < size) { //子树均在范围内
        if ([list[element] integerValue] >= [list[lchild] integerValue] && [list[element] integerValue] >= [list[rchild]integerValue]) return; //如果比左右子树都大，完成整理
        if ([list[lchild] integerValue] > [list[rchild] integerValue]) { //如果左边最大
            [list exchangeObjectAtIndex:element withObjectAtIndex:lchild]; //把左面的提到上面
            element = lchild; //循环时整理子树
        }else{//否则右面最大
            [list exchangeObjectAtIndex:element withObjectAtIndex:rchild];
            element = rchild;
        }
        lchild = element * 2 +1;
        rchild = lchild + 1; //重新计算子树位置
    }
    //只有左子树且子树大于自己
    if (lchild < size && [list[lchild] integerValue] > [list[element] integerValue]) {
        [list exchangeObjectAtIndex:lchild withObjectAtIndex:element];
    }
}

冒泡排序

思路：冒泡排序是一种简单的排序算法。算法思想是遍历数组，依次比较两个相邻的元素，若两者位置错误，则交换两者位置，每次遍历都会有一个元素添加到排好序列中。

冒泡排序

示例：

#pragma mark - 冒泡升序排序
- (void)bubbleAscendingOrderSortWithArray:(NSMutableArray *)ascendingArr{
    for (int i = 0; i < ascendingArr.count; i++) {
        //是否继续遍历
        BOOL isOutLoop = YES;
        for (int j = 0; j < ascendingArr.count-1-i; j++) {
            NSInteger left = [ascendingArr[j] integerValue];
            NSInteger right = [ascendingArr[j+1] integerValue];
            if (left > right) {
                [ascendingArr exchangeObjectAtIndex:j withObjectAtIndex:j+1];
                isOutLoop = NO;
            }
        }
        if(isOutLoop){break;}
    }
    NSLog(@"冒泡升序排序后结果：%@", ascendingArr);
}

快速排序

思路：选中一个基准元素，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都要比基准元素小，另外一部分的所有数据都要比基准元素大，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序（Quicksort）是对冒泡排序的一种改进。

快速排序

示例：

#pragma mark - 快速升序排序
- (void)quickAscendingOrderSort:(NSMutableArray *)arr leftIndex:(NSInteger)left rightIndex:(NSInteger)right{
    if (left < right) {
        NSInteger temp = [self getMiddleIndex:arr leftIndex:left rightIndex:right];
        /**** 递归排序 ***/
        //排序基准数左边的
        [self quickAscendingOrderSort:arr leftIndex:left rightIndex:temp-1];
        //排序基准数右边的
        [self quickAscendingOrderSort:arr leftIndex:temp+1 rightIndex:right];
    }
        NSLog(@"快速升序排序结果：%@", arr);
}

- (NSInteger)getMiddleIndex:(NSMutableArray *)arr leftIndex:(NSInteger)left rightIndex:(NSInteger)right{
    NSInteger tempValue = [arr[left] integerValue]; //记录基准数
    while (left < right) {
        /**** 首先从右边right开始查找比基准数小的值 ***/
        while (left < right && tempValue<= [arr[right] integerValue]) {//如果比基准数大，继续查找
            right--;
        }
        if (left < right) {//如果比基准数小，则将查找到的小值调换到left的位置
            arr[left] = arr[right];
        }
        /**** 当在右边查找到一个比基准数小的值时，就从left开始往后找比基准数大的值 ***/
        while (left < right && [arr[left] integerValue] <= tempValue) {
            left ++;
        }
        if (left < right) {//如果比基准数大，则将查找到的大值调换到right的位置
            arr[right] = arr[left];
        }
    }
    arr[left] = [NSNumber numberWithInteger:tempValue];//将基准数放到正确位置
    return left;
}

//调用
NSMutableArray *arr = [NSMutableArray arrayWithObjects:@29,@21,@2,@34,@3,@10,@20,@22,@11,@9,@2,@28,@45,@64,@4, nil];
[self quickAscendingOrderSort:arr leftIndex:0 rightIndex:arr.count-1];

归并排序

归并排序(Merging Sort) 就是利用归并的思想实现的排序方法。它的原理是假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或者1的有序子序列；再两两归并，如此反复，直到得到一个长度为n的有序序列为止，这种排序方法称为归并排序。

归并排序

示例：

#pragma mark - 归并升序排序
- (void)megerSortAscendingOrderSort:(NSMutableArray *)ascendingArr{
    //tempArray数组里存放ascendingArr.count个数组，每个数组包含一个元素
    NSMutableArray *tempArray = [NSMutableArray arrayWithCapacity:1];
    for (NSNumber *num in ascendingArr) {
        NSMutableArray *subArray = [NSMutableArray array];
        [subArray addObject:num];
        [tempArray addObject:subArray];
    }
    
    //开始合并为一个数组
    while (tempArray.count != 1) {
        NSInteger i = 0;
        while (i < tempArray.count - 1) {
            tempArray[i] = [self mergeArrayFirstList:tempArray[i] secondList:tempArray[i + 1]];
            [tempArray removeObjectAtIndex:i + 1];
            i++;
        }
    }
    NSLog(@"归并升序排序结果：%@", tempArray[0]);
}
- (NSArray *)mergeArrayFirstList:(NSArray *)array1 secondList:(NSArray *)array2 {
    NSMutableArray *resultArray = [NSMutableArray array];
    NSInteger firstIndex = 0, secondIndex = 0;
    while (firstIndex < array1.count && secondIndex < array2.count) {
        if ([array1[firstIndex] floatValue] < [array2[secondIndex] floatValue]) {
            [resultArray addObject:array1[firstIndex]];
            firstIndex++;
        } else {
            [resultArray addObject:array2[secondIndex]];
            secondIndex++;
        }
    }
    while (firstIndex < array1.count) {
        [resultArray addObject:array1[firstIndex]];
        firstIndex++;
    }
    while (secondIndex < array2.count) {
        [resultArray addObject:array2[secondIndex]];
        secondIndex++;
    }
    return resultArray.copy;
}

基数排序

基数排序也是非比较的排序算法，又称卡片排序；
对每一位进行排序，从最低位开始排序，复杂度为O(kn), n为数组长度，k为数组中的数的最大的位数；
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。
有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
基数排序基于分别排序，分别收集，所以是稳定的。
过程：
取得数组中的最大数，并取得位数；
arr为原始数组，从最低位开始取每个位组成radix数组；
对radix进行计数排序（利用计数排序适用于小范围数的特点）；
MSD ：从高位开始进行排序
LSD ：从低位开始进行排序

基数排序

示例：

#pragma mark - 基数排序
- (void)radixSort:(NSMutableArray *)ascendingArr{
    //创建空桶
    NSMutableArray *buckt = [self createBucket];
    //待排数组的最大数值
    NSNumber *maxnumber = [self listMaxItem:ascendingArr];
    //最大数值的数字位数
    NSInteger maxLength = numberLength(maxnumber);
    // 按照从低位到高位的顺序执行排序过程
    for (int digit = 1; digit <= maxLength; digit++) {
        // 入桶
        for (NSNumber *item in ascendingArr) {
            //确定item 归属哪个桶 以digit位数为基数
            NSInteger baseNumber = [self fetchBaseNumber:item digit:digit];
            NSMutableArray *mutArray = buckt[baseNumber];
            //将数据放入空桶上
            [mutArray addObject:item];
        }
        NSInteger index = 0;
        //出桶
        for (int i = 0; i < buckt.count; i++) {
            NSMutableArray *array = buckt[i];
            //将桶的数据放回待排数组中
            while (array.count != 0) {
                NSNumber *number = [array objectAtIndex:0];
                ascendingArr[index] = number;
                [array removeObjectAtIndex:0];
                index++;
            }
        }
    }
    NSLog(@"基数升序排序结果：%@", ascendingArr);
}
//创建空桶，每个桶里都是数组
- (NSMutableArray *)createBucket {
    NSMutableArray *bucket = [NSMutableArray array];
    for (int index = 0; index < 10; index++) {//数字0~9
        NSMutableArray *array = [NSMutableArray array];
        [bucket addObject:array];
    }
    return bucket;
}
//数据最大值
- (NSNumber *)listMaxItem:(NSArray *)list {
    NSNumber *maxNumber = list[0];
    for (NSNumber *number in list) {
        if ([maxNumber integerValue] < [number integerValue]) {
            maxNumber = number;
        }
    }
    return maxNumber;
}
//数字的位数
NSInteger numberLength(NSNumber *number) {
    NSString *string = [NSString stringWithFormat:@"%ld", (long)[number integerValue]];
    return string.length;
}
- (NSInteger)fetchBaseNumber:(NSNumber *)number digit:(NSInteger)digit {
    //digit为基数位数
    if (digit > 0 && digit <= numberLength(number)) {
        NSMutableArray *numbersArray = [NSMutableArray array];
        //number的位数确定
        NSString *string = [NSString stringWithFormat:@"%ld", [number integerValue]];
        for (int index = 0; index < numberLength(number); index++) {
            [numbersArray addObject:[string substringWithRange:NSMakeRange(index, 1)]];
        }
        //number的位数是几位数的
        NSString *str = numbersArray[numbersArray.count - digit];
        return [str integerValue];
    }
    return 0;
}