排序算法
// 1. 冒泡排序 （大數(shù)沉底）
/** 冒泡排序的特點(diǎn)
* 我們?nèi)〕龅谝粋€(gè)數(shù) 和 第二個(gè)數(shù) 將最小的數(shù) 賦給第一個(gè)數(shù) 然后讓第二個(gè)數(shù)與 第三個(gè)數(shù)比較 將最小的數(shù) 賦給 第二個(gè)數(shù) 然后依次類推
* 第一輪下來我們就獲取到了最大的數(shù) 第二輪就從第二個(gè)數(shù)開始 我們就獲取到了第二個(gè)比較大的數(shù) 通過循環(huán)就可以實(shí)現(xiàn) 升序
*/
NSMutableArray * dataArr = [NSMutableArray arrayWithArray:@[@"13",@"5",@"89",@"20",@"40",@"18",@"120"]];
for(int i = 0 ;i<dataArr.count;i++){
for(int j = 0; j< dataArr.count-1-i;j++){
if([dataArr[j] integerValue]>[dataArr[j+1] integerValue]){
NSString * temp = dataArr[j];
dataArr[j] = dataArr[j+1];
dataArr[j+1] = temp;
}
}
}
NSLog(@"冒泡排序之后數(shù)組的順序--%@",dataArr);
// 2. 選擇排序 （小數(shù)上來）
/** 選擇排序的特點(diǎn)
* 我們?nèi)〕龅谝粋€(gè)數(shù) 然后讓它與剩下的數(shù)一一比較 那么一輪下來 我們就能確定最小值
*/
NSMutableArray * selectArr = [NSMutableArray arrayWithArray:@[@"13",@"5",@"89",@"20",@"40",@"18",@"120"]];
for(int i=0;i<selectArr.count-1;i++){
for(int j = i+1;j<selectArr.count;j++){
if([selectArr[i] integerValue]>[selectArr[j] integerValue]){
NSString * temp = selectArr[i];
selectArr[i] = selectArr[j];
selectArr[j] = temp;
}
}
}
NSLog(@"選擇排序之后數(shù)組的順序--%@",selectArr);
// 3. 插入排序
/** 插入排序的特點(diǎn)
* 第一步我們?nèi)〕龅诙?shù) 然后讓 第二個(gè)數(shù)與第一個(gè)數(shù)比較 如果 第二個(gè)數(shù)< 第一個(gè)數(shù) 那么我們就將數(shù)組第二個(gè)數(shù)的位子換成第一個(gè)數(shù)的值 然后 j--
*/
NSMutableArray * insertArr = [NSMutableArray arrayWithArray:@[@"13",@"5",@"89",@"20",@"40",@"18",@"120"]];
for(int i =1;i<insertArr.count;i++){
int j = i;
NSString * temp = insertArr[i];
while (j>0&&[temp integerValue] < [insertArr[j-1] integerValue]) {
[insertArr replaceObjectAtIndex:j withObject:insertArr[j-1]];
j--;
}
[insertArr replaceObjectAtIndex:j withObject:temp];
}
NSLog(@"插入排序最終結(jié)果---%@",insertArr);
//4. 希爾排序
/** 希爾排序的特點(diǎn)
* 類似于對(duì)半查找 但又不一樣 這個(gè)不常用湃累。了解就行了
*/
NSMutableArray * hillArr = [NSMutableArray arrayWithArray:@[@"13",@"5",@"89",@"20",@"40",@"18",@"120"]];
int gap = hillArr.count/2.0;
while (gap>=1) {
for(int i = gap ;i< hillArr.count;i++){
NSString * temp = hillArr[i];
int j = i;
while (j>gap && [temp integerValue]<[hillArr[j-gap] integerValue]) {
[hillArr replaceObjectAtIndex:j withObject:hillArr[j-gap]];
j-=gap;
}
[hillArr replaceObjectAtIndex:j withObject:temp];
}
gap = gap/2;
}
NSLog(@"希爾排序最終結(jié)果---%@",insertArr);
//5. 二分查找
/** 二分查找的特點(diǎn)。這個(gè)蠻重要的有些面試的話 會(huì)問到
* 二分查找有一個(gè)特點(diǎn)那就是這個(gè)數(shù)組一定是排序好的 不論是升序 還是降序 都一定排好了
*/
NSArray * erFenArr = @[@"5",@"13",@"20",@"80",@"87",@"100",@"120"];
NSLog(@"二分查找最終輸出的值--%ld",(long)[self TB_erFenCheckWithlow:0 Andhight:erFenArr.count AndArr:erFenArr AndSelctID:@"80"]);
// 二分查找
-(NSInteger )TB_erFenCheckWithlow:(NSInteger)low Andhight:(NSInteger)hight AndArr:(NSArray *)arr AndSelctID:(NSString *)key{
if(low<hight){
NSInteger mid = (low + hight)/2;
if([key integerValue] == [arr[mid] integerValue]) {
return mid;
} else if ([key integerValue] < [arr[mid] integerValue]) {
return [self TB_erFenCheckWithlow:low Andhight:mid-1 AndArr:arr AndSelctID:key];
} else {
return [self TB_erFenCheckWithlow:mid+1 Andhight:hight AndArr:arr AndSelctID:key];
}
}else{
NSLog(@"參數(shù)錯(cuò)誤");
return -1;
}
}
//6. 快排
/** 快排 這個(gè)也蠻重要的 面試的話有可能會(huì)問
*/
NSMutableArray * kuaipaiArr = [NSMutableArray arrayWithArray:@[@"13",@"5",@"89",@"20",@"40",@"18",@"120"]];
[self TB_KuaipaiWithArr:kuaipaiArr low:0 hight:kuaipaiArr.count-1];
NSLog(@"快速排序最終結(jié)果---%@",kuaipaiArr);
// 快排
-(void)TB_KuaipaiWithArr:(NSMutableArray *)kuaipaiarr low:(NSInteger)low hight:(NSInteger)hight{
if(low>=hight) return;
NSInteger i = low;
NSInteger j = hight;
NSString * temp = kuaipaiarr[low];
while (i<j) {
while (i<j &&[temp integerValue]<=[kuaipaiarr[j] integerValue]) {
j--;
}
kuaipaiarr[i] = kuaipaiarr[j];
while (i<j&& [temp integerValue]>=[kuaipaiarr[i] integerValue]) {
i++;
}
kuaipaiarr[j] = kuaipaiarr[i];
}
kuaipaiarr[i] = temp;
[self TB_KuaipaiWithArr:kuaipaiarr low:low hight:i-1];
[self TB_KuaipaiWithArr:kuaipaiarr low:i+1 hight:hight];
}
