Objective-C

一、冒泡排序

核心思想:
通过与相邻元素的比较和交换，把最大的数交换到最后面。

/**
 5, 3, 8, 6, 4  (开始)
 第一趟___(冒泡出最大值8)
 3, 5, 8, 6, 4 （5和3交换）
 3, 5, 8, 6, 4 （5和8不用交换）
 3, 5, 6, 8, 4 （8和6交换）
 3, 5, 6, 4, 8 （8和4交换）
 第二趟___(冒泡出最大值6)
 3, 5, 6, 4, 8 （3和5不用交换）
 3, 5, 6, 4, 8 （5和6不用交换）
 3, 5, 4, 6, 8 （6和4交换）
 第三趟___(冒泡出最大值5)
 3, 5, 4, 6, 8 （3和5不用交换）
 3, 4, 5, 6, 8 （5和4交换）
 第四趟___(冒泡出最大值4)
 3, 4, 5, 6, 8  (3和4不用交换)
 */
NSMutableArray *array = [NSMutableArray arrayWithObjects:@5, @3, @8, @6, @4, nil];
    for (int i = 0; i < array.count - 1; ++i) {
        for (int j = 0; j < array.count - i - 1; ++j) {
            if (array[j] > array[j + 1]) {
                NSNumber *temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }

    NSLog(@"冒泡排序后：%@",array);
    //输出:   冒泡排序后：(3, 4, 5, 6, 8)

二、 选择排序

核心思想:
选出最小的数与第1个位置的数交换，然后从剩下的数中再找出最小的数与第2个位置的数交换，依次类推。

/**
 5, 3, 8, 6, 4  (开始)
 第一趟___(最小值3交换到第1个位置)
 3, 5, 8, 6, 4 （5和3交换）
 3, 5, 8, 6, 4 （3和8不用交换）
 3, 5, 8, 6, 4 （3和6不用交换）
 3, 5, 8, 6, 4 （3和4不用交换）
 第二趟___(最小值4交换到第2个位置)
 3, 5, 8, 6, 4  (5和8不用交换)
 3, 5, 8, 6, 4  (5和6不用交换)
 3, 4, 8, 6, 5  (5和4交换)
 第三趟___(最小值5交换到第3个位置)
 3, 4, 6, 8, 5  (8和6交换)
 3, 4, 5, 8, 6  (6和5交换)
 第四趟___(最小值6交换到第4个位置)
 3, 4, 5, 6, 8  (8和6交换)
 */
NSMutableArray *array = [NSMutableArray arrayWithObjects:@5, @3, @8, @6, @4, nil];    
    for (int i = 0; i < array.count; ++i) {
        for (int j = i + 1; j < array.count; ++j) {
            if (array[i] > array[j]) {
                NSNumber *temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
    }

    NSLog(@"选择排序后：%@",array);
    //输出:   选择排序后：(3, 4, 5, 6, 8)

三、 插入排序

核心思想:
找到合适位置插入元素，插入位置后移。

/**
 5, 3, 8, 6, 4  (开始)
 第一趟
 3, 5, 8, 6, 4 （3插入 下标0位置）
 第二趟
 3, 5, 8, 6, 4 （3插入 下标2位置）
 第三趟
 3, 5, 6, 8, 4 （6插入 下标2位置）
 第四趟
 3, 4, 5, 6, 8 （4插入 下标1位置）
 */

NSMutableArray *array = [NSMutableArray arrayWithObjects:@5, @3, @8, @6, @4, nil];
    for (int i = 1; i < array.count; i++) {
        int j = i;
        NSNumber *insertValue = array[i];
        while (j > 0 && insertValue < array[j - 1]) {
            array[j] = array[j - 1];
            j--;
        }
        array[j] = insertValue;
    }

    NSLog(@"插入排序后：%@", array);
    //输出:   选择排序后：(3, 4, 5, 6, 8)

四、快速排序

核心思想:
冒泡+二分法+分治。

/**
 5, 3, 8, 6, 4  (开始)
 第一趟(基准: 5)
 4, 3, 8, 6, 4 (小)
 4, 3, 8, 6, 8 (大)
 4, 3, 8, 6, 8 (小)
 4, 3, 8, 6, 8 (大)
 4, 3, 5, 6, 8 (中间)
 第二趟(基准: 4)
 3, 3, 5, 6, 8 (小)
 3, 3, 5, 6, 8 (大)
 3, 4, 5, 6, 8 (中间)
 第三趟(基准: 6)
 3, 4, 5, 6, 8 (小)
 3, 4, 5, 6, 8 (大)
 3, 4, 5, 6, 8 (中间)
 */

    NSMutableArray *array = [NSMutableArray arrayWithObjects:@5, @3, @8, @6, @4, nil];  
    int end = [[NSNumber numberWithInteger:array.count - 1] intValue];
    [self quickSort:array start:0 end:end];

    NSLog(@"选择排序后：%@", array);
    //输出:   选择排序后：(3, 4, 5, 6, 8)


- (void)quickSort:(NSMutableArray *)array start:(int)start end:(int)end{
    //递归结束
    if (start >= end){
        return;
    }
    int index = [self indexQuickSort:array left:start right:end];
    [self quickSort:array start:start end:index - 1];
    [self quickSort:array start:index + 1 end:end];
}

- (int)indexQuickSort:(NSMutableArray *)array left:(int)left right:(int)right{
    NSNumber *keyValue = array[left];       //基准值
    while (left < right) {
        while (left < right && array[right] >= keyValue) {
            right--;
        }
        array[left] = array[right];         //小的换到左边
        while (left < right && array[left] <= keyValue) {
            left++;
        }
        array[right] = array[left];         //大的换到右边
    }
    array[left] = keyValue;                 //基准换到中间
    return left;
}