大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
NSStringCompareOptions comparisonOptions = NSCaseInsensitiveSearch | NSNumericSearch | NSWidthInsensitiveSearch | NSForcedOrderingSearch;
创新互联专业为企业提供眉山网站建设、眉山做网站、眉山网站设计、眉山网站制作等企业网站建设、网页设计与制作、眉山企业网站模板建站服务,十多年眉山做网站经验,不只是建网站,更提供有价值的思路和整体网络服务。
NSComparator temSortFirst = ^(NSString *obj1, NSString *obj2){
//#warning 这里是处理比较逻辑。下面的把字符串分开。处理结果是:按分开后的结果比较。把分开前的字符串按比较结果排序
obj1 = [obj1 componentsSeparatedByString:@"/"].lastObject;
obj2 = [obj2 componentsSeparatedByString:@"/"].lastObject;
NSRange range = NSMakeRange(0, obj1.length);
// obj1在前,升序;obj2在前,降序
return [obj2 compare:obj1 options:comparisonOptions range:range];
};
NSArray *resultArrayFirst = [mutableArray sortedArrayUsingComparator:temSortFirst];
// NSLog(@"%@", resultArrayFirst);
#warning 再排序
NSComparator temSortSecond = ^(NSString *obj1, NSString *obj2) {
NSRange range = NSMakeRange(0, obj1.length);
obj1 = [obj1 componentsSeparatedByString:@"/"].lastObject;
obj2 = [obj2 componentsSeparatedByString:@"/"].lastObject;
obj1 = [[obj1 componentsSeparatedByString:@"."].firstObject componentsSeparatedByString:@"_"].firstObject;
obj2 = [[obj2 componentsSeparatedByString:@"."].firstObject componentsSeparatedByString:@"_"].firstObject;
if (obj1 == obj2) {
return [obj1 compare:obj2 options:comparisonOptions range:range];
} else {
return [obj2 compare:obj1 options:comparisonOptions range:range];
}
};
_resultArraySecond = (NSMutableArray *)[resultArrayFirst sortedArrayUsingComparator:temSortSecond];
// NSLog(@"%@", resultArraySecond);
/*
////测试合并成一处⚠️结果无效。
// NSStringCompareOptions comparisonOptions = NSCaseInsensitiveSearch | NSNumericSearch | NSWidthInsensitiveSearch | NSForcedOrderingSearch;
// NSComparator temSort = ^(NSString *obj1, NSString *obj2) {
// NSRange range = NSMakeRange(0, obj1.length);
// obj1 = [obj1 componentsSeparatedByString:@"/"].lastObject;
// obj2 = [obj2 componentsSeparatedByString:@"/"].lastObject;
// obj1 = [[obj1 componentsSeparatedByString:@"."].firstObject componentsSeparatedByString:@"_"].firstObject;
// obj2 = [[obj2 componentsSeparatedByString:@"."].firstObject componentsSeparatedByString:@"_"].firstObject;;
//
// if (obj1 == obj2) {
// return [obj1 compare:obj2 options:comparisonOptions range:range];
// }
//// else if (obj3 obj4) {
//// return [obj2 compare:obj1 options:comparisonOptions range:range];
//// }
// else {
//
// return [obj2 compare:obj1 options:comparisonOptions range:range];
// }
// };
// NSArray *resultArray = [temDataArr sortedArrayUsingComparator:temSort];
// NSLog(@"%@", resultArray);
*/
时间复杂度: O(n²)
稳定性:不稳定
假设序列有 n个元素 , n1 ,根据算法步骤,第1轮需在n个元素中遍历n次查找到最小的元素,第2轮需在剩余的(n-1)个元素中遍历(n-1)次找到最小的元素,… 第n-1轮需在剩余的2个元素中找到最小的元素,第n轮剩余1个元素放在已排序元素的末尾。
函数表达式为:
f(n) = n+(n-1)+…+2+1
f(n) = (n+1)*n/2
f(n) = (n²+n)/2
用大O表示法,忽略常量、低阶和常数系数。
时间复杂度为: O(n²)
终端打印结果:
网上搜了一下,很多都说得云里雾里的,下面举个栗子????说明:
假设某学校积分入学剩余2个学位,A、B、C三位学生先后报名,积分分别为 [A(90), B(90), C(100)] ,积分从高到低排序,前两名获得入学资格,如果使用选择排序:
第一轮排序会将 A 和 C 交换,变成 [C(100), B(90), A(90)] ,此时排序已完成;
A、B同积分,但原来A比B优先报名的,本应优先取得入学资格,排序后却变成了B在A的前面,现实中必然是不公平的。
因此可以看出, 选择排序 是 不稳定 的。
RUNOOB.COM-1.2 选择排序
数据排序方法
好的排序方法可以有效提高排序速度,提高排序效果。
在计算机领域主要使用数据排序方法根据占用内存的方式不同分为2大类:内部排序方法与外部排序方法。
内部排序方法
若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序。
内排序的方法有许多种,按所用策略不同,可归纳为五类:插入排序、选择排序、交换排序、归并排序和基数排序。
其中,插入排序主要包括直接插入排序和希尔排序两种;选择排序主要包括直接选择排序和堆排序;交换排序主要包括气(冒)泡排序和快速排序。
外部排序方法
外部排序基本上由两个相互独立的阶段组成。首先,按可用内存大小,将外存上含n个记录的文件分成若干长度为k的子文件或段(segment),依次读入内存并利用有效的内部排序方法对它们进行排序,并将排序后得到的有序子文件重新写入外存。通常称这些有序子文件为归并段或顺串;然后,对这些归并段进行逐趟归并,使归并段(有序子文件)逐渐由小到大,直至得到整个有序文件为止。
IOS几种简单有效的数组排序方法
//第一种,利用数组的sortedArrayUsingComparator调用 NSComparator ,obj1和obj2指的数组中的对象
NSComparator cmptr = ^(id obj1, id obj2){
if ([obj1 integerValue] [obj2 integerValue]) {
return (NSComparisonResult)NSOrderedDescending;
}
if ([obj1 integerValue] [obj2 integerValue]) {
return (NSComparisonResult)NSOrderedAscending;
}
return (NSComparisonResult)NSOrderedSame;
};
NSArray *sortArray = [[NSArray alloc] initWithObjects:@"1",@"3",@"4",@"7",@"8",@"2",@"6",@"5",@"13",@"15",@"12",@"20",@"28",@"",nil];
//排序前
NSMutableString *outputBefore = [[NSMutableString alloc] init];
for(NSString *str in sortArray){
[outputBefore appendFormat:@"];
}
NSLog(@"排序前:%@",outputBefore);
[outputBefore release];
//第一种排序
NSArray *array = [sortArray sortedArrayUsingComparator:cmptr];
NSMutableString *outputAfter = [[NSMutableString alloc] init];
for(NSString *str in array){
[outputAfter appendFormat:@"];
}
NSLog(@"排序后:%@",outputAfter);
[outputAfter release];
第二种 排序方法 利用sortedArrayUsingFunction 调用 对应方法customSort,这个方法中的obj1和obj2分别是指数组中的对象。
NSInteger customSort(id obj1, id obj2,void* context){
if ([obj1 integerValue] [obj2 integerValue]) {
return (NSComparisonResult)NSOrderedDescending;
}
if ([obj1 integerValue] [obj2 integerValue]) {
return (NSComparisonResult)NSOrderedAscending;
}
return (NSComparisonResult)NSOrderedSame;
}
NSArray *sortArray = [[NSArray alloc] initWithObjects:@"1",@"3",@"4",@"7",@"8",@"2",@"6",@"5",@"13",@"15",@"12",@"20",@"28",@"",nil];
//排序前
NSMutableString *outputBefore = [[NSMutableString alloc] init];
for(NSString *str in sortArray){
[outputBefore appendFormat:@"];
}
NSLog(@"排序前:%@",outputBefore);
[outputBefore release];
NSArray *array = [sortArray sortedArrayUsingFunction:customSort context:nil];
NSMutableString *outputAfter = [[NSMutableString alloc] init];
for(NSString *str in array){
[outputAfter appendFormat:@"];
}
NSLog(@"排序后:%@",outputAfter);
[outputAfter release];
第三种 利用sortUsingDescriptors调用NSSortDescriptor
NSSortDescriptor *sortDescriptor = [[NSSortDescriptor alloc] initWithKey:@"price" ascending:NO];//其中,price为数组中的对象的属性,这个针对数组中存放对象比较更简洁方便
NSArray *sortDescriptors = [[NSArray alloc] initWithObjects:sortDescriptor count:1];
[_totalInfoArray sortUsingDescriptors:sortDescriptors];
[_airListView refreshTable:_totalInfoArray];
[sortDescriptor release];
[sortDescriptors release];
希尔排序(Shell Sort),一听这名字就知道是一个叫希尔的外国人发明的排序。没错,他就是唐纳德 希尔(Donald Shell),一位美国的计算机科学家,他于1959年发明的希尔排序算法。
对于希尔排序,比较正式的官方的解释是这样:
希尔排序也是插入排序的一种。既然是其中的一种,那么他们的区别是什么呢?插入排序在最坏的情况下,即整个数组是倒序的,此时时间复杂度达到了O(n 2 )。希尔排序在插入排序的基础上增加一个叫 增量 的概念。那什么增量?插入排序只能与相邻的元素进行比较,而希尔排序则是进行跳跃比较,而增量就是步长。比如增量为3时,下标为0的元素与下标为3的元素比较,3再与6比较,1与4比较,4再与7比较……想必你肯定做过一群人站成一排,按一二报数,喊一的一队,喊二的一队,此时的增量就是2。所以你也可以理解为是按增量进行了分组,再对每一组进行插入排序。当使用一个增量对所有的分组排好序后,再去减少增量,重复之前步骤,直到增量为1,此时只有一个分组了,再对这一个分组进行插入排序,整个希尔排序就结束了(所以希尔排序也叫 缩小增量排序 ,但显然没有希尔排序好听和高大上 斜眼笑)。
从增量的初始值选取,到逐渐变为1,将所有用过的增量组成一个序列,就是 增量序列 。而希尔排序的增量序列选择直接影响它的时间复杂度(不要问我为什么,我也不知道)。最简单的增量就是希尔鼓励使用的希尔增量。增量初始值选择为N/2(N为数组长度),然后每次将增量除以2,得到下一个增量。所以它的增量序列为{N/2, (N / 2)/2, ..., 1}。除了希尔增量还有 Hibbard 增量 、 Knuth增量 等等都是很复杂的数学公式,我怕你看了晕,就放在后面介绍吧!(说的好像自己看了不晕一样)
那下面我们就以最简单的希尔增量来进行希尔排序。
然后对比之前文章所写的选择排序和插入排序。
三个同样的数组,分别使用选择、插入、希尔进行排序比较时间。
数组长度1万时打印结果为:
数组长度为两万时打印结果为:
差距是很明显的。
希尔排序为 不稳定性排序 。因为相同的元素可能在各自的插入排序中移动,所以它的稳定性就被打破了。可能有人想问,稳定性是干嘛的啊?稳定的意思是指 相同的元素在排序后的相对位置不变 。比如有两个5 ,作为区分前面的叫5 1 ,后面的叫5 2 ,排序完成后5 1 还在5 2 的前面。那你可能会问,反正是一样的,换了就换呗。但是在实际应用中被排序的对象会拥有不同的属性,举个栗子,公司在招聘时,想要年龄小的,所以对所有人进行了按年龄的排序。之后还想看成绩分数高的。所以在按成绩进行排序时就有可能出现成绩一样的,但他们的年龄不一样,而你不能把成绩相同但年龄大的排在小的前面。此时算法的稳定性就有了意义。
使用希尔增量,在最坏的情况下时间复杂度仍为O(n 2 ),而使用hibbard增量在最坏的情况下却为O(n 3/2 )。
如果觉得作者对哪里的理解有偏差或者其他的优化,希望不吝赐教,留言指正。谢谢支持~
冒泡排序是相邻数据进行两两比较,假设升序排序,则一趟排序下来,就会有一个最大数产生在数组最末端。因为有 n 个数据需要进行比较,而每一趟排序需要遍历n个数据,所以时间复杂度为O(n^2)
快速排序是定下一个基准数(一般默认定义最左侧数据为基准数,可以理解为参照数),每一趟排序都需要从左(角标 i)右(角标 j)两侧开始像中间进行排序,因为基准数定义在左侧,一般先从右侧开始向左侧移动,j--;遇到小于基准数的暂停,左侧开始向右移动,i++;遇到大于基准数的暂停;然后交换i 和 j 所对应的数据。当i和j相遇的时候,则将相遇值与基准数进行交换,一趟排序结束。时间复杂度是O(log2 n)