/*
桶排序思想：假设有11个桶（分别对应0到10分），每出现一个分数，对应的在桶里放一个小旗子，最后按顺序数桶里的小旗子
时间复杂度：m+n, m 为桶的个数，n为待排序的个数
*/

#pragma mark - - 桶排序
/*
   假设：一次考试成绩如下：5，3，2，3，8，（满分为10），从大到小排列？
 */

-(void)TSort {
    
    NSMutableArray *sortArray = [[NSMutableArray alloc] init];
    // 待排序 数组
    NSArray *a = @[@5,@3,@2,@3,@8];
    // 初始化 桶数组 初始值为0
    NSMutableArray *t =[[NSMutableArray alloc] initWithCapacity:11];
    for (int i=0; i<11; i++) {
        [t addObject:[NSNumber numberWithInteger:0]];
    }
    
    // 放入旗子 每出现一次 +1；
    for (NSInteger i=0; i<a.count; i++) {
        NSInteger tem = [t[[a[i] intValue]] integerValue];
        tem++;
        t[[a[i] intValue]] = [NSNumber numberWithInteger:tem];
        
    }
    
    // 从大到小 排列 先数编号最大的桶
    for (NSInteger i=t.count-1; i<t.count; i--) { // 依次判断
        for (NSInteger j=1; j<=[t[i] integerValue]; j++) { // 出现几次打印几次
            NSLog(@"桶排序:%ld",i);
            [sortArray addObject:[NSNumber numberWithInteger:i]];
        }
    }
    

}

/*
冒泡排序思想：每次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来，每一次排序都将一个数的归位，如果从大到小排列，那么第一次排序，将最小的数归位到末位，第二次排序，将第二小的数归位到倒数第二位... 第一次需要交换n-1次 第二次需要交换n-2次
时间复杂度：n^2 ,n为待排序的个数
*/

#pragma mark - - 冒泡排序
/*
 假设：一次考试成绩如下：5，3，2，3，8，（满分为10），从大到小排列？
 */


-(void)MSort {
 
    // 待排序 数组
    NSMutableArray *a = [NSMutableArray arrayWithArray:@[@"5",@"3",@"2",@"3",@"8"]];
    for (int i=0; i<a.count; i++) {
        for (int j=0; j<a.count-1-i; j++) {
            if ([a[j] integerValue]<[a[j+1] integerValue]) {
                NSString *tem = a[j];
                a[j] = a[j+1];
                a[j+1] = tem;
            }
            
        }
    }
    
    for (NSInteger i=0; i<a.count; i++) {
        NSLog(@"冒泡排序:%ld",[a[i] integerValue]);
    }
    
}

/*
快速排序思想：随意找一个基准数，以这个基准数作参照数，使基准数左边都比基准数小，右边都比基准数大。假定有两个哨兵i，j，哨兵j从右向左找一个小于基准数的数，停下，哨兵i再从左向右找一个大于基准数的数，停下，交换这两个数，继续，直到哨兵i和哨兵j相遇，则将基准数与相遇位置的数交换，这样基准数的左边都小于基准数，基准数的右边都大于基准数，得到两个小序列，这两个序列继续上述操作
时间复杂度：最大为n^2 平均为nlogn n为待排序的个数
*/

#pragma mark - -  快速排序
/*
 假设：一次考试成绩如下：5，3，2，3，8，（满分为10），从小到大排列？
 */

-(void)QSort {
    // 待排序 数组
    NSMutableArray *a = [NSMutableArray arrayWithArray:@[@"5",@"3",@"2",@"3",@"8",@"6",@"9",@"7",@"10"]];
    
    [self quicksortWithLeft:0 Right:a.count-1 WithArray:a];
    
    for (NSInteger i=0; i<a.count; i++) {
        NSLog(@"快速排序:%ld",[a[i] integerValue]);
    }
   
    
    
    
    
}

