obj-c排序算法
文章目录
obj-c排序算法
本文采用objective-c实现常见的排序算法：选择排序，插入排序，快速排序。
悼念乔帮主，期待apple在后乔帮主时代创造出更出色的产品。
1
//
2
//
Sort.h
3
//
Algorithm
4
//
5
//
Created by 张 汉国 on 11-9-30.
6
//
Copyright 2011年 __MyCompanyName__. All rights reserved.
7
8
9
#import
<Foundation/Foundation.h>
10
11
interface
style="font: 12.0px 'Courier New'; color: #008080; background-color: #f5f5f5">12
13
}
14
15
//选择排序
16
-(void)selectSortWithArray:(NSArray
*)aData;
17
//插入排序
18
-(void)insertSortWithArray:(NSArray
*)aData;
19
//快速排序
20
-(void)quickSortWithArray:(NSArray
*)aData;
21
22
-(void)swapWithData:(NSMutableArray
*)aData index1:(NSInteger)index1 index2:(NSInteger)index2;
23
24
25
end
1
//
2
//
Sort.m
3
//
Algorithm
4
//
5
//
Created by 张 汉国 on 11-9-30.
6
//
Copyright 2011年 __MyCompanyName__. All rights reserved.
7
//
8
9
#import
“Sort.h”
10
11
interface
Sort()
12
-(void)quickSortWithArray:(NSArray
*)aData left:(NSInteger)left right:(NSInteger)right;
13
end
14
15
implementation
Sort
16
17
-
(id)init
18
{
19
self = [super init];
20
if
(self)
{
21
//
Initialization code here.
22
}
23
24
return
self;
25
}
26
27
-(void)selectSortWithArray:(NSArray
*)aData{
28
NSMutableArray *data = [[NSMutableArray
alloc]initWithArray:aData];
29
for
(int
i=0;
i<[data count]-1;
i++) {
30
int
m
=i;
31
for
(int
j
=i+1;
j<[data count]; j++) {
32
if
([data
objectAtIndex:j] < [data objectAtIndex:m]) {
33
m = j;
34
}
35
}
36
if
(m
!= i) {
37
[self swapWithData:data index1:m index2:i];
38
}
39
}
40
NSLog( “选择排序后的结果：% “,[data
description]);
41
[data release];
42
}
43
44
-(void)insertSortWithArray:(NSArray
*)aData{
45
NSMutableArray *data = [[NSMutableArray
alloc]initWithArray:aData];
46
for
(int
i
= 1;
i < [data count]; i++) {
47
id
tmp
= [data objectAtIndex:i];
48
int
j
= i-1;
49
while
(j
!= -1
&&
[data objectAtIndex:j] > tmp) {
50
[data replaceObjectAtIndex:j+1
withObject:[data
objectAtIndex:j]];
51
j–;
52
}
53
[data replaceObjectAtIndex:j+1
withObject:tmp];
54
}
55
NSLog( “插入排序后的结果：% “,[data
description]);
56
[data release];
57
}
58
59
-(void)quickSortWithArray:(NSArray
*)aData{
60
NSMutableArray *data = [[NSMutableArray alloc]
initWithArray:aData];
61
[self quickSortWithArray:data left:0
right:[aData
count]-1];
62
NSLog( “快速排序后的结果：% “,[data
description]);
63
[data release];
64
65
}
66
67
-(void)quickSortWithArray:(NSMutableArray
*)aData left:(NSInteger)left right:(NSInteger)right{
68
if
(right
> left) {
69
NSInteger i = left;
70
NSInteger j = right + 1;
71
while
(true)
{
72
while
(i+1
<
[aData count] && [aData objectAtIndex:++i] < [aData
objectAtIndex:left]) ;
73
while
(j-1
>
-1
&&
[aData objectAtIndex:–j] > [aData objectAtIndex:left]) ;
74
if
(i
>= j) {
75
break;
76
}
77
[self swapWithData:aData index1:i index2:j];
78
}
79
[self swapWithData:aData index1:left index2:j];
80
[self quickSortWithArray:aData left:left right:j-1];
81
[self quickSortWithArray:aData left:j+1
right:right];
82
}
83
}
84
85
86
-(void)dealloc{
87
[super dealloc];
88
}
89
90
-(void)swapWithData:(NSMutableArray
*)aData index1:(NSInteger)index1 index2:(NSInteger)index2{
91
NSNumber *tmp = [aData objectAtIndex:index1];
92
[aData replaceObjectAtIndex:index1 withObject:[aData
objectAtIndex:index2]];
93
[aData replaceObjectAtIndex:index2 withObject:tmp];
94
}
95
96
end
测试例子：
1
//
2
//
main.m
3
//
Algorithm
4
//
5
//
Created by 张 汉国 on 11-9-30.
6
//
Copyright 2011年 __MyCompanyName__. All rights reserved.
7
//
8
9
#import
<Foundation/Foundation.h>
10
#import
“Sort.h”
11
12
#define
kSize
20
13
#define
kMax
100
14
15
int
main
(int
argc,
const
char
*
argv[])
16
{
17
18
NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];
19
20
//
insert code here…
21
NSLog( “Hello,
World!”);
22
23
NSMutableArray *data = [[NSMutableArray alloc]
initWithCapacity:kSize];
24
25
for
(int
i
=0;i<kSize;i++)
{
26
u_int32_t x = arc4random() % kMax;//0~kMax
27
NSNumber *num = [[NSNumber alloc] initWithInt:x];
28
[data addObject:num];
29
[num release];
30
}
31
32
NSLog( “排序前的数据：% “,[data
description]);
33
34
Sort *sort = [[Sort alloc] init];
35
[sort selectSortWithArray:data];
36
[sort insertSortWithArray:data];
37
[sort quickSortWithArray:data];
38
[sort release];
39
[data release];
40
[pool drain];
41
return
0;
42
}
