「多图警告」手撕排序算法 - iOS进阶必备

朴灿烈づ我的快乐病毒、 2021-11-01 09:03 199阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，一起学算法

![640][]

作者 | Lefex

来源 | 超越技术

整理 | 程序员小吴

**冒泡排序**

冒泡排序是通过比较两个相邻元素的大小实现排序，如果前一个元素大于后一个元素，就交换这两个元素。这样就会让每一趟冒泡都能找到最大一个元素并放到最后。

以 \[ 8, 1, 4, 6, 2, 3, 5, 7 \] 为例，对它进行冒泡排序：

![640?wx\_fmt=png][640_wx_fmt_png]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

代码实现：

+ (NSArray *)bubbleSort:(NSArray *)unsortDatas {    NSMutableArray *unSortArray = [unsortDatas mutableCopy];    for (int i = 0; i < unSortArray.count -1 ; i++) {        BOOL isChange = NO;        for (int j = 0; j < unSortArray.count - 1 - i; j++) {            // 比较相邻两个元素的大小，后一个大于前一个就交换            if ([unSortArray[j] integerValue] > [unSortArray[j+1] integerValue]) {                NSNumber *data = unSortArray[j+1];                unSortArray[j+1] = unSortArray[j];                unSortArray[j] = data;                isChange = YES;            }        }        if (!isChange) {            // 如果某次未发生数据交换，说明数据已排序            break;        }    }    return [unSortArray copy];}NSArray *)unsortDatas {
        
        NSMutableArray *unSortArray = [unsortDatas mutableCopy];
        for (int i = 0; i < unSortArray.count -1 ; i++) {
        
            BOOL isChange = NO;
            for (int j = 0; j < unSortArray.count - 1 - i; j++) {
        
                // 比较相邻两个元素的大小，后一个大于前一个就交换
                if ([unSortArray[j] integerValue] > [unSortArray[j+1] integerValue]) {
        
                    NSNumber *data = unSortArray[j+1];
                    unSortArray[j+1] = unSortArray[j];
                    unSortArray[j] = data;
                    isChange = YES;
                }
            }
            if (!isChange) {
        
                // 如果某次未发生数据交换，说明数据已排序
                break;
            }
        }
        return [unSortArray copy];
    }

**特点**

稳定性：它是指对同样的数据进行排序，会不会改变它的相对位置。比如 \[ 1, 3, 2, 4, 2 \] 经过排序后，两个相同的元素 2 位置会不会被交换。冒泡排序是比较相邻两个元素的大小，显然不会破坏稳定性。

空间复杂度：由于整个排序过程是在原数据上进行操作，故为 O(1);

时间复杂度：由于嵌套了 2 层循环，故为 O(n\*n);

**选择排序**

选择排序的思想是，依次从「无序列表」中找到一个最小的元素放到「有序列表」的最后面。以 arr = \[ 8, 1, 4, 6, 2, 3, 5, 4 \] 为例，排序开始时把 arr 分为有序列表 A = \[ \], 无序列表 B = \[ 8, 1, 4, 6, 2, 3, 5, 4 \]，依次从 B 中找出最小的元素放到 A 的最后面。这种排序也是逻辑上的分组，实际上不会创建 A 和 B，只是用下标来标记 A 和 B。

以 arr = \[ 8, 1, 4, 6, 2, 3, 5, 4 \] 为例，第一次找到最小元素 1 与 8 进行交换，这时有列表 A = \[1\], 无序列表 B = \[8, 4, 6, 2, 3, 5, 4\]；第二次从 B 中找到最小元素 2，与 B 中的第一个元素进行交换，交换后 A = \[1，2\]，B = \[4, 6, 8, 3, 5, 4\]；就这样不断缩短 B，扩大 A，最终达到有序。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 2]

代码实现：

+ (NSArray *)seelectSort:(NSArray *)unsortDatas {    NSMutableArray *unSortArray = [unsortDatas mutableCopy];    for (int i = 0; i < unSortArray.count; i++) {        int mindex = i;        for (int j = i; j < unSortArray.count; j++) {            // 找到最小元素的index            if ([unSortArray[j] integerValue] < [unSortArray[mindex] integerValue]) {                mindex = j;            }        }        // 交换位置        NSNumber *data = unSortArray[i];        unSortArray[i] = unSortArray[mindex];        unSortArray[mindex] = data;    }    return [unSortArray copy];}NSArray *)unsortDatas {
        
        NSMutableArray *unSortArray = [unsortDatas mutableCopy];
        for (int i = 0; i < unSortArray.count; i++) {
        
            int mindex = i;
            for (int j = i; j < unSortArray.count; j++) {
        
                // 找到最小元素的index
                if ([unSortArray[j] integerValue] < [unSortArray[mindex] integerValue]) {
        
                    mindex = j;
                }
            }
            // 交换位置
            NSNumber *data = unSortArray[i];
            unSortArray[i] = unSortArray[mindex];
            unSortArray[mindex] = data;
        }
        return [unSortArray copy];
    }

**特点**

稳定性：排序过程中元素是按顺序进行遍历，相同元素相对位置不会发生变化，故稳定。

空间复杂度：在原序列进行操作，故为 O( 1 );

时间复杂度：需要 2 次循环遍历，故为 O( n \* n );

**插入排序**

在整个排序过程如图所示，以 arr = \[ 8, 1, 4, 6, 2, 3, 5, 7\] 为例，它会把 arr 分成两组 A = \[ 8 \] 和 B = \[ 1, 4, 6, 2, 3, 5, 7\] ，逐步遍历 B 中元素插入到 A 中，最终构成一个有序序列：

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 3]代码实现：

+ (NSArray *)insertionSort:(NSArray *)unsortDatas {    NSMutableArray *unSortArray = [unsortDatas mutableCopy];    int preindx = 0;    NSNumber *current;    for (int i = 1; i < unSortArray.count; i++) {        preindx = i - 1;        // 必须记录这个元素，不然会被覆盖掉        current = unSortArray[i];        // 逆序遍历已经排序好的数组        // 当前元素小于排序好的元素，就移动到下一个位置        while (preindx >= 0 && [current integerValue] < [unSortArray[preindx] integerValue] ) {            // 元素向后移动            unSortArray[preindx+1] = unSortArray[preindx];            preindx -= 1;        }        // 找到合适的位置，把当前的元素插入        unSortArray[preindx+1] = current;    }    return [unSortArray copy];}NSArray *)unsortDatas {
        
        NSMutableArray *unSortArray = [unsortDatas mutableCopy];
        int preindx = 0;
        NSNumber *current;
        for (int i = 1; i < unSortArray.count; i++) {
        
            preindx = i - 1;
            // 必须记录这个元素，不然会被覆盖掉
            current = unSortArray[i];
            // 逆序遍历已经排序好的数组
    
            // 当前元素小于排序好的元素，就移动到下一个位置
            while (preindx >= 0 && [current integerValue] < [unSortArray[preindx] integerValue] ) {
        
                // 元素向后移动
                unSortArray[preindx+1] = unSortArray[preindx];
                preindx -= 1;
            }
            // 找到合适的位置，把当前的元素插入
            unSortArray[preindx+1] = current;
        }
        return [unSortArray copy];
    }

**特点**

稳定性：它是从后往前遍历已排序好的序列，相同元素不会改变位置，故为稳定排序；  
空间复杂度：它是在原序列进行排序，故为 O ( 1 );

时间复杂度：排序的过程中，首先要遍历所有的元素，然后在已排序序列中找到合适的位置并插入。共需要 2 层循环，故为 O ( n \* n );

**希尔排序**

希尔排序，它是由 D.L.Shell 于1959 年提出而得名。根据它的名字很难想象算法的核心思想。\[ 所以只能死记硬背了，面试官问：希尔排序的思想是什么？\]。它的核心思想是把一个序列分组，对分组后的内容进行[**插入排序**][Link 1]，这里的分组只是逻辑上的分组，不会重新开辟存储空间。它其实是插入排序的优化版，插入排序对基本有序的序列性能好，希尔排序利用这一特性把原序列分组，对每个分组进行排序，逐步完成排序。

以 arr = \[ 8, 1, 4, 6, 2, 3, 5, 7 \] 为例，通过 floor(8/2) 来分为 4 组，8 表示数组中元素的个数。分完组后，对组内元素进行插入排序。

「 第1次分组 」

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 4]

「 利用第 1 次分组结果进行第 2 次分组 」

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 5]

「 利用第 2 次分组结果进行最后一次分组 」

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 6]

