iOS 算法

/**
 快速排序

 @param list 输入排序数组
 */
- (void)quickSort:(NSMutableArray *)list
{
    NSInteger startIndex = 0;
    NSInteger endIndex = list.count-1;
    [self sortList:list withStartIndex:startIndex endInde:endIndex];
    NSLog(@"quick sort=%@",list);

}
- (void)sortList:(NSMutableArray *)list withStartIndex:(NSInteger)startIndex endInde:(NSInteger)endIndex
{
    NSInteger i = startIndex;
    NSInteger j = endIndex;
    if (i >= j) {
        return;
    }
    int temp = [list[i] intValue];
    while (i < j) {
        while (i <j && [list[j] intValue] >= temp) {
            j --;
        }

        [list exchangeObjectAtIndex:i withObjectAtIndex:j];
        temp = [list[j] intValue];
        while (i <j && [list[i] intValue] <=temp) {
            i ++;
        }
        [list exchangeObjectAtIndex:i withObjectAtIndex:j];
    }
    [self sortList:list withStartIndex:startIndex endInde:i-1];
    [self sortList:list withStartIndex:i+1 endInde:endIndex];
}

// 70 20 30 50 80 10 90 40 60

/**
 堆排序

 @param list 输入排序数组
 */
- (void)heapSort:(NSMutableArray *)list
{
    NSInteger i,size;
    size = list.count;
    for (i = list.count/2; i>=0; i--) {
        [self createBinggerHeap:list withSize:size beIndex:i];
    }
    while (size>0) {
        [list exchangeObjectAtIndex:size-1 withObjectAtIndex:0];
        size --;
        [self createBinggerHeap:list withSize:size beIndex:0];
    }
    NSLog(@"list=%@",list);
}
// element = 3 size = 9
- (void)createBinggerHeap:(NSMutableArray *)list withSize:(NSInteger)size beIndex:(NSInteger)element
{
    NSInteger lchild = element*2+1;
    NSInteger rchild = lchild+1;
    while (rchild < size){
        if(list[element] >= list[lchild] && list[element] >= list[rchild]) return;
        if (list[lchild] >list[rchild]) {
            [list exchangeObjectAtIndex:element withObjectAtIndex:lchild];
            element = lchild;
        }else {
            [list exchangeObjectAtIndex:element withObjectAtIndex:rchild];
            element = rchild;
        }
        lchild = element *2 +1;
        rchild = lchild+1;
    }
    if (lchild<size && list[lchild] >list[element]) {
        [list exchangeObjectAtIndex:lchild withObjectAtIndex:element];
    }
}


- (void)sortArray
{
    NSMutableArray *arr = [NSMutableArray arrayWithObjects:@"12",@"38",@"26",@"11",@"98", nil];
    NSLog(@"排序前数组:%@",arr);
    // 选择排序 (n-1)! 4!= 4+3+2+1
    int count=0;
    for (int i = 0; i<=arr.count-1; i++) {
        for (int j = i+1; j<=arr.count-1; j++) {
            count ++;
            if ([arr[j] intValue] < [arr[i] intValue]) {
                int temp = [arr[i] intValue];
                arr[i] = arr[j];
                arr[j] = [NSString stringWithFormat:@"%d",temp];
            }
        }
    }
    NSLog(@"排序后数组:%@ count=%d",arr,count);
    NSMutableArray *arr1 = [NSMutableArray arrayWithObjects:@"12",@"38",@"26",@"11",@"98", nil];
    NSLog(@"排序前数组:%@",arr1);

    //冒泡排序
    int count1=0;
    for (int i = 0; i<arr1.count-1; i++) {
        for (int j =0; j<arr1.count-i-1; j++) {
            count1 ++;
            if ([arr1[j] intValue] > [arr1[j+1] intValue]) {
                int temp = [arr1[j] intValue];
                arr1[j] = arr1[j+1];
                arr1[j+1] = [NSString stringWithFormat:@"%d",temp];
            }
        }
    }
    NSLog(@"排序后数组:%@ count=%d",arr1,count1);


    //插入排序
    NSMutableArray *list = [NSMutableArray arrayWithObjects:@"15",@"25",@"5",@"95",@"85", nil];
    NSLog(@"排序前数组list:%@",list);

    for (int i = 1; i<list.count; i++) {
        int j = i;
        NSInteger temp = [[list objectAtIndex:i] integerValue];
        while (j>0&&temp<[[list objectAtIndex:j-1] integerValue]) {
            [list replaceObjectAtIndex:j withObject:[list objectAtIndex:j-1]];
            j--;
        }
        [list replaceObjectAtIndex:j withObject:[NSNumber numberWithInteger:temp]];
    }
    NSLog(@"排序后数组list:%@",list);

    //希尔排序
    NSMutableArray *list1 = [NSMutableArray arrayWithObjects:@"9",@"8",@"7",@"6",@"5",@"4",@"3",@"2",@"1", nil];
    NSLog(@"排序前数组list1:%@",list1);
    int gap = list1.count/2.0;
    while (gap >= 1) {

        for (int i=gap; i<list1.count; i++) {
            NSInteger temp = [list1[i] integerValue];
            int j=i;
            while (j>=gap && temp< [list1[j-gap] integerValue]) {
                [list1 replaceObjectAtIndex:j withObject:list1[j-gap]];
                j -= gap;
            }

            [list1 replaceObjectAtIndex:j withObject:[NSString stringWithFormat:@"%ld",temp]];
        }
        gap /= 2;
    }
    NSLog(@"排序后数组list1:%@",list1);

}