/*
桶排序思想：假设有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];
}
