iOS - 排序

一、冒泡排序

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

1.算法过程：

（1）比较相邻的元素。如果第一个比第二个大，就交换它们两个；
（2）对每一对相邻元素作同样的操作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
（3）针对所有的元素重复以上的步骤，除了最后一个；
（4）重复步骤1~3，直到没有任何一对数字需要比较。

2.复杂度

假设序列有 n 个元素，(n>1)，根据算法步骤，第 1 轮 需在 n 个元素中两两比较 (n-1) 次，第 2 轮 需要在剩余的 (n-1) 个元素中两两比较 (n-2) 次，第(n-1) 轮需在最后 2 个元素中仅比较 1 次。
函数表达式为：
f(n) = (n-1) + (n-2) +...+ 2 + 1
f(n) = [1+(n-1)]×(n-1)/2
f(n) = n*(n-1)/2
f(n) = (n² - n)/2

用 大 O 表示法，忽略常量、低阶和常数系数。
时间复杂度为：O(n²)
空间复杂度为：并未开辟额外空间，所以为 O(1)
稳定性: 稳定

3.代码

    NSMutableArray *array = [NSMutableArray arrayWithObjects:@45,@3,@22,@23,@40,@34, nil];
    for (int i = 0; i < array.count - 1; i ++) {//循环array.count-1次
        for (int j = 0; j < array.count - 1 ; j ++) {
            if ([array[j] integerValue] >[array[j+1] integerValue] ) {
                [array exchangeObjectAtIndex:j withObjectAtIndex:j+1];
            }
        }
    }
    NSLog(@"%@",array);

这样写的冒泡排序需要比对（数组的个数-1）的平方次，每一圈内循环都把最大的数换到最后，如上：第一圈 45 被替换到最后一个元素位置，第二圈 40 被替换到倒数第二个元素的位置，那么 40 和 45 还需要比对么，答案是否定的，所以可以对上述方法进行第一次优化：

    NSMutableArray *array = [NSMutableArray arrayWithObjects:@45,@3,@22,@23,@40,@34, nil];
    for (int i = 0; i < array.count - 1; i ++) {//循环array.count-1次
        for (int j = 0; j < array.count - 1 - i; j ++) {
            if ([array[j] integerValue] >[array[j+1] integerValue] ) {
                [array exchangeObjectAtIndex:j withObjectAtIndex:j+1];
            }
        }
    }
    NSLog(@"%@",array);

当循环结束前，数组已经排好顺序了，那么后面的比较就没有必要了，可以跳出循环。继续优化结果：

    for (int i = 0; i < array.count - 1; i ++) {//循环array.count-1次
        BOOL isEnd = NO;//判断是否已排序完成
        for (int j = 0; j < array.count -1 -i; j++) {
            if ([array[j] integerValue] >[array[j+1] integerValue] ) {
                isEnd = YES;
                [array exchangeObjectAtIndex:j withObjectAtIndex:j+1];
            }
        }
        if (!isEnd) {
            break;
        }

    }
    NSLog(@"%@",array);

二、选择排序

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

1.算法过程

（1）首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
（2）再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
（3）重复第二步，直到所有元素均排序完毕。

2.复杂度

假设序列有 n 个元素（n>1），根据算法步骤，第 1 轮 需在 n 个元素中遍历 n 次查找到最小的元素，第2轮 需在剩余的 (n-1) 个元素中遍历 (n-1) 次找到最小的元素，… 第 n-1 轮 需在剩余的 2 个元素中找到最小的元素，第 n 轮剩余 1 个元素放在已排序元素的末尾。

函数表达式为：
f(n) = n+(n-1)+…+2+1
f(n) = (n+1)*n/2
f(n) = (n²+n)/2

用 大 O 表示法，忽略常量、低阶和常数系数。
时间复杂度为：O(n²)
空间复杂度为：并未开辟额外空间，所以为 O(1)
稳定性: 不稳定

3.代码

    int count = 0;
    NSMutableArray *array = [NSMutableArray arrayWithObjects:@3,@2,@9,@1,@6,@7,@4,@5,@8,nil];
        for (int i = 0; i<array.count - 1; i++) {
            NSInteger min = [array[i] integerValue];
            NSInteger index = i;
            for (NSInteger j= i+1; j< array.count; j++) {
                
                if (min > [array[j] integerValue]) {
                    min = [array[j] integerValue];
                    index = j;
                }
                count ++;
            }
            [array exchangeObjectAtIndex:index withObjectAtIndex:i];
        }
    NSLog(@"排序后的数组===%@",array);
    NSLog(@"循环次数count=%d",count);

