之前參加了一場(chǎng)海歸博士主持的面試,問了很多關(guān)于數(shù)組,字典,基礎(chǔ)算法的知識(shí),上學(xué)那會(huì)忽視了,經(jīng)歷那次之后想了很多,加上最近工作遇到了很多這方面的邏輯問題,所以在這里總結(jié)一下基礎(chǔ)排序算法的OC實(shí)現(xiàn).
常用基礎(chǔ)排序算法
- 冒泡排序
- 快速排序
冒泡排序
NSMutableArray *ary = [NSMutableArray arrayWithObjects:@34,@12,@24,@3,@51,nil];
//遍歷`數(shù)組的個(gè)數(shù)`次 /*
i = 0 的時(shí)候，j的相鄰兩個(gè)位置都要比較排一下位置：
j = 0 的時(shí)候：ary = 34,12,24,3,51
j = 1 的時(shí)候：ary = 34,24,12,3,51
j = 2 的時(shí)候：ary = 34,24,12,3,51
j = 3 的時(shí)候：ary = 34,24,12,51,3
i = 1; ............后面依次類推就可以了
*/
for (int i = 0; i < ary.count; ++i)
{
//遍歷數(shù)組的每一個(gè)`索引`（不包括最后一個(gè),因?yàn)楸容^的是j+1）
for (int j = 0; j < ary.count-1; ++j)
{
//根據(jù)索引的`相鄰兩位`進(jìn)行`比較`
if (ary[j] < ary[j+1]) //從大到小,從小到大改一下此處的符號(hào)就好了
{
[ary exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
}
}
NSLog(@"最終結(jié)果：%@",ary);
快速排序
快速排序：是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法，當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時(shí)阔馋，快速排序的平均時(shí)間最短尘颓；
- (void)viewDidLoad {
[super viewDidLoad];
NSMutableArray *arr = [[NSMutableArray alloc]initWithObjects:@(16), @(11),@(12),@(5),@(19),@(14),@(31),@(17),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ù)組長(zhǎng)度為0或1時(shí)返回 return ;
}
NSInteger i = leftIndex;
NSInteger j = rightIndex;
//記錄比較基準(zhǔn)數(shù)
NSInteger key = [array[i] integerValue];
while (i < j)
{
/****
首先從右邊j開始查找比基準(zhǔn)數(shù)小的值
***/
while (i < j && [array[j] integerValue] >= key)
{
//如果比基準(zhǔn)數(shù)大幸斥，繼續(xù)查找 j--;
}
//如果比基準(zhǔn)數(shù)小半沽，則將查找到的小值調(diào)換到i的位置 array[i] = array[j];
/****
當(dāng)在右邊查找到一個(gè)比基準(zhǔn)數(shù)小的值時(shí)椰憋，就從i開始往后找比基準(zhǔn)數(shù)大的值
***/
while (i < j && [array[i] integerValue] <= key)
{
//如果比基準(zhǔn)數(shù)小此熬，繼續(xù)查找
i++;
}
//如果比基準(zhǔn)數(shù)大橄教，則將查找到的大值調(diào)換到j(luò)的位置
array[j] = array[i];
}
//將基準(zhǔn)數(shù)放到正確位置
array[i] = @(key);
/**** 遞歸排序 ***/
//排序基準(zhǔn)數(shù)左邊的
[self quickSortArray:array withLeftIndex:leftIndex andRightIndex:i - 1];
//排序基準(zhǔn)數(shù)右邊的
[self quickSortArray:array withLeftIndex:i + 1 andRightIndex:rightIndex]; }
