冒泡排序:两两作比较,最大(或者最小)的值放在最后
NSArray *arr = @[@23,@43,@18,@89,@14,@78,@65,@87,@99];
//冒泡排序
for(int i=0;i<arr.count - 1;i++){//遍历次数
for(int j=0;j<arr.count-i-1;j++){
if(arr[j]>arr[j+1]){//如果条件满足相邻元素交换顺序
int tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
for (int n=0; n< sizeof(arr)/sizeof(arr[0]); n ++) {
printf("冒泡排序:%d\n",arr[n]);
}
简单选择排序-通过索引
选择排序:每次循环遍历选择最小(或者最大)的值,
for(int i=0;i<arr.count-1;i++){ //遍历次数
for(int j=i+1;j<arr.count;j++){
if(arr[i]>arr[j]){//每次遍历选择最小的值与索引为i元素交换
int tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
}
}
}
折半查找
//折半查找
- (int)findKey:(NSArray *)arr arrCount:(int)length findNum:(int)key{
int min = 0;
int max = length;
int mid = 0;
while (min <= max) {
mid = (min+max)/2;
int midNum = [(NSNumber *)arr[mid] intValue];
if (key >midNum) {
min = mid +1;
}else if (key < midNum){
max = mid-1;
}else{
return mid;
}
}
return -1;
}
快速排序
原理:
1 ）.设置两个变量i，j ，排序开始时i = 0，就j = mutableArray.count - 1；
2 ）.设置数组的第一个值为比较基准数key，key = mutableArray.count[0]；
3 ）.因为设置key为数组的第一个值，所以先从数组最右边开始往前查找比key小的值。如果没有找到，j--继续往前搜索；如果找到则将mutableArray[i]和mutableArray[j]互换，并且停止往前搜索，进入第4步；
4 ）.从i位置开始往后搜索比可以大的值，如果没有找到，i++继续往后搜索；如果找到则将mutableArray[i]和mutableArray[j]互换，并且停止往后搜索；
5 ）.重复第3、4步，直到i == j（此时刚好执行完第三步或第四部），停止排序；
- (void)quickSortArray:(NSMutableArray *)array withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex
{
if (leftIndex >= rightIndex) {//如果数组长度为0或1时返回
return ;
}
NSInteger i = leftIndex;
NSInteger j = rightIndex;
//记录比较基准数
NSInteger key = [array[i] integerValue];
while (i < j) {
/**** 首先从右边j开始查找比基准数小的值 ***/
while (i < j && [array[j] integerValue] >= key) {//如果比基准数大，继续查找
j--;
}
//如果比基准数小，则将查找到的小值调换到i的位置
array[i] = array[j];
/**** 当在右边查找到一个比基准数小的值时，就从i开始往后找比基准数大的值 ***/
while (i < j && [array[i] integerValue] <= key) {//如果比基准数小，继续查找
i++;
}
//如果比基准数大，则将查找到的大值调换到j的位置
array[j] = array[i];
}
//将基准数放到正确位置
array[i] = @(key);
/**** 递归排序 ***/
//排序基准数左边的
[self quickSortArray:array withLeftIndex:leftIndex andRightIndex:i - 1];
//排序基准数右边的
[self quickSortArray:array withLeftIndex:i + 1 andRightIndex:rightIndex];
}
递归算法:阶乘
- (int)recursiveCaculate:(int)i{
if (i == 0) {
return 1;
}else{
return i * [self recursiveCaculate:i-1];
}
}
随机生成10000个数，随机数在0~99,计算出现次数最多数
- (void)viewDidLoad {
[super viewDidLoad];
NSMutableArray *mutabl = [NSMutableArray array];
for (int i =0 ; i < 10000; i++) {
int randomNum = arc4random()%99;
NSNumber *num = [NSNumber numberWithInt:randomNum];
[mutabl addObject:num];
}
int maxNum = [self selectAppearNumCount:mutabl];
}
- (int)selectAppearNumCount:(NSMutableArray *)mutablArr{
int maxCount = 1;
int maxNum = 0;
NSMutableDictionary *dict = [NSMutableDictionary dictionary];
for (NSNumber *num in mutablArr) {
NSString *keyNum = [NSString stringWithFormat:@"%d",num.intValue];
NSNumber *countNum = [dict objectForKey:keyNum];
if (countNum) {
int count = countNum.intValue;
count +=1;
if (count>maxCount) {
maxCount = count;
maxNum = num.intValue;
}
}else{
[dict setObject:[NSNumber numberWithInt:1] forKey:keyNum];
}
}
NSLog(@"最大数---%d,最大次数----%d",maxCount,maxNum);
return maxNum;
}