-(void)quicksortWithLeft:(NSInteger)left Right:(NSInteger)right WithArray:(NSMutableArray *)a{
    if (left>right) {
        return ;
    }
    
    NSInteger i=left;
    NSInteger j=right;
    NSString * tem = a[left];
    
    while (i!=j) {
        while ([a[j] integerValue]>=[tem integerValue]&&i<j) {
            // 找到小于基准数 停下
            j--;
        }
        
        while ([a[i] integerValue]<=[tem integerValue]&&i<j) {
            // 找到大于基准数 停下
            i++;
        }
        //如果i和j 没有相遇 交换数据
        if (i<j) {
            NSString * t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
        
    }
    
    // i和j相遇 出while循环
    // 归位基准数 交换 基准数 和 i j相遇处的数
    a[left] = a[i];
    a[i] = tem;
    // 此时 获得两个子序列，左边都比基准数小 右边都比基准数大 处理两个子序列 分别归位基准数
    [self quicksortWithLeft:left Right:i-1 WithArray:a];
    [self quicksortWithLeft:i+1 Right:right WithArray:a];
    
}

#pragma mark - -  排序&&去重
/*
 假设：100，15，60，45，20，15，80，40，45，70 从小到大排序 并去重
 */
// 桶排序 去重
-(void)TCSort {
    NSMutableArray * a = [NSMutableArray arrayWithArray:@[@100,@15,@60,@45,@20,@15,@80,@40,@45,@70]];
    NSMutableArray * b =[[NSMutableArray alloc] initWithCapacity:100+1];
    for (NSInteger i =0; i<100+1; i++) {
        b[i] = [NSNumber numberWithInt:0];
    }
    
    for (NSInteger i=0; i<a.count; i++) {
        b[[a[i] integerValue]] = [NSNumber numberWithInteger:1];
    }
    
    for (NSInteger i=0; i<b.count; i++) {
        if ([b[i] integerValue] == 1) {
            NSLog(@"桶排序 去重：%ld",i);
        }
    }
    
    
}

// 冒泡排序 去重
-(void)MCSort {
   NSMutableArray * a = [NSMutableArray arrayWithArray:@[@100,@15,@60,@45,@20,@15,@80,@40,@45,@70]];
    // 冒泡排序
    for (NSInteger i=0; i<a.count; i++) {
        for (NSInteger j=0; j<a.count-1-i; j++) {
            if (a[j]>a[j+1]) {
                NSNumber *tem = a[j];
                a[j] = a[j+1];
                a[j+1] = tem;
            }
            
        }
    }
    
    // 去重
    NSLog(@"冒泡排序 去重 %ld",[a[0] integerValue]);
    for (NSInteger i=1; i<a.count; i++) {
        if (a[i]!=a[i-1]) {
            NSLog(@"冒泡排序 去重 %ld",[a[i] integerValue]);
        }
    }
}

// 快速排序 去重 从大到小 基准数 左侧大 右侧小
-(void)CQuickSort {
    NSMutableArray * a = [NSMutableArray arrayWithArray:@[@100,@15,@60,@45,@20,@15,@80,@40,@45,@70]];
    [self DQuickSortWithLeft:0 Right:a.count-1 andArray:a];
    
    NSLog(@"快速排序 倒序去重:%ld",[a[0] integerValue]);
    for (NSInteger i=1; i<a.count; i++) {
        if (a[i]!=a[i-1]) {
            NSLog(@"快速排序 倒序去重:%ld",[a[i] integerValue]);
        }
    }
}

-(void)DQuickSortWithLeft:(NSInteger)left Right:(NSInteger)right andArray:(NSMutableArray *)a {
    // 跳出递归 结束循环
    if(left > right) {
        return ;
    }
    
    NSInteger i = left;
    NSInteger j = right ;
    NSNumber *tem = a[right];
    
    while (i!=j) {
        while ([a[i] integerValue]>=[tem integerValue]&&i<j) {
            i++;
        }
        while ([a[j] integerValue]<=[tem integerValue]&&i<j) {
            j--;
        }
        
        if (i<j) {
            // 交换
            NSNumber *t = a[j];
            a[j] =a[i];
            a[i] =t;
        }
        
    }
    
    a[right]= a[i];
    a[i] =tem;
    
    [self DQuickSortWithLeft:left Right:i-1 andArray:a];
    [self DQuickSortWithLeft:i+1 Right:right andArray:a];
    
}