排序算法

#import <Foundation/Foundation.h>

NS_ASSUME_NONNULL_BEGIN

@interface NSArray (Sort)

/**
 * 插入排序
 *
 * 是否基于比较：是
 * 是否稳定排序：是
 * 是否原地操作：是
 * 时间复杂度为O(n2)，比较高，适合小规模数据的排序。
 * 适合排序数据类型：NSString,NSNumber,CGFloat,NSInteger,long
 **/
- (void)insertionSortArray:(NSMutableArray *)array;

/**
 * 选择排序
 *
 * 是否基于比较：是
 * 是否稳定排序：否
 * 是否原地操作：是
 * 时间复杂度为O(n2)，比较高，适合小规模数据的排序。
 * 适合排序数据类型：NSString,NSNumber,CGFloat,NSInteger,long
 **/
- (void)selectSortArray:(NSMutableArray *)array;

/**
 * 冒泡排序
 *
 * 是否基于比较：是
 * 是否稳定排序：是
 * 是否原地操作：是
 * 时间复杂度为O(n2)，比较高，适合小规模数据的排序。
 * 适合排序数据类型：NSString,NSNumber,CGFloat,NSInteger,long
 **/
- (void)bubbleSortArray:(NSMutableArray *)array;

/**
 * 快速排序
 *
 * 是否基于比较：是
 * 是否稳定排序：否
 * 是否原地操作：是
 * 时间复杂度为O(nlogn)，因此大规模表现良好。
 * 适合排序数据类型：NSString,NSNumber,CGFloat,NSInteger,long
 **/
- (void)quickSortArray:(NSMutableArray *)array withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex;

/**
 * 希尔排序
 *
 * 是否基于比较：是
 * 是否稳定排序：是
 * 是否原地操作：是
 * 时间复杂度为O(n(1.3—2))，因此中等大小规模表现良好。
 * 适合排序数据类型：NSString,NSNumber,CGFloat,NSInteger,long
 **/
- (void)shellSortArray:(NSMutableArray *)array;

//堆排序
- (void)heapSortArray:(NSMutableArray *)array;

/**
 * 归并排序
 *
 * 是否基于比较：是
 * 是否稳定排序：是
 * 是否原地操作：否
 * 时间复杂度为O(nlogn)，因此大规模表现良好。
 * 适合排序数据类型：NSString,NSNumber,CGFloat,NSInteger,long
 **/
- (void)megerSortAscendingOrderSort:(NSMutableArray *)ascendingArray;

/**
 * 基数排序
 *
 * 是否基于比较：否（线性排序）
 * 是否稳定排序：是
 * 是否原地操作：否
 * 时间复杂度为更低的O(n)，但是对要排序的数据要求很苛刻，基数排序要求数据可以划分成高低位，位之间有递进关系。比较两个数，我们只需要比较高位，高位相同的再比较低位。而且每一-位的数据范围不能太大。
 * 适合排序数据类型：NSString,NSNumber,NSInteger,long
 **/
- (void)radixSortArray:(NSMutableArray *)array;



/**
 * 二分查找（循环）
 **/
- (NSInteger)binarySearch:(NSArray *)source target:(NSInteger)target;

@end

NS_ASSUME_NONNULL_END

#import "NSArray+Sort.h"

@implementation NSArray (Sort)

#pragma mark 插入排序
/**
 * 插入排序
 *
 * 是否基于比较：是
 * 是否稳定排序：是
 * 是否原地操作：是
 * 时间复杂度为O(n2)，比较高，适合小规模数据的排序。
 * 适合排序数据类型：NSString,NSNumber,CGFloat,NSInteger,long
 **/
- (void)insertionSortArray:(NSMutableArray *)array {
    for (int i = 1; i < array.count; i++) {
        int j = i;  /* j是一个坑， 确定坑的位置，再把数从坑里取出来，注意顺序*/
        id temp = array[i]; /* temp 是从坑里取数*/
        if ([array[i] intValue] < [array[i-1] intValue]) {  /* j > 0 防止越界。写&&前面效率更高*/
            while (j > 0 && [temp intValue] < [array[j-1] intValue]) {
                array[j] = array[j-1];
                j--;
            }
            array[j] = temp;
        }
    }
    NSLog(@"%@",array);
}

