iOS排序算法

冒泡排序:两两作比较,最大(或者最小)的值放在最后

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;
}