算法-冒泡排序和快速排序(Object-C)
索引 0 1 2 3 4 5 6
数值 15 32 8 99 12 17 36，
①取出0位的15作为基准值，然后倒序从后往前找小于15的，将12赋值给0位；
②从前往后找大于15的将32放置到位置4；
③位置1空出来，然后继续倒序找小于15的，正序找大于15的，最后索引到大3的时候重复以上过程。
冒泡排序
冒泡基本上没有什么好说的，直接看代码吧，新建了Sort类处理排序:
//
// Sort.h
// Algorithm
//https://www.cnblogs.com/xiaofeixiang
// Created by keso on 15/3/15.
// Copyright (c) 2015年 keso. All rights reserved.
//
#import <Foundation/Foundation.h>
@interface Sort : NSObject
@property (nonatomic,strong)NSMutableArray *dataSource;
-(void)bubbleSort:(NSMutableArray*)dataSource;
-(void)quickSort:(NSInteger)start endIndex:(NSInteger)end;
@end
Sort.m中的bubbleSort实现:
//冒泡排序
-(void)bubbleSort:(NSMutableArray*)dataSource{
NSUInteger count=[dataSource count];
for(int i=0;i<count;i++){
for (int j=0; j<count-i-1;j++) {
if ([dataSource[j] intValue]>[dataSource[j+1] intValue]) {
NSString *temp=dataSource[j];
dataSource[j]=dataSource[j+1];
dataSource[j+1]=temp;
}
}
}
for (NSInteger i=0; i<[dataSource count]; i++) {
NSLog(@"排序--%@",dataSource[i]);
}
}
冒泡排序比较稳定，但是每次只是移动两个数字比较慢，如果是正序的话时间复杂度是O(n)，如果是逆序的需要弄成正序的，那么事件复杂度O(n*n)，会经过n(n-1)/2次比较，平均事件复杂度O(n*n);
快速排序
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。基本思路如下:
1．先从数组中取出一个数作为基准数值，也可以理解为中间变量。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。
快速排序由于排序效率在同为O(n*logn)的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想----分治法也确实实用，也算是出门居家必备的算法了，理解比较好理解，具体的实现能写出来基本上算是理解的，至于更深的就要看工作中实际的操作过程啦。
Sort.h中定义了一个QuickSort方法，还有一个NSMutabArray是为了保存最后的结果的,具体实现:
//快速排序
-(void)quickSort:(NSInteger)start endIndex:(NSInteger)end{
if (start<end) {
NSInteger standardValue=[_dataSource[start] intValue];
NSInteger left=start,right=end;
while (start<end) {
//从后往前找，如果后面的数值大于基准值，递减
while (start<end&&[_dataSource[end] intValue]>standardValue) {
end--;
}
//小于基准值的时候，给数组中索引为start赋值
if (start<end) {
_dataSource[start]=_dataSource[end];
start=start+1;
}
//从前往后找，如果数值小于基准值，递增
while (start<end&&[_dataSource[start] intValue]<standardValue) {
start++;
}
//大于基准值，给数组中索引为end的数据赋值
if (start<end) {
_dataSource[end]=_dataSource[start];
end=end-1;
}
}
//退出的时候值start和end相等
_dataSource[start]=[NSString stringWithFormat:@"%ld",(long)standardValue];
[self quickSort:left endIndex:end-1];//处理左边
[self quickSort:end+1 endIndex:right];//处理右边
}
}
主函数中的调用如下:
NSMutableArray *data=[[NSMutableArray alloc] initWithObjects:@"10",@"88",@"97",@"33",@"8",@"73",@"18", nil];
[sort bubbleSort:data];
sort.dataSource=data;
[sort quickSort:0 endIndex:[data count]-1];
for (int i=0; i<[data count]; i++) {
NSLog(@"排序:%@",data[i]);
}
return 0;
代码可能不是最简洁的，但是应该是比较好理解的，如果有问题，随时可以在评论区与我交流~