希尔排序实际上是插入排序的一种,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。时间复杂度无法准确的估计,希尔排序的基本逻辑
记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个数组恰被分成一组,算法便终止。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
-(
NSMutableArray
*)shellSort:(
NSMutableArray
*)arr{
NSInteger
group=1;
while
(group>[arr count]/3) {
group=3*group+1;
}
while
(group>=1) {
//将数组变成group有序
for
(
NSInteger
i=group; i<[arr count]; i++) {
//将分组后的数据与前面的数据一一比较进行交换
for
(
NSInteger
j=i; j>=group&&[arr[j] integerValue]<[arr[j-group] integerValue]; j-=group) {
NSInteger
temp=[arr[j] integerValue];
arr[j]=[
NSNumber
numberWithInteger:[arr[j-group] integerValue]];
arr[j-group]=[
NSNumber
numberWithInteger:temp];
}
}
group=group/3;
}
return
arr;
}
|
如果数组的长度是10,这里的增量是4,网上有些博客对理解是,增量的取值规则为第一次取总长度的一半,第二次取一半的一半,依次累推直到1为止,其实这样可以快速理解希尔排序,不过希尔排序的性能跟增量的选择有很大的关系,对于增量的选择不应该不应该这么简单粗暴,如果在实际实战过程中需要根据实际情况取决。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
NSMutableArray
*arr=[[
NSMutableArray
alloc]initWithCapacity:10];
[arr addObject:@
"6"
];
[arr addObject:@
"3"
];
[arr addObject:@
"2"
];
[arr addObject:@
"8"
];
[arr addObject:@
"9"
];
[arr addObject:@
"10"
];
[arr addObject:@
"4"
];
[arr addObject:@
"5"
];
[arr addObject:@
"1"
];
MySort *sort=[[MySort alloc]init];
NSMutableArray
*resultArr= [sort shellSort1:arr];
for
(
NSInteger
i=0; i<[resultArr count]; i++) {
NSLog
(@
"%@"
,[resultArr objectAtIndex:i]);
}
NSLog
(@
"iOS技术交流群:228407086"
);
NSLog
(@
"原文地址:http://www.cnblogs.com/xiaofeixiang"
);
|
运行结果:
本文转自Fly_Elephant博客园博客,原文链接:http://www.cnblogs.com/xiaofeixiang/p/4584859.html,如需转载请自行联系原作者