iOS算法(一)快速排序算法

快速排序是当遇到较大数据时,排序快,高效的方法(公司面试时,基本上会被问到...)

该方法的基本思想是:

1.先从数列中取出一个数作为基准数。

2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。

3.再对左右区间重复第二步,直到各区间只有一个数。

简单地理解就是,找一个基准数(待排序的任意数,一般都是选定首元素),把比小于等于基准数的元素放到基准数的左边,把大于基准数的元素放在基准数的右边.排完之后,在把基准数的左边和右边各看成一个整体, 左边:继续选择基准数把小于等于基准数的元素放到基准数的左边,把大于基准数的元素放在基准数的右边,右边也是一样..直到各区间只有一个数位置.

快速排序之所比较快,因为相比冒泡排序,每次交换是跳跃式的。每次排序的时候设置一个基准点,将小于等于基准点的数全部放到基准点的左边,将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换,交换的距离就大的多了。因此总的比较和交换次数就少了,速度自然就提高了。当然在最坏的情况下,仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2),它的平均时间复杂度为O(NlogN)。

图片诠释上面的思想
11.png

代码实现:

define kSize 20

define kMax 100

-(void)viewDidLoad { [super viewDidLoad]; //初始化20个100以内的随机数,放在data数组中 NSMutableArray *data = [[NSMutableArray alloc] initWithCapacity:kSize]; for (int i =0;i<kSize;i++) { u_int32_t x = arc4random() % kMax;//0~kMax NSNumber *num = [[NSNumber alloc] initWithInt:x]; [data addObject:num]; }
NSLog(@"排序前的数据:%@",[data description]); LZJSort *sort = [[LZJSort alloc] init]; [sort quickSortWithArray:data]; }

方法实现

-(void)quickSortWithArray:(NSArray *)aData{ NSMutableArray *data = [[NSMutableArray alloc] initWithArray:aData]; [self quickSortWithArray:data left:0 right:[aData count]-1]; NSLog(@"快速排序后的结果:%@",[data description]); } -(void)quickSortWithArray:(NSMutableArray *)aData left:(NSInteger)left right:(NSInteger)right{ if (right > left) { NSInteger i = left; NSInteger j = right + 1; while (true) { while (i+1 < [aData count] && [aData objectAtIndex:++i] < [aData objectAtIndex:left]) ; while (j-1 > -1 && [aData objectAtIndex:--j] > [aData objectAtIndex:left]) ; if (i >= j) { break; } [self swapWithData:aData index1:i index2:j]; } [self swapWithData:aData index1:left index2:j]; [self quickSortWithArray:aData left:left right:j-1]; [self quickSortWithArray:aData left:j+1 right:right]; } } -(void)swapWithData:(NSMutableArray *)aData index1:(NSInteger)index1 index2:(NSInteger)index2{ NSNumber *tmp = [aData objectAtIndex:index1]; [aData replaceObjectAtIndex:index1 withObject:[aData objectAtIndex:index2]]; [aData replaceObjectAtIndex:index2 withObject:tmp]; }

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 1.OC里用到集合类是什么? 基本类型为:NSArray,NSSet以及NSDictionary 可变类型为:NS...
    轻皱眉头浅忧思阅读 1,396评论 0 3
  • 一 冒泡排序 冒泡排序:原理:冒泡顾名思义,就像气泡从水底冒出一样,它的排序方式是:研究了一下,它给人的感觉是像近...
    你美依旧阅读 132评论 0 0
  • //冒泡排序从大到小 (void)orderBubbleSort:(NSMutableArray *)mArray...
    onlyyourself阅读 263评论 0 0
  • 知道自己的位置 当谈及成长的时候,有一个重要的前提:要知道自己的位置。就是要知道自己现在是一个什么样的水平,未来能...
    成长时间线阅读 142评论 0 0
  • 就想安安静静做个淡然女子, 上班休闲都能轻轻松松地美着。
    傲慢的小秋菊阅读 171评论 3 1