#pragma mark 选择排序 --每次把最大的选出来 放到前面，然后依次类推
/**
 * 选择排序
 *
 * 是否基于比较：是
 * 是否稳定排序：否
 * 是否原地操作：是
 * 时间复杂度为O(n2)，比较高，适合小规模数据的排序。
 * 适合排序数据类型：NSString,NSNumber,CGFloat,NSInteger,long
 **/
- (void)selectSortArray:(NSMutableArray *)array {
    int index = 0;//记录找到的关键字下标
    for (int i = 0; i < array.count - 1; i++) {
        index = i;
        for (int j = i + 1; j < array.count; j++) {
            if ([array[index] integerValue] < [array[j]integerValue]) {
                //如果有比当前index值大的值,则记录次下标
                index = j;//记录最大值(最小值)的下标
            }
        }
        if (i != index) {  //若index不等于i，说明找到最大值，交换
            [array exchangeObjectAtIndex:i withObjectAtIndex:index];
        }
    }
    NSLog(@"%@",array);
}

#pragma mark 冒泡排序
/**
 * 冒泡排序
 *
 * 是否基于比较：是
 * 是否稳定排序：是
 * 是否原地操作：是
 * 时间复杂度为O(n2)，比较高，适合小规模数据的排序。
 * 适合排序数据类型：NSString,NSNumber,CGFloat,NSInteger,long
 **/
- (void)bubbleSortArray:(NSMutableArray *)array {
    for (NSInteger i = 0; i < array.count-1; i++) {
        for (NSInteger j = 0; j < array.count-1-i; j++) {
            NSInteger left = [array[j] integerValue];
            NSInteger right = [array[j+1] integerValue];
            if (left > right) {
                [array exchangeObjectAtIndex:j withObjectAtIndex:j+1];
            }
        }
    }
    NSLog(@"%@",array);
}

#pragma mark 快速排序
//1. 算法思想
//快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
//2. 实现原理
//2.1、设置两个变量 low、high，排序开始时：low=0，high=size-1。
//2.2、整个数组找基准正确位置，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面
//默认数组的第一个数为基准数据，赋值给key，即key=array[low]。
//因为默认数组的第一个数为基准，所以从后面开始向前搜索（high–），找到第一个小于key的array[high]，就将 array[high] 赋给 array[low]，即 array[low] = array[high]。（循环条件是 array[high] >= key；结束时 array[high] < key）
//此时从前面开始向后搜索（low++），找到第一个大于key的array[low]，就将 array[low] 赋给 array[high]，即 array[high] = array[low]。（循环条件是 array[low] <= key；结束时 array[low] > key）
//循环 2-3 步骤，直到 low=high，该位置就是基准位置。
//把基准数据赋给当前位置。
//2.3、第一趟找到的基准位置，作为下一趟的分界点。
//2.4、递归调用（recursive）分界点前和分界点后的子数组排序，重复2.2、2.3、2.4的步骤。
//2.5、最终就会得到排序好的数组。
/**
 * 快速排序
 *
 * 是否基于比较：是
 * 是否稳定排序：否
 * 是否原地操作：是
 * 时间复杂度为O(nlogn)，因此大规模表现良好。
 * 适合排序数据类型：NSString,NSNumber,CGFloat,NSInteger,long
 **/
