總結了下在iOS開發(fā)常用到的算法，不管是在面試中還是日常開發(fā)中，都會用到
1、冒泡排序
冒泡算法是重復地走訪過要排序的數(shù)列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數(shù)列的工作是重復地進行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。
對以下一組數(shù)據(jù)進行降序排序（冒泡排序）“55, 23, 93, 23, 4, 56, 1, 34, 11, 69”
int array[10] = {55, 23, 93, 23, 4, 56, 1, 34, 11, 69};
int num = sizeof(array)/sizeof(int);
for (int i = 0 ; i < num - 1; i++) {
for (int j = 0 ; j < num - 1 - i; j++) {
if (array[j] < array[j +1]) {
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
for (int i = 0; i < num; i++) {
printf("%d", array[i]);
if (i == num - 1) {
printf("\n");
} else {
printf(" ");
}
}
2、選擇排序
選擇排序的工作原理是每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完。
對以下一組數(shù)據(jù)進行升序排序（選擇排序）。“55, 23, 93, 23, 4, 56, 1, 34, 11, 69”
int array[10] = {55, 23, 93, 23, 4, 56, 1, 34, 11, 69};
int num = sizeof(array)/sizeof(int);
for (int i = 0; i < num - 1; i++) {
for (int j = i + 1; j < num ; j++) {
if (array[i] > array [j]) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
for (int i = 0; i < num; i++) {
printf("%d", array[i]);
if (i == num - 1) {
printf("\n");
} else {
printf(" ");
}
}
3、快速排序算法
該方法的基本思想是：
1．先從數(shù)列中取出一個數(shù)作為基準數(shù)。
2．分區(qū)過程，將比這個數(shù)大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊。
3．再對左右區(qū)間重復第二步，直到各區(qū)間只有一個數(shù)。
- (void)viewDidLoad {
[super viewDidLoad];
NSMutableArray *arr = [[NSMutableArray alloc] initWithObjects:@(55), @(23),@(93),@(23),@(4),@(56),@(1),@(34),@(69),nil];
[self quickSortArray:arr withLeftIndex:0 andRightIndex:arr.count - 1];
NSLog(@"%@",arr);
}
- (void)quickSortArray:(NSMutableArray *)array withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex
{
if (leftIndex >= rightIndex) {//如果數(shù)組長度為0或1時返回
return ;
}
NSInteger i = leftIndex;
NSInteger j = rightIndex;
//記錄比較基準數(shù)
NSInteger key = [array[i] integerValue];
while (i < j) {
/**** 首先從右邊j開始查找比基準數(shù)小的值 ***/
while (i < j && [array[j] integerValue] >= key) {//如果比基準數(shù)大，繼續(xù)查找
j--;
}
//如果比基準數(shù)小，則將查找到的小值調(diào)換到i的位置
array[i] = array[j];
/**** 當在右邊查找到一個比基準數(shù)小的值時，就從i開始往后找比基準數(shù)大的值 ***/
while (i < j && [array[i] integerValue] <= key) {//如果比基準數(shù)小，繼續(xù)查找
i++;
}
//如果比基準數(shù)大，則將查找到的大值調(diào)換到j的位置
array[j] = array[i];
}
//將基準數(shù)放到正確位置
array[i] = @(key);
/**** 遞歸排序 ***/
//排序基準數(shù)左邊的
[self quickSortArray:array withLeftIndex:leftIndex andRightIndex:i - 1];
//排序基準數(shù)右邊的
[self quickSortArray:array withLeftIndex:i + 1 andRightIndex:rightIndex];
}
4、 歸并排序
該方法的基本思想是：
1.分解：將待排序的問題分解成大小大致相等的兩部分。
2.求解子問題：用歸并排序的方法對兩個子問題進行遞歸排序。
3.合并(merge)：將排好序的有序子序列進行合并，得到符合要求的子序列。
@interface ViewController ()
@property (nonatomic, strong) NSMutableArray *tempArr;
@end
@implementation ViewController
-(NSMutableArray *)tempArr
{
if (_tempArr == nil) {
_tempArr = [NSMutableArray array];
}
return _tempArr;
}
- (void)viewDidLoad {
[super viewDidLoad];
NSMutableArray *arr = [[NSMutableArray alloc] initWithObjects:@(55), @(29),@(93),@(23),@(4),@(56),@(1),@(34),@(69),nil];
[self mergeSortArray:arr lowIndex:0 highIndex:arr.count - 1];
NSLog(@"%@",arr);
}
- (void)mergeSortArray:(NSMutableArray *)array lowIndex:(NSInteger)lowIndex highIndex:(NSInteger)highIndex
{
if (lowIndex >= highIndex) {
return;
}
NSInteger midIndex = lowIndex + (highIndex - lowIndex) / 2;
[self mergeSortArray:array lowIndex:lowIndex highIndex:midIndex];
[self mergeSortArray:array lowIndex:midIndex + 1 highIndex:highIndex];
[self mergeArray:array lowIndex:lowIndex midIndex:midIndex highIndex:highIndex];
}
- (void)mergeArray:(NSMutableArray *)array lowIndex:(NSInteger)lowIndex midIndex:(NSInteger)midIndex highIndex:(NSInteger)highIndex
{
for (NSInteger i = lowIndex; i <= highIndex; i ++) {
self.tempArr[i] = array[i];
}
NSInteger k = lowIndex;
NSInteger l = midIndex + 1;
for (NSInteger j = lowIndex; j <= highIndex; j ++) {
if (l > highIndex) {
array[j] = self.tempArr[k];
k++;
}else if (k > midIndex)
{
array[j] = self.tempArr[l];
l++;
}else if ([self.tempArr[k] integerValue] > [self.tempArr[l] integerValue])
{
array[j] = self.tempArr[l];
l++;
}else
{
array[j] = self.tempArr[k];
k++;
}
}
}