优化：在循环选取时，每次扫描未排序区间分别选择最小、最大值放于数组始、末位置

    NSMutableArray *array = [NSMutableArray arrayWithObjects:@3,@2,@9,@1,@6,@7,@4,@5,@8,@5,nil];
    for (int i = 0; i<array.count - 1; i++) {
        NSInteger min = [array[i] integerValue];
        NSInteger max = [array[array.count - 1 - i] integerValue];
                
        NSInteger minIndex = i;
        NSInteger maxIndex = array.count - 1 - i;

        if(minIndex +1 == maxIndex||minIndex == maxIndex){
            break;
        }
        for (NSInteger j= i+1; j< array.count-i; j++) {

            if (min > [array[j] integerValue]) {
                min = [array[j] integerValue];
                minIndex = j;
            }
            if (max < [array[j] integerValue]) {
                max = [array[j] integerValue];
                maxIndex = j;
            }
        }

        [array exchangeObjectAtIndex:minIndex withObjectAtIndex:i];
        [array exchangeObjectAtIndex:maxIndex withObjectAtIndex:array.count - i - 1];

    }
    NSLog(@"排序后的数组===%@",array);

4.不稳定性

选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第 n-1个元素，第 n 个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列 5,8,5,3,6，我们知道第一遍选择第 1 个元素 5 会和 3 交换，那么原序列中两个 5 的 相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。

三、插入排序

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。可以形象地比喻成打扑克牌的时候整理牌的顺序的方法。

1.算法过程描述

（1）从第一个元素开始，该元素可以认为已经被排序；
（2）取出下一个元素作为新元素，在已经排序的元素序列中从后向前扫描；
（3）如果该元素（已排序）大于新元素，将该元素移到下一位置；
（4）重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
（5）将新元素插入到该位置后；
（6）重复步骤2~5。

2.复杂度

假设序列有 n 个元素（n>1），根据算法步骤，第 1 轮取第2个元素插入到已排序数列（1个元素）中，第 2 轮取 第3个元素插入到已排序数列（有2个元素）中，… 第 (n-1) 轮取第n个元素插入到已排序数列（有(n-1)` 个元素）中。

函数表达式为：
f(n) = 1+2+…+(n-1)
f(n) = n*(n-1)/2
f(n) = (n²-n)/2

用 大 O 表示法，忽略常量、低阶和常数系数。
时间复杂度为：O(n²)
空间复杂度为：并未开辟额外空间，所以为O(1)
稳定性: 稳定

3.代码

    NSMutableArray *array = [NSMutableArray arrayWithObjects:@3,@2,@9,@1,@6,@7,@4,@5,@8,@5,nil];
    for (int i = 0; i<array.count ; i++) {
        NSInteger valueI = [array[i] integerValue];
        for (int j= i - 1; j >= 0; j--) {
            
            NSInteger valueJ = [array[j] integerValue];
            if(valueI < valueJ){
                [array exchangeObjectAtIndex:i withObjectAtIndex:j];
                i = j;
            }
        }
    }
    NSLog(@"排序后的数组===%@",array);

四、快速排序

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
基本思想是，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

1.算法过程描述

（1）从数列中挑出一个元素，称为 “基准”（pivot）；
（2）重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
（3）递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r之间的任意一个数据作为 pivot(分区点), 我们遍历 p 到r之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到r 之间是大于 pivot 的。
剩下，可以用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到 r之间的数据，直到区间缩小为 1，就说明所有的数据都有序了。

2.复杂度

用 大O 表示法，忽略常量、低阶和常数系数。
时间复杂度为：最坏 O(n²) ， 最好 O(nlogn)
空间复杂度为：并未开辟额外空间，所以为 O(1)
稳定性: 不稳定

3.代码

- (void)viewDidLoad {
    [super viewDidLoad];
    self.view.backgroundColor = [UIColor whiteColor];

    NSMutableArray *array = [NSMutableArray arrayWithObjects:@3,@2,@9,@1,@6,@7,@4,@5,@8,@5,nil];
    [self quickSortArray:array withLeftIndex:0 andRightIndex:(int)array.count - 1];
    NSLog(@"排序后的数组===%@",array);
}

 
//快速排序
- (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];
}

4.稳定性

如果数组中有两个相同的元素，比如测试的序列 6，8，7，6，3，5，9，4 在经过第一次分区操作之后，两个 6 的相对先后顺序就会改变。所以，快速排序并不是一个稳定的排序算法。

5.快速排序的性能分析

最好的情况下, 选择的 pivot 都很合适，正好能将大区间对等地一分为二。这时快排的时间复杂度递推求解公式跟归并是相同的。即为 O(nlogn)。

最坏的情况下，有序数组中，每次选择最后一个元素作为 pivot，那每次分区得到的两个区间都是不均等的。我们需要进行大约 n 次分区操作，才能完成快排的整个过程。每次分区我们平均要扫描大约 n/2 个元素，快排的时间复杂度就从 O(nlogn) 退化成了 O(n2)。

T(n) 在大部分情况下的时间复杂度都可以做到 O(nlogn)，只有在极端情况下，才会退化到 O(n2)。