iOS简单的排序算法

发表于 | 阅读次数

排序

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#pragma mark - 插入算法
- (NSArray *)insertSortArray:(NSArray *)originArray
{
    NSMutableArray * sortArr = [originArray mutableCopy];
    int j;
    NSNumber * temp;
    
    for (int i = 1; i < sortArr.count; i ++)
    {
        temp = sortArr[i];
        j = i - 1;
        while (j > -1 && [temp compare:sortArr[j]] == NSOrderedAscending)
        {
            sortArr[j + 1] = sortArr[j];
            j --;
        }
        sortArr[j + 1] = temp;
    }
    return sortArr;
}

描述

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

算法复杂度

如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需（n-1）次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有 n(n-1)/2次 。插入排序的赋值操作是比较操作的次数加上 (n-1）次。平均来说插入排序算法的时间复杂度为O(n^2）。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择

稳定性

插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#pragma mark - 希尔排序
- (NSArray *)shellSortArray:(NSArray *)originArray
{
    NSMutableArray * sortArray = [originArray mutableCopy];
    NSInteger  count = originArray.count;
    [self shellSortArray:sortArray count:count];
    return sortArray;
}
- (void)shellSortArray:(NSMutableArray *)array count:(NSInteger)count
{
    NSInteger i,j,gap;
    
    for (gap = count / 2; gap > 0; gap /= 2)//步长
    {
        for (i = gap; i < count; i ++)//直接插入
        {
            NSNumber * temp = array[i];
            for (j = i - gap; j >= 0 && [array[j] compare:array[j + gap]] == NSOrderedDescending; j -= gap) {
                array[j + gap] = array[j];
            }
            array[j + gap] = temp;
        }
    }
}

描述

希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因DL．Shell于1959年提出而得名
基本思想：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率较高。
以n=10的一个数组 3,2,5,8,6,0,1,4,9,7为例（位置间隔为gap的为同一组，每次对同一组的数据进行直接插入排序）
第一次 gap = 10 / 2 = 5 分为五组(3,0),(2,1),(5,4),(8,9) ,(6,7) 排序完为 (0,3),(1,2),(4,5),(8,9) ,(6,7)
3 2 5 8 6 0 1 4 9 7 → 0 1 4 8 6 3 2 5 9 7
第二次 gap = 5 / 2 = 2 分为两组(0,4,6,2,9),(1,8,3,5,7) 排序完为 (0,2,4,6,9),(1,3,5,7,8)
0 1 4 8 6 3 2 5 9 7 → 0 1 2 3 4 5 6 7 9 8
第三次 gap = 2 / 2 = 1 分为一组(0,1,2,3,4,5,6,7,9,8) 排序完为(0,1,2,3,4,5,6,7,8,9)
0 1 2 3 4 5 6 7 9 8 → 0 1 2 3 4 5 6 7 8 9
第四次 gap = 1 / 2 = 0 排序完成得到数组
0 1 2 3 4 5 6 7 8 9

归并算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#pragma mark - 归并算法
- (NSArray *)mergeSortArray:(NSArray *)array
{
    NSMutableArray * tempArray = [NSMutableArray arrayWithCapacity:array.count];
    NSMutableArray * sortArray = [array mutableCopy];
    [self mergeSortArray:sortArray tempArray:tempArray startIndex:0 endIndex:sortArray.count - 1];
    return sortArray;
}
- (void)mergeSortArray:(NSMutableArray *)array  tempArray:(NSMutableArray *)tempArray startIndex:(NSInteger)startIndex endIndex:(NSInteger)endIndex
{
    if (startIndex >= endIndex) return;
    NSInteger middleIndex = (endIndex - startIndex) / 2 + startIndex;
    [self mergeSortArray:array tempArray:tempArray startIndex:startIndex endIndex:middleIndex];
    [self mergeSortArray:array tempArray:tempArray startIndex:middleIndex + 1 endIndex:endIndex];
    [self mergeSortArray:array tempArray:tempArray startIndex:startIndex middleIndex:middleIndex endIndex:endIndex];
}
- (void)mergeSortArray:(NSMutableArray *)array tempArray:(NSMutableArray *)tempArray startIndex:(NSInteger)startIndex middleIndex:(NSInteger)middleIndex endIndex:(NSInteger)endIndex
{
    for (NSInteger i = startIndex; i <= endIndex; i ++)
    {
        tempArray[i]  = array[i];
    }
    NSInteger leftIndex = startIndex;
    NSInteger rightIndex = middleIndex + 1;
    NSInteger currentIndex = startIndex;
    
    while (leftIndex <= middleIndex && rightIndex <= endIndex)
    {
        if ([tempArray[leftIndex] compare:tempArray[rightIndex]] != NSOrderedDescending)
        {
            array[currentIndex] = tempArray[leftIndex];
            leftIndex ++;
        }else
        {
            array[currentIndex] = tempArray[rightIndex];
            rightIndex ++;
        }
        currentIndex ++;
    }
    if (middleIndex - leftIndex >= 0) {
        for (int i = 0; i <= middleIndex - leftIndex; i ++)
        {
            array[currentIndex + i] = tempArray[leftIndex + i];
        }
    }
}

定义

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

描述

1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2.设定两个指针，最初位置分别为两个已经排序序列的起始位置
3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针超出序列尾
4.将另一序列剩下的所有元素直接复制到合并序列尾

算法复杂度

时间复杂度为O(nlog₂n) 这是该算法中最好、最坏和平均的时间性能。
空间复杂度为 O(n)
比较操作的次数介于(nlogn) / 2和nlogn - n + 1。
赋值操作的次数是(2nlogn)。归并算法的空间复杂度为：0 (n)
归并排序比较占用内存，但却是一种效率高(仅次于快速排序)且稳定的算法。

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#pragma mark - 冒泡排序
- (NSArray *)bubbleSortArray:(NSArray *)originArray
{
    NSMutableArray * sortArray = [originArray mutableCopy];
    NSNumber * temp;
    NSInteger count = originArray.count;
    for (int j = 0; j < count; j ++)
    {
        for (int i = 0; i < count - 1 - j; i ++)
        {
            if ([sortArray[i] compare:sortArray[i + 1]] == NSOrderedDescending)
            {
                temp = sortArray[i];
                sortArray[i] = sortArray[i + 1];
                sortArray[i + 1] = temp;
            }
        }
    }
    return sortArray;
}

描述

1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

算法复杂度

平均时间复杂度也是：O(n^2)
最优的情况下时间复杂度为：O(n)
最差的情况下时间复杂度为：O(n^2)

稳定性

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#pragma mark - 快速排序
- (NSArray *)quickSortArray:(NSArray *)originArray
{
    NSMutableArray * sortArray = [originArray mutableCopy];
    [self quickSortArray:sortArray left:0 right:originArray.count - 1];
    return sortArray;
}
- (void)quickSortArray:(NSMutableArray *)array left:(NSInteger)left right:(NSInteger)right
{
    if (left >= right) return;
    
    NSInteger i = left;
    NSInteger j = right;
    NSNumber * key = array[left];
    
    while (i < j)
    {
        while (i < j && [key compare:array[j]] == NSOrderedAscending)
        {//而寻找结束的条件就是，1，找到一个小于或者大于key的数（大于或小于取决于你想升序还是降序）2，没有符合条件1的，并且i与j的大小没有反转
            j --;//向前寻找
        }
        
        array[i] = array[j];
        //找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是array[left]，那么就是给key）
        
        while (i < j && [key compare:array[i]] == NSOrderedDescending)
        {//这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反,因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反
            i ++;
        }
        array[j] = array[i];
    }
    array[i] = key;//当在当组内找完一遍以后就把中间数key回归
    [self quickSortArray:array left:left right:i - 1];//最后用同样的方式对分出来的左边的小组进行同上的做法
    [self quickSortArray:array left:i + 1 right:right];//用同样的方式对分出来的右边的小组进行同上的做法
}

描述

快速排序是对冒泡排序的一种改进。
一趟快速排序的算法是：
1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索(j–)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；
5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。

算法复杂度

快速排序的平均时间复杂度也是：O(nlogn)
快速排序最优的情况下时间复杂度为：O( nlogn )
最差的情况下时间复杂度为：O( n^2 )
最优的情况下空间复杂度为：O(logn) ；每一次都平分数组的情况
最差的情况下空间复杂度为：O( n ) ；退化为冒泡排序的情况

选择排序

#pragma mark - 选择排序
- (NSArray *)selectSortArray:(NSArray *)originArray
{
    NSMutableArray * sortArray = [originArray mutableCopy];
    NSNumber * min;
    for (NSInteger i = 0; i < sortArray.count - 1; i ++)
    {
        min = sortArray[i];
        for (NSInteger j = i + 1; j < sortArray.count; j ++)
        {
            if ([min compare:sortArray[j]] == NSOrderedDescending) {
                NSNumber * temp = sortArray[j];
                sortArray[j] = min;
                min = temp;
            }
        }
        sortArray[i] = min;
    }
    return sortArray;
}

描述

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

时间复杂度

选择排序的交换操作介于 0 和 (n - 1） 次之间。选择排序的比较操作为 n (n - 1） / 2 次之间。选择排序的赋值操作介于 0 和 3 (n - 1） 次之间。比较次数O(n^2），比较次数与关键字的初始状态无关，总的比较次数N=(n-1）+(n-2）+…+1=n*(n-1）/2。交换次数O(n），最好情况是，已经有序，交换0次；最坏情况交换n-1次，逆序交换n/2次。交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。