算法-冒泡排序和快速排序(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
//http://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;
代碼可能不是最簡潔的，但是應該是比較好理解的，如果有問題，隨時可以在評論區與我交流~