- (void)quickSortArray:(NSMutableArray *)array withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex {
    if (leftIndex >= rightIndex) {//如果数组长度为0或1时返回
        return ;
    }
    NSInteger i = leftIndex;
    NSInteger j = rightIndex;
    //记录比较基准数
    NSInteger key = [array[i] integerValue];
    
    while (i < j) {
        /**** 首先从右边j开始查找比基准数小的值 ***/
        while (i < j && [array[j] integerValue] >= key) {//如果比基准数大，继续查找
            j--;
        }
        //如果比基准数小，则将查找到的小值调换到i的位置
        array[i] = array[j];
        
        /**** 当在右边查找到一个比基准数小的值时，就从i开始往后找比基准数大的值 ***/
        while (i < j && [array[i] integerValue] <= key) {//如果比基准数小，继续查找
            i++;
        }
        //如果比基准数大，则将查找到的大值调换到j的位置
        array[j] = array[i];
    }
    
    //将基准数放到正确位置
    array[i] = @(key);
    
    /**** 递归排序 ***/
    //排序基准数左边的
    [self quickSortArray:array withLeftIndex:leftIndex andRightIndex:i - 1];
    //排序基准数右边的
    [self quickSortArray:array withLeftIndex:i + 1 andRightIndex:rightIndex];
    
    NSLog(@"快速排序 %@",array);                    
}

#pragma mark 希尔排序
/**
 * 希尔排序
 *
 * 是否基于比较：是
 * 是否稳定排序：是
 * 是否原地操作：是
 * 时间复杂度为O(n(1.3—2))，因此中等大小规模表现良好。
 * 适合排序数据类型：NSString,NSNumber,CGFloat,NSInteger,long
 **/
- (void)shellSortArray:(NSMutableArray *)array {//起始间隔值gap设置为总数的一半，直到gap==1结束
    int gap = (int)array.count / 2;
    while (gap >= 1) {
        for(int i = gap; i < [array count]; i++){
            NSInteger temp = [[array objectAtIndex:i] intValue];
            int j = i;
            while (j >= gap && temp < [[array objectAtIndex:(j - gap)] intValue]) {
                [array replaceObjectAtIndex:j withObject:[array objectAtIndex:j-gap]];
                j -= gap;
            }
            [array replaceObjectAtIndex:j withObject:[NSNumber numberWithInteger:temp]];
        }
        gap = gap / 2;
    }
    NSLog(@"希尔排序 %@",array);
}

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

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

//==========================归并排序============================
#pragma mark 归并排序
//时间复杂度为O(nlogn)
//（1）“分解”——将序列每次折半划分
//（2）“合并”——将划分后的序列段两两合并后排序
/**
 * 归并排序
 *
 * 是否基于比较：是
 * 是否稳定排序：是
 * 是否原地操作：否
 * 时间复杂度为O(nlogn)，因此大规模表现良好。
 * 适合排序数据类型：NSString,NSNumber,CGFloat,NSInteger,long
 **/
- (void)megerSortAscendingOrderSort:(NSMutableArray *)ascendingArray {
    // 排序数组
    NSMutableArray *tempArray = [NSMutableArray arrayWithCapacity:1];
    // 第一趟排序是的子数组个数为ascendingArr.count
    for (NSNumber *num in ascendingArray) {
        NSMutableArray *subArray = [NSMutableArray array];
        [subArray addObject:num];
        [tempArray addObject:subArray];
    }
    /**
     分解操作 每一次归并操作
     当数组个数为偶数时tempArray.count/2; 当数组个数为奇数时tempArray.count/2+1; 当tempArray.count == 1时，归并排序完成
     */
    while (tempArray.count != 1) {
        NSInteger i = 0;
        // 当数组个数为偶数时 进行合并操作， 当数组个数为奇数时，最后一位轮空
        while (i < tempArray.count - 1) {
            // 将i 与i+1 进行合并操作 将合并结果放入i位置上 将i+1位置上的元素删除
            tempArray[i] = [self mergeArrayFirstList:tempArray[i] secondList:tempArray[i + 1]];
            [tempArray removeObjectAtIndex:i + 1];
            // i++ 继续下一循环的合并操作
            i++;
        }
    }
    NSLog(@"归并升序排序结果：%@", tempArray[0]);
}