代码实现：

+ (NSArray *)shellSort:(NSArray *)unsortDatas {    NSMutableArray *unSortArray = [unsortDatas mutableCopy];    // len = 9    int len = (int)unSortArray.count;    // floor 向下取整，所以 gap的值为：4，2，1    for (int gap = floor(len / 2); gap > 0; gap = floor(gap/2)) {        // i=4;i<9;i++ (4,5,6,7,8)        for (int i = gap; i < len; i++) {            // j=0,1,2,3,4            // [0]-[4] [1]-[5] [2]-[6] [3]-[7] [4]-[8]            for (int j = i - gap; j >= 0 && [unSortArray[j] integerValue] > [unSortArray[j+gap] integerValue]; j-=gap) {                // 交换位置                NSNumber *temp = unSortArray[j];                unSortArray[j] = unSortArray[gap+j];                unSortArray[gap+j] = temp;            }        }    }    return [unSortArray copy];}NSArray *)unsortDatas {
        
        NSMutableArray *unSortArray = [unsortDatas mutableCopy];
        // len = 9
        int len = (int)unSortArray.count;
        // floor 向下取整，所以 gap的值为：4，2，1
        for (int gap = floor(len / 2); gap > 0; gap = floor(gap/2)) {
        
            // i=4;i<9;i++ (4,5,6,7,8)
            for (int i = gap; i < len; i++) {
        
                // j=0,1,2,3,4
                // [0]-[4] [1]-[5] [2]-[6] [3]-[7] [4]-[8]
                for (int j = i - gap; j >= 0 && [unSortArray[j] integerValue] > [unSortArray[j+gap] integerValue]; j-=gap) {
        
                    // 交换位置
                    NSNumber *temp = unSortArray[j];
                    unSortArray[j] = unSortArray[gap+j];
                    unSortArray[gap+j] = temp;
                }
            }
        }
        return [unSortArray copy];
    }

**特点**

稳定性：它可能会把相同元素分到不同的组中，那么两个相同的元素就有可能调换相对位置，故不稳定。

空间复杂度：由于整个排序过程是在原数据上进行操作，故为 O(1);

时间复杂度：希尔排序的时间复杂度与增量序列的选取有关，例如希尔增量时间复杂度为O(n²)，而Hibbard增量的希尔排序的时间复杂度为O(log n的3/2)，希尔排序时间复杂度的下界是n\*log2n

**快速排序**

快速排序的核心思想是对待排序序列通过一个「支点」（支点就是序列中的一个元素，别把它想的太高大上）进行拆分，使得左边的数据小于支点，右边的数据大于支点。然后把左边和右边再做一次递归，直到递归结束。支点的选择也是一门大学问，我们以 （左边index + 右边index）/ 2 来选择支点。

以 arr = \[ 8, 1, 4, 6, 2, 3, 5, 7 \] 为例，选择一个支点, index= (L+R)/2 = (0+7)/2=3, 支点的值 pivot = arr\[index\] = arr\[3\] = 6，接下来需要把 arr 中小于 6 的移到左边，大于 6 的移到右边。

快速排序使用一个高效的方法做数据拆分。

用一个指向左边的游标 i，和指向右边的游标 j，逐渐移动这两个游标，直到找到 arr\[i\] > 6 和 arr\[j\] < 6, 停止移动游标，交换 arr\[i\] 和 arr\[j\]，交换完后 i++，j--（对下一个元素进行比较），直到 i>=j，停止移动。

图中的 L，R 是指快速排序开始时序列的起始和结束索引，在一趟快速排序中，它们的值不会发生改变，直到下一趟排序时才会改变。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 7]

一趟快速排序完成后，分别对小于6和大于等于6的部分进行快速排序，递归就好了。对 \[ 5, 1, 4, 3, 2 \] 进行一趟快速排序。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 8]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 9]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 10]

代码实现：

/** 快速排序 @param unSortArray 待排序序列 @param lindex 待排序序列左边的index @param rIndex 待排序序列右边的index @return 排序结果 */+ (NSArray *)quickSort:(NSMutableArray *)unSortArray leftIndex:(NSInteger)lindex rightIndex:(NSInteger)rIndex {    NSInteger i = lindex; NSInteger j = rIndex;    // 取中间的值作为一个支点    NSNumber *pivot = unSortArray[(lindex + rIndex) / 2];    while (i <= j) {        // 向左移动，直到找打大于支点的元素        while ([unSortArray[i] integerValue] < [pivot integerValue]) {            i++;        }        // 向右移动，直到找到小于支点的元素        while ([unSortArray[j] integerValue] > [pivot integerValue]) {            j--;        }        // 交换两个元素，让左边的大于支点，右边的小于支点        if (i <= j) {            // 如果 i== j，交换个啥？            if (i != j) {                NSNumber *temp = unSortArray[i];                unSortArray[i] = unSortArray[j];                unSortArray[j] = temp; }            i++;            j--;        }    }    // 递归左边，进行快速排序    if (lindex < j) {        [self quickSort:unSortArray leftIndex:lindex rightIndex:j];    }    // 递归右边，进行快速排序    if (i < rIndex) {        [self quickSort:unSortArray leftIndex:i rightIndex:rIndex];    }    return [unSortArray copy];}
    + (NSArray *)quickSort:(NSMutableArray *)unSortArray leftIndex:(NSInteger)lindex rightIndex:(NSInteger)rIndex {
        
        NSInteger i = lindex; NSInteger j = rIndex;
        // 取中间的值作为一个支点
        NSNumber *pivot = unSortArray[(lindex + rIndex) / 2];
        while (i <= j) {
        
            // 向左移动，直到找打大于支点的元素
            while ([unSortArray[i] integerValue] < [pivot integerValue]) {
        
                i++;
            }
            // 向右移动，直到找到小于支点的元素
            while ([unSortArray[j] integerValue] > [pivot integerValue]) {
        
                j--;
            }
            // 交换两个元素，让左边的大于支点，右边的小于支点
            if (i <= j) {
        
                // 如果 i== j，交换个啥？
                if (i != j) {
        
                    NSNumber *temp = unSortArray[i];
                    unSortArray[i] = unSortArray[j];
                    unSortArray[j] = temp; }
                i++;
                j--;
            }
        }
        // 递归左边，进行快速排序
        if (lindex < j) {
        
            [self quickSort:unSortArray leftIndex:lindex rightIndex:j];
        }
        // 递归右边，进行快速排序
        if (i < rIndex) {
        
            [self quickSort:unSortArray leftIndex:i rightIndex:rIndex];
        }
        return [unSortArray copy];
    }

**归并排序**

归并排序，采用分治思想，先把待排序序列拆分成一个个子序列，直到子序列只有一个元素，停止拆分，然后对每个子序列进行边排序边合并。其实，从名字「归并」可以看出一丝「拆、合」的意思（妄加猜测）。

以 arr = \[ 8, 1, 4, 6, 2, 3, 5, 7 \] 为例，排序需要分两步：

a、「**拆**」，以 length/2 拆分为 A = \[ 8, 1, 4, 6 \] ，B = \[ 2, 3, 5, 7 \]，继续对 A 和 B 进行拆分，A1 = \[ 8, 1 \] 、A2 = \[ 4, 6 \]、B1 = \[ 2, 3 \]、B2 = \[ 5, 7 \]，继续拆分，直到只有一个元素，A11 = \[ 8 \] , A12= \[ 1 \] 、A21 = \[ 4 \]、A22 = \[ 6 \]、B11 = \[ 2 \]、B12 = \[ 3 \]、B21 = \[ 5 \]、B22 = \[ 7 \]。

b、「**合**」，对单个元素的序列进行合并，A11和A12合并为\[ 1, 8 \], A21 和 A22 合并为 \[ 4, 6 \]，等等。在合并的过程中也需要排序。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 11]

代码实现：

+ (NSArray *)mergeSort:(NSArray *)unSortArray {    NSInteger len = unSortArray.count;    // 递归终止条件    if (len <= 1) {        return unSortArray;    }    NSInteger mid = len / 2;    // 对左半部分进行拆分    NSArray *lList = [self mergeSort:[unSortArray subarrayWithRange:NSMakeRange(0, mid)]];    // 对右半部分进行拆分    NSArray *rList = [self mergeSort:[unSortArray subarrayWithRange:NSMakeRange(mid, len-mid)]];    // 递归结束后执行下面的语句    NSInteger lIndex = 0;    NSInteger rIndex = 0;    // 进行合并    NSMutableArray *results = [NSMutableArray array];    while (lIndex < lList.count && rIndex < rList.count) {        if ([lList[lIndex] integerValue] < [rList[rIndex] integerValue]) {            [results addObject:lList[lIndex]];            lIndex += 1;        } else {            [results addObject:rList[rIndex]];            rIndex += 1;        }    }    // 把左边剩余元素加到排序结果中    if (lIndex < lList.count) {        [results addObjectsFromArray:[lList subarrayWithRange:NSMakeRange(lIndex, lList.count-lIndex)]];    }    // 把右边剩余元素加到排序结果中    if (rIndex < rList.count) {        [results addObjectsFromArray:[rList subarrayWithRange:NSMakeRange(rIndex, rList.count-rIndex)]];    }    return results;}NSArray *)unSortArray {
        
        NSInteger len = unSortArray.count;
        // 递归终止条件
        if (len <= 1) {
        
            return unSortArray;
        }
        NSInteger mid = len / 2;
        // 对左半部分进行拆分
        NSArray *lList = [self mergeSort:[unSortArray subarrayWithRange:NSMakeRange(0, mid)]];
        // 对右半部分进行拆分
        NSArray *rList = [self mergeSort:[unSortArray subarrayWithRange:NSMakeRange(mid, len-mid)]];
        // 递归结束后执行下面的语句
        NSInteger lIndex = 0;
        NSInteger rIndex = 0;
        // 进行合并
        NSMutableArray *results = [NSMutableArray array];
        while (lIndex < lList.count && rIndex < rList.count) {
        
            if ([lList[lIndex] integerValue] < [rList[rIndex] integerValue]) {
        
                [results addObject:lList[lIndex]];
                lIndex += 1;
            } else {
        
                [results addObject:rList[rIndex]];
                rIndex += 1;
            }
        }
        // 把左边剩余元素加到排序结果中
        if (lIndex < lList.count) {
        
            [results addObjectsFromArray:[lList subarrayWithRange:NSMakeRange(lIndex, lList.count-lIndex)]];
        }
        // 把右边剩余元素加到排序结果中
        if (rIndex < rList.count) {
        
            [results addObjectsFromArray:[rList subarrayWithRange:NSMakeRange(rIndex, rList.count-rIndex)]];
        }
        return results;
    }

**特点**

稳定性：在元素拆分的时候，虽然相同元素可能被分到不同的组中，但是合并的时候相同元素相对位置不会发生变化，故稳定。

空间复杂度：需要用到一个数组保存排序结果，也就是合并的时候，需要开辟空间来存储排序结果，故为 O ( n );

时间复杂度：最好最坏都为 O(nlogn);

**计数排序**

前面所讲的 6 种排序都是基于「比较」的思想，总是在比较两个元素的大小，然后交换位置。

现在来换个“口味”，来看看计数排序。

计数排序的核心思想是把一个无序序列 A 转换成另一个有序序列 B，从 B 中逐个“取出”所有元素，取出的元素即为有序序列「没看明白，不急，后面来张图就搞明白了」。这种算法比快速排序还要快「特定条件下」，它适用于待排序序列中元素的取值范围比较小。比如对某大型公司员工按年龄排序，年龄的取值范围很小，大约在（10-100）之间。

对数组 arr = \[ 8, 1, 4, 6, 2, 3, 5, 4 \] 进行排序，使用计数排序需要找到与其对应的一个有序序列，可以使用数组的下标与 arr 做一个映射「数组的下标恰好是有序的」。

遍历 arr，把 arr 中的元素放到 counArr 中，counArr 的大小是由 arr 中最大元素和最小元素决定的。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 12]

图中有个技巧，为了让 countArr 尽可能地小，countArr 的长度使用了 arr 中的最大值 max - arr 中的最小值 min + 1 （max - min + 1），arr\[i\] - min 恰好是 countArr 的下标。countArr 中记录了某个值出现的次数，比如 8 出现过 1 次，则在 countArr 中的值为 1；4 出现过 2 次，则在 countArr 中的值为 2。

代码实现：

+ (NSArray *)countingSort:(NSArray *)datas {    // 1.找出数组中最大数和最小数    NSNumber *max = [datas firstObject];    NSNumber *min = [datas firstObject];    for (int i = 0; i < datas.count; i++) {        NSNumber *item = datas[i];        if ([item integerValue] > [max integerValue]) {            max = item;        }        if ([item integerValue] < [min integerValue]) {            min = item;        }    }    // 2.创建一个数组 countArr 来保存 datas 中元素出现的个数    NSInteger sub = [max integerValue] - [min integerValue] + 1;    NSMutableArray *countArr = [NSMutableArray arrayWithCapacity:sub];    for (int i = 0; i < sub; i++) {        [countArr addObject:@(0)];    }    // 3.把 datas 转换成 countArr，使用 datas[i] 与 countArr 的下标对应起来    for (int i = 0; i < datas.count; i++) {        NSNumber *aData = datas[i];        NSInteger index = [aData integerValue] - [min integerValue];        countArr[index] = @([countArr[index] integerValue] + 1);    }    // 4.从countArr中输出结果    NSMutableArray *resultArr = [NSMutableArray arrayWithCapacity:datas.count];    for (int i = 0; i < countArr.count; i++) {        NSInteger count = [countArr[i] integerValue];        while (count > 0) {            [resultArr addObject:@(i + [min integerValue])];            count -= 1;        }    }    return [resultArr copy];}// 1.找出数组中最大数和最小数
        NSNumber *max = [datas firstObject];
        NSNumber *min = [datas firstObject];
        for (int i = 0; i < datas.count; i++) {
        
            NSNumber *item = datas[i];
            if ([item integerValue] > [max integerValue]) {
        
                max = item;
            }
            if ([item integerValue] < [min integerValue]) {
        
                min = item;
            }
        }
        // 2.创建一个数组 countArr 来保存 datas 中元素出现的个数
        NSInteger sub = [max integerValue] - [min integerValue] + 1;
        NSMutableArray *countArr = [NSMutableArray arrayWithCapacity:sub];
        for (int i = 0; i < sub; i++) {
        
            [countArr addObject:@(0)];
        }
        // 3.把 datas 转换成 countArr，使用 datas[i] 与 countArr 的下标对应起来
        for (int i = 0; i < datas.count; i++) {
        
            NSNumber *aData = datas[i];
            NSInteger index = [aData integerValue] - [min integerValue];
            countArr[index] = @([countArr[index] integerValue] + 1);
        }
        // 4.从countArr中输出结果
        NSMutableArray *resultArr = [NSMutableArray arrayWithCapacity:datas.count];
        for (int i = 0; i < countArr.count; i++) {
        
            NSInteger count = [countArr[i] integerValue];
            while (count > 0) {
        
                [resultArr addObject:@(i + [min integerValue])];
                count -= 1;
            }
        }
        return [resultArr copy];
    }

**特点**

稳定性：在元素往 countArr 中记录时按顺序遍历，从 countArr 中取出元素也是按顺序取出，相同元素相对位置不会发生变化，故稳定。

空间复杂度：需要额外申请空间，复杂度为“桶”的个数，故为 O ( k )， k 为“桶”的个数，也就是 countArr 的长度;

时间复杂度：最好最坏都为 O(n+k)， k 为“桶”的个数，也就是 countArr 的长度;

**桶排序**

以 arr = \[ 8, 1, 4, 6, 2, 3, 5, 7 \] 为例，排序前需要确定桶的个数，和确定桶中元素的取值范围：

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 13]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 14]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 15]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 16]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 17]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 18]

代码实现：

+ (NSArray *)bucketSort:(NSArray *)datas {    // 1.找出数组中最大数和最小数    NSNumber *max = [datas firstObject];    NSNumber *min = [datas firstObject];    for (int i = 0; i < datas.count; i++) {        NSNumber *item = datas[i];        if ([item integerValue] > [max integerValue]) {            max = item;        }        if ([item integerValue] < [min integerValue]) {            min = item;        }    }    // 2.创建桶，桶的个数为 3    int maxBucket = 3;    NSMutableArray *buckets = [NSMutableArray arrayWithCapacity:maxBucket];    for (int i = 0; i < maxBucket; i++) {        NSMutableArray *aBucket = [NSMutableArray array];        [buckets addObject:aBucket];    }    // 3.把数据分配到桶中，桶中的数据是有序的    // a.计算桶中数据的平均值，这样分组数据的时候会把数据放到对应的桶中    float space = ([max integerValue] - [min integerValue] + 1) / (maxBucket*1.0);    for (int i = 0; i < datas.count; i++) {        // b.根据数据值计算它在桶中的位置        int index = floor(([datas[i] integerValue] - [min integerValue]) / space);        NSMutableArray *bucket = buckets[index];        int maxCount = (int)bucket.count;        NSInteger minIndex = 0;        for (int j = maxCount - 1; j >= 0; j--) {            if ([datas[i] integerValue] > [bucket[j] integerValue]) {                minIndex = j+1;                break;            }        }        [bucket insertObject:datas[i] atIndex:minIndex];    }    // 4.把桶中的数据重新组装起来    NSMutableArray *results = [NSMutableArray array];    [buckets enumerateObjectsUsingBlock:^(NSArray *obj, NSUInteger idx, BOOL * _Nonnull stop) {        [results addObjectsFromArray:obj];    }];    return results;}NSArray *)datas {
        
        // 1.找出数组中最大数和最小数
        NSNumber *max = [datas firstObject];
        NSNumber *min = [datas firstObject];
        for (int i = 0; i < datas.count; i++) {
        
            NSNumber *item = datas[i];
            if ([item integerValue] > [max integerValue]) {
        
                max = item;
            }
            if ([item integerValue] < [min integerValue]) {
        
                min = item;
            }
        }
        // 2.创建桶，桶的个数为 3
        int maxBucket = 3;
        NSMutableArray *buckets = [NSMutableArray arrayWithCapacity:maxBucket];
        for (int i = 0; i < maxBucket; i++) {
        
            NSMutableArray *aBucket = [NSMutableArray array];
            [buckets addObject:aBucket];
        }
        // 3.把数据分配到桶中，桶中的数据是有序的
        // a.计算桶中数据的平均值，这样分组数据的时候会把数据放到对应的桶中
        float space = ([max integerValue] - [min integerValue] + 1) / (maxBucket*1.0);
        for (int i = 0; i < datas.count; i++) {
        
            // b.根据数据值计算它在桶中的位置
            int index = floor(([datas[i] integerValue] - [min integerValue]) / space);
            NSMutableArray *bucket = buckets[index];
            int maxCount = (int)bucket.count;
            NSInteger minIndex = 0;
            for (int j = maxCount - 1; j >= 0; j--) {
        
                if ([datas[i] integerValue] > [bucket[j] integerValue]) {
        
                    minIndex = j+1;
                    break;
                }
            }
            [bucket insertObject:datas[i] atIndex:minIndex];
        }
        // 4.把桶中的数据重新组装起来
        NSMutableArray *results = [NSMutableArray array];
        [buckets enumerateObjectsUsingBlock:^(NSArray *obj, NSUInteger idx, BOOL * _Nonnull stop) {
        
            [results addObjectsFromArray:obj];
        }];
    
        return results;
    }

**特点**

稳定性：在元素拆分的时候，相同元素会被分到同一组中，合并的时候也是按顺序合并，故稳定。

空间复杂度：桶的个数加元素的个数，为 O ( n + k );

时间复杂度：最好为 O( n + k )，最坏为 O（n \* n）;

**基数排序**

基数排序是从待排序序列找出可以作为排序的「关键字」，按照「关键字」进行多次排序，最终得到有序序列。比如对 100 以内的序列 arr = \[ 3, 9, 489, 1, 5, 10, 2, 7, 6, 204 \]进行排序，排序关键字为「个位数」、「十位数」和「百位数」这 3 个关键字，分别对这 3 个关键字进行排序，最终得到一个有序序列。

以 arr = \[ 3, 9, 489, 1, 5, 10, 2, 7, 6, 204 \] 为例，最大为 3 位数，分别对个、十、百位进行排序，最终得到的序列就是有序序列。可以把 arr 看成 \[ 003, 009, 489, 001, 005, 010, 002, 007, 006, 204 \]，这样理解起来比较简单。

数字的取值范围为 0-9，故可以分为 10 个桶。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 19]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 20]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 18]

代码实现：

+ (NSArray *)radixSort:(NSArray *)datas {    NSMutableArray *tempDatas;    NSInteger maxValue = 0;    int maxDigit = 0;    int level = 0;    do {        // 1.创建10个桶        NSMutableArray *buckets = [NSMutableArray array];        for (int i = 0; i < 10; i++) {            NSMutableArray *array = [NSMutableArray array];            [buckets addObject:array];        }        // 2.把数保存到桶中        for (int i = 0; i < datas.count; i++) {            NSInteger value = [datas[i] integerValue];            // 求一个数的多次方            int xx = (level < 1 ? 1 : (pow(10, level)));            // 求个位数、十位数....            int mod = value / xx  % 10;            [buckets[mod] addObject:datas[i]];            // 求最大数为了计算最大数            if (maxDigit == 0) {                if (value > maxValue) {                    maxValue = value;                }            }        }        // 3.把桶中的数据重新合并        tempDatas = [NSMutableArray array];        for (int i = 0; i < 10; i++) {            NSMutableArray *aBucket = buckets[i];            [tempDatas addObjectsFromArray:aBucket];        }        // 4.求出数组中最大数的位数, 只需计算一次        if (maxDigit == 0) {            while(maxValue > 0){                maxValue = maxValue / 10;                maxDigit++;            }        }        // 5.继续下一轮排序        datas = tempDatas;        level += 1;    } while (level < maxDigit);    return tempDatas;}NSArray *)datas {
        
        NSMutableArray *tempDatas;
        NSInteger maxValue = 0;
        int maxDigit = 0;
        int level = 0;
        do {
        
            // 1.创建10个桶
            NSMutableArray *buckets = [NSMutableArray array];
            for (int i = 0; i < 10; i++) {
        
                NSMutableArray *array = [NSMutableArray array];
                [buckets addObject:array];
            }
            // 2.把数保存到桶中
            for (int i = 0; i < datas.count; i++) {
        
                NSInteger value = [datas[i] integerValue];
                // 求一个数的多次方
                int xx = (level < 1 ? 1 : (pow(10, level)));
                // 求个位数、十位数....
                int mod = value / xx  % 10;
                [buckets[mod] addObject:datas[i]];
                // 求最大数为了计算最大数
                if (maxDigit == 0) {
        
                    if (value > maxValue) {
        
                        maxValue = value;
                    }
                }
            }
            // 3.把桶中的数据重新合并
            tempDatas = [NSMutableArray array];
            for (int i = 0; i < 10; i++) {
        
                NSMutableArray *aBucket = buckets[i];
                [tempDatas addObjectsFromArray:aBucket];
    
            }
            // 4.求出数组中最大数的位数, 只需计算一次
            if (maxDigit == 0) {
        
                while(maxValue > 0){
        
                    maxValue = maxValue / 10;
                    maxDigit++;
                }
            }
            // 5.继续下一轮排序
            datas = tempDatas;
            level += 1;
    
        } while (level < maxDigit);
    
        return tempDatas;
    }

**特点**

稳定性：在元素拆分的时候，相同元素会被分到同一组中，合并的时候也是按顺序合并，故稳定。

空间复杂度：O ( n + k );

时间复杂度：最好最坏都为 O( n \* k );

**总结**

以上就是 iOS 中的十大经典排序算法，仔细阅读一番理解之后，能助你在 iOS 的算法笔试环节一臂之力。

ps：我在前几年开源了一个项目：**在Object-C中学习数据结构与算法之排序算法，**如果你是 iOS 开发者，可以在 GitHub 上 **https://github.com/MisterBooo/Play-With-Sort-OC** 获取可调试运行的源码。

![640][640 1]

--------------------

**本文相关阅读推荐：**

[毕业十年后，我忍不住出了一份程序员的高考试卷][Link 2]

[一道腾讯面试题：厉害了我的杯][Link 3]

[十大经典排序算法动画与解析，看我就够了][Link 4]

[这或许是东半球分析十大排序算法最好的一篇文章][Link 5]

[面试官，我会写二分查找法！对，没有 bug 的那种！][bug]

[看《长安十二时辰》可以了解哪些算法知识][Link 6]

GitHub 标星 3w+，很全面的算法和数据结构知识

--------------------

![640?wx\_fmt=png][640_wx_fmt_png 1]

[640]: /images/20211101/e2dd35c43afd4176b0f3e8b4b0b5111d.png
[640_wx_fmt_png]: /images/20211101/4de90f59be414fda96b5b8b0ac2bf3e1.png
[640_wx_fmt_jpeg]: /images/20211101/bfa93091dfb04c5d85547d079d56f9f0.png
[640_wx_fmt_jpeg 1]: /images/20211101/8bf11eb67ab143a3a488802143eb858c.png
[640_wx_fmt_jpeg 2]: /images/20211101/dac9c5a250024bf4af4301569d0b92e3.png
[640_wx_fmt_jpeg 3]: /images/20211101/60c04c462acd4d99894fe2298f976293.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUzMTk3ODc0OA==&mid=2247483828&idx=1&sn=d8f0675f4e54e3b273c90c59be54eaeb&chksm=fabb0127cdcc883158bb0791f26cae1ea8494b496744f802b22babb4c03eaaef25e98dfbff57&scene=21#wechat_redirect
[640_wx_fmt_jpeg 4]: /images/20211101/9cf9f598ea6c44d1930f45c721ec79de.png
[640_wx_fmt_jpeg 5]: /images/20211101/c040aa2db1f142808777db1cf5b3ae03.png
[640_wx_fmt_jpeg 6]: /images/20211101/ed0d8d53ff6f4a56ab71ea7d086542b6.png
[640_wx_fmt_jpeg 7]: /images/20211101/f7b657ad6eaf463f9f36d05bf1c3173a.png
[640_wx_fmt_jpeg 8]: /images/20211101/d4dece7e9309487881e66c800e4bb0b0.png
[640_wx_fmt_jpeg 9]: /images/20211101/770d17d3d2d847f191554518d12f8ea8.png
[640_wx_fmt_jpeg 10]: /images/20211101/e25269804eed4e149bad2bc15f3894cd.png
[640_wx_fmt_jpeg 11]: /images/20211101/98164be100284d3caf3743ea75729ff1.png
[640_wx_fmt_jpeg 12]: /images/20211101/4d58212a1ede4fd68387c9f60edb22c5.png
[640_wx_fmt_jpeg 13]: /images/20211101/39b3a1a80d334c0884cae25ef1dcef27.png
[640_wx_fmt_jpeg 14]: /images/20211101/5a2d0d4bf94647b3ba28f5eb2febe920.png
[640_wx_fmt_jpeg 15]: /images/20211101/47da128ba5e843299805796bc6dbe5d1.png
[640_wx_fmt_jpeg 16]: /images/20211101/e2cce578c81843ee9b825c47b303fd7c.png
[640_wx_fmt_jpeg 17]: /images/20211101/6a030e24fa5f441fa4b284a532772636.png
[640_wx_fmt_jpeg 18]: /images/20211101/2100f38511374321af2524c8433844d9.png
[640_wx_fmt_jpeg 19]: /images/20211101/5073a60a080f4109a8c3acd2661f7424.png
[640_wx_fmt_jpeg 20]: /images/20211101/6ca1db4646af4b6fa896ca7c9b2e0d46.png
[640 1]: /images/20211101/57a3b1a548c64e31809a15fd26c5ff05.png
[Link 2]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/91488249
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484557&idx=1&sn=739d80488fe1169a9c9ca26ecfcdfba6&chksm=fa0e6b0ccd79e21a1c2b0d99db69f6206cddddfe2367742e9de1d7d17ec35a5ce29fa4e30d63&scene=21#wechat_redirect
[Link 4]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/87910210
[Link 5]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/92825279
[bug]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485240&idx=1&sn=fbccc747b2e8558c6478171709005ff9&chksm=fa0e68b9cd79e1af5ab68d42adea0b24c7d4867069091df9e95b6f20ab57b69c4e38994a36be&scene=21#wechat_redirect
[Link 6]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485904&idx=1&sn=0eae783ce1b7c0383f41d76a269f511e&chksm=fa0e6651cd79ef47d31a0dba6909873974a964e81654cf702e3868da51fa9a695e7b9a383c1a&scene=21#wechat_redirect
[640_wx_fmt_png 1]: /images/20211101/74e412c55c134f0782369d46926bc328.png