刘浩的技术博客

就当是做个笔记,顺便分享一些知识,更希望业界的交流

经典排序算法

插入排序

将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增1的有序表。将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增1的有序表。实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
- (NSArray *)insertSort:(NSMutableArray *)array {
    int i,j;
    NSNumber *temp;

    for (i = 1; i<array.count; i++) {
        j = i - 1;
        temp = array[i];

        while (j >= 0 && [temp compare:array[j]] == NSOrderedAscending) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = temp;
    }

    return [array copy];

}

希尔排序

将待排序的记录分成几组,从而减少参与直接插入排序的数据量,当经过几次分组之后,记录的排列已经基本有序,这时再对所有记录实施直接插入排序。 通过设置间隔来把元素分成多个组来进行插入排序,当间隔为1时序列基本有序,然后对整个序列进行插入排序,这样需要移动的元素很少了。比如有十个元素,假如间隔为5,那么就是把元素分成了五组来分别插入排序。实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
- (NSArray *)shellSort:(NSMutableArray *)array {
    int i,j,d;
    NSNumber *temp;
    for (d = (int)(array.count/2); d >= 1; d = d/2) {
        for (i = d; i < (int)array.count; i++) {
            j = i - d;
            temp = array[i];

            while (j >= 0 && [temp compare:array[j]] == NSOrderedAscending) {
                array[j + d] = array[j];
                j = j - d;
            }
            array[j + d] = temp;
        }
    }

    return [array copy];
}

冒泡排序

两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止。 对比相邻的两个项,比较然后交换,直到选取一个最小的数,然后在n-1个元素里以此选出此小的数,以此类推直到全部有序为止。实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
- (NSArray *)bubbleSort:(NSMutableArray *)array {
    int i,j;
    NSNumber *temp;

    for (i = 0; i < array.count - 1; i++) {
        for (j = (i+1);j < array.count; j++) {
            if ([array[i] compare:array[j]] == NSOrderedDescending) {
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
    }

    return [array copy];
}

快速排序

  1. 获取中轴元素
  2. i从左至右扫描,如果小于基准元素,则i自增,否则记下a[i]
  3. j从右至左扫描,如果大于基准元素,则i自减,否则记下a[j]
  4. 交换a[i]和a[j] 5.重复这一步骤直至i和j交错,然后和基准元素比较,然后交换。

可以定义一个基准数任意位置元素都可以。把小于基准数的数字放到左边,把大于基准数的数字放到右边。(代码实现时先从序列最右边向左边找比基准数小的数,找到了可以先放在基准数位置(一开始用临时变量保存基准数),反正一个循环下来基准数到最后会放在别的位置。然后从序列最左边向右找比基准数大的数,找到放在前面留下的坑位,然后从右边坑位开始向右找比基准数小的数,找到放在前面留下的坑位,知道左右两边找到同一个位置时把基准数放在这个位置,用递归方法分别对基准数左右两部分用同样的方式,直到最后),实现代码如下:

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
- (NSArray *)quickSort:(NSMutableArray *)array {
    [self partitionOfQuickSort:array low:0 high:(int)(array.count - 1)];

    return [array copy];
}

- (void)partitionOfQuickSort:(NSMutableArray *)array low:(int)low high:(int)high {
    if (low < high) {
        int i = low;
        int j = high;
        NSNumber *temp = array[i];

        while (i < j) {
            while (i < j && [temp compare:array[j]] == NSOrderedAscending) {
                j--;
            }

            array[i] = array[j];

            while (i < j && [temp compare:array[i]] == NSOrderedDescending) {
                i++;
            }

            array[j] = array[i];
        }

        array[i] = temp;


        [self partitionOfQuickSort:array low:0 high:i - 1];
        [self partitionOfQuickSort:array low:i + 1 high:high];
    }
}

简单选择排序

第一趟从所有的n个记录中选择最小的记录放在第一位,第二趟从n-1个记录中选择最小的记录放到第二位。以此类推,经过n-1趟排序之后,整个待排序序列就成为有序序列了。 从一个无序序列里选出最小的数放在第一位,然后选出第二小的数放在第二位,以此类推,直到序列有序。实现的时候可以多加一个参数记录最小位置的索引。(因为是一个个找的,所以一旦找到比其小的数,那么此数字前面的数字一定比其大,所以可以记录索引从此开始再搜索,以此类推直到找到最小索引为止)。实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
- (NSArray *)simpleSelectSort:(NSMutableArray *)array {
    int i,j,k;
    NSNumber *temp;
    for (i = 0; i< (array.count - 1); i++) {
        k = i;
        for (j = i + 1; j < array.count; j++) {
            if ([array[k] compare:array[j]] == NSOrderedDescending) {
                k = j;
            }
        }

        if (i != k) {
            temp = array[i];
            array[i] = array[k];
            array[k] = temp;
        }
    }


    return [array copy];
}

二路归并排序

如果初始序列含有n个记录,则可以看成是n个有序的子序列,每个子序列的长度为1,然后两两归并,得到(表示不小于x的最小整数)个长度为2或1的有序子序列;再两两归并,……,如此重复,直至得到一个长度为n的有序序列为止。 对于两个有序的序列使用合并排序,把较小的值放入临时数组(如i与j序列对比,如i序列元素较小则放入临时数组,然后i下移一个元素继续对比,j类似。),然后接着对比,直到一个序列的值都放入的临时的数组,那么另外序列的只需要一次放入临时数组就好了(因为两个序列本身就有序了。)。实现代码如下:

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
- (NSArray *)mergingSort:(NSMutableArray *)array {
    [self merging:array low:0 high:(int)(array.count - 1)];
    return [array copy];
}

- (void)merging:(NSMutableArray *)array low:(int)low high:(int)high {
    if (low < high) {
        int mid = (low + high)/2;
        [self merging:array low:low high:mid]; //left
        [self merging:array low:mid + 1 high:high]; //right
        [self mergeSort:array low:low mid:mid high:high];

    }
}

- (void)mergeSort:(NSMutableArray *)array low:(int)low mid:(int)mid high:(int)high {
    int i= low,j=mid + 1;
    NSMutableArray *tempArray = [NSMutableArray new];

    while (i <= mid && j <= high) {
        if ([array[i] compare:array[j]] == NSOrderedDescending) {
            [tempArray addObject:array[i]];
            i++;
        }
        else {
            [tempArray addObject:array[j]];
            j++;
        }
    }

    while (i <= mid) {
        [tempArray addObject:array[i]];
        i++;
    }
    while (j <= high) {
        [tempArray addObject:array[j]];
        j++;
    }

    for (NSNumber *temp in tempArray) {
        array[low] = temp;
        low++;
    }
}