// 合并
- (NSArray *)mergeArrayFirstList:(NSArray *)array1 secondList:(NSArray *)array2 {
    // 合并序列数组
    NSMutableArray *resultArray = [NSMutableArray array];
    // firstIndex是第一段序列的下标 secondIndex是第二段序列的下标
    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;
}
//==========================归并排序============================


//==========================基数排序============================
#pragma mark --- 基数排序
/**
 * 基数排序
 *
 * 是否基于比较：否（线性排序）
 * 是否稳定排序：是
 * 是否原地操作：否
 * 时间复杂度为更低的O(n)，但是对要排序的数据要求很苛刻，基数排序要求数据可以划分成高低位，位之间有递进关系。比较两个数，我们只需要比较高位，高位相同的再比较低位。而且每一-位的数据范围不能太大。
 * 适合排序数据类型：NSString,NSNumber,NSInteger,long
 **/
- (void)radixSortArray:(NSMutableArray *)array {
    NSMutableArray *bucket = [self createBucket];
    double maxNumber = [self listMaxItem:array];
    NSInteger maxLength = [self numberLength:maxNumber];
    
    for (NSInteger digit = 1; digit <= maxLength; digit++)  {
        //入桶
        for (NSNumber *number in array) {
            NSInteger baseNumber = [self fetchBaseNumber:number.doubleValue digit:digit];
            NSMutableArray *subArray = bucket[baseNumber];
            [subArray addObject:number];
        }
        
        //出桶
        NSInteger index = 0;
        
        for (NSInteger i = 0; i < bucket.count; i++) {
            NSMutableArray *subArray = bucket[i];
            while (subArray.count > 0) {
                NSNumber *item = subArray[0];
                [array replaceObjectAtIndex:index withObject:item];
                [subArray removeObjectAtIndex:0];
                index++;
            }
        }
    }
    NSLog(@"基数排序 %@",array);
}

//创建10个空桶
- (NSMutableArray *)createBucket {
    NSMutableArray *bucketArray = [NSMutableArray array];
    for (NSInteger i = 0; i < 10; i++) {
        [bucketArray addObject:[NSMutableArray array]];
    }
    return bucketArray;
}

//计算无序序列中最大的数值
- (double)listMaxItem:(NSArray *)array {
    double maxNumber = [array[0] doubleValue];
    for (NSNumber *number in array) {
        if (maxNumber < number.doubleValue) {
            maxNumber = number.doubleValue;
        }
    }
    return maxNumber;
}

//获取数字的长度
- (NSInteger)numberLength:(double)number {
    NSString *numberStr = [NSString stringWithFormat:@"%f",number];
    return numberStr.length;
}

//获取数值中特定位数的值
- (NSInteger)fetchBaseNumber:(double)number digit:(NSInteger)digit {
    if (digit > 0 && digit <= [self numberLength:number]) {
        NSMutableArray *numbersArray = [NSMutableArray array];
        NSString *numberStr = [NSString stringWithFormat:@"%f",number];
        for (NSInteger i = 0; i < numberStr.length; i++) {
            NSString *subStr = [numberStr substringWithRange:NSMakeRange(i, 1)];
            [numbersArray addObject:[NSNumber numberWithInteger:subStr.doubleValue]];
        }
        return [numbersArray[numbersArray.count - digit] integerValue];
    }
    return 0;
}
//==========================基数排序============================






/**
 * 二分查找（循环）
 **/
- (NSInteger)binarySearch:(NSArray *)source target:(NSInteger)target {
    if (source.count == 0) {
        return -1;
    }
    NSInteger start = 0;
    NSInteger end = source.count - 1;
    NSInteger mid = 0;
    
    while (start + 1 < end) {
        mid = start + (end - start) / 2;
        if ([source[mid] integerValue] == target) { // 相邻就退出
            return mid;
        } else if ([source[mid] integerValue] < target) {
            start = mid;
        } else {
            end = mid;
        }
    }
    
    if ([source[start] integerValue] == target) {
        return start;
    }
    if ([source[end] integerValue] == target) {
        return end;
    }
    
    return -1;
}

@end