专栏首页哈雷彗星撞地球算法之路----排序算法(上)

算法之路----排序算法(上)

排序算法在各种语言中都有已经封装好的API可使用了。但是排序算法内部怎么实现的?有哪些常用的排序算法我们还是需要了解一下的。

排序的稳定性

假设Ki = Kj(1≤ i ≤ n, 1≤ j ≤ n),且在排序前的序列中ri领先于rj(即i < j)。如果排序后ri仍领先于rj,则称所用的排序算法是稳定的;反之,若使得排序后的序列中r仍领先于ri,则称使用的排序算法是不稳定的。

简单说来,就是待排序的元素中,如果有两个值相等,排序前是a在前,b在后,排序后仍然是a在前,b在后,那么这个排序算法就是稳定的。如果排序后是b在前,a在后,那么这个排序算法就是不稳定的。

内排序和外排序

根据在排序过程中待排序的记录是否全部都被放置在内存中,排序算法又被分为内排序和外排序。

内排序是在排序整个过程中,待排序的所有记录全部被放置在内存中。外排序是由于排序的记录个数太多,不能同时放置在内存,整个排序过程需要在内外存之间多次交换数据才能进行。

根据排序过程中借助的主要操作不同,内排序可以分为:插入排序、交换排序、选择排序和归并排序。

简单排序算法

按照算法的复杂度可以分为两大类,其中冒泡排序、简单选择排序和直接插入排序属于简单算法,而希尔排序、堆排序、归并排序、快速排序属于改进算法。

简单排序算法的时间复杂度都是O(n2),在编程的发展中,曾经一度认为排序算法,无法再精进。

这里就先记录一下三种简单排序算法。

冒泡排序

冒泡排序(Bubble Sort) 是一种交换排序,它的基本思想是:两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止。

// 按照从小到大排序
// NSArray *numbers = @[@(0),@(5),@(4),@(5),@(7),@(8),@(9),@(2),@(3)];
- (NSArray *)bubbleSortWithArray:(NSArray *)array
{
    NSMutableArray *sortedArray = [NSMutableArray arrayWithArray:array];
    int count = (int)sortedArray.count;
    int i,j;
    // 因为数组的下标是从 0 至 count - 1;
    for (i = 0; i < count; i++) {
        // 因为数组下标是从 0 至 count - 1,因为j+1 最大为count -1,所以j最大为count -2
        for (j = count - 2; j >= i; j--) {
            if ([sortedArray[j] intValue] > [sortedArray[j + 1] intValue]) {
                [sortedArray exchangeObjectAtIndex:j withObjectAtIndex:j+1];
            }
        }
    }
    return [sortedArray copy];
}

上面这种算法是外层从0开始递增遍历,内层是从count-1 到i,递减遍历,可以理解为一次将最小、倒数第二小、倒数第三小.... 依次至于第0、第1、第2.....的位置。

还可以这样写:

+ (NSMutableArray *)bubbleSort:(NSMutableArray *)randomNumbers
{
    if (randomNumbers.count == 0) {
        return randomNumbers;
    }
    
    if (![randomNumbers isKindOfClass:[NSMutableArray class]]) {
        NSLog(@"参数类型错误,请使用NSMutableArray类型对象做入参");
        return nil;
    }
    
    for (int i = 0; i < randomNumbers.count; i++) {
        for (int j = 0; j < randomNumbers.count - i - 1; j++) {
            if ([randomNumbers[j] intValue] > [randomNumbers[j + 1] intValue]) {
                [randomNumbers exchangeObjectAtIndex:j withObjectAtIndex:j+1];
            }
        }
    }
    
    return randomNumbers;
}

这种写法是外层从0开始递增遍历,内层也是从0开始递增遍历,依次将最大、第2大、第3大......的元素依次放置到最后、倒数第二后、倒数第三后......的位置。

当然以上两种做法还可以针对某些特殊数据做一些优化。比如,如果数据只有最后两个元素或者只有最开始两个元素需要互换。 那么上述算法还可以再做一些优化。

如果,某次选择排序时,如果没有互换元素,这说明所有元素都已经是有序的了,以后的循环就不用再次互换了。

+ (NSMutableArray *)bubbleSort2:(NSMutableArray *)randomNumbers
{
    if (randomNumbers.count == 0) {
        return randomNumbers;
    }
    
    if (![randomNumbers isKindOfClass:[NSMutableArray class]]) {
        NSLog(@"参数类型错误,请使用NSMutableArray类型对象做入参");
        return nil;
    }
    
    BOOL flag = YES;
    for (int i = 0; i < randomNumbers.count && flag; i++) {
        flag = NO;
        for (int j = 0; j < randomNumbers.count - i - 1; j++) {
            if ([randomNumbers[j] intValue] > [randomNumbers[j + 1] intValue]) {
                [randomNumbers exchangeObjectAtIndex:j withObjectAtIndex:j+1];
                flag = YES;
            }
        }
    }
    
    return randomNumbers;
}

选择排序

选择排序(Selection Sort)就是通过 n - i 次关键字间的比较,从n - i + 1个记录中选出关键字最小的记录,并和 第 i (1≤ i ≤ n)个记录交换。

+ (NSMutableArray *)selectSort:(NSMutableArray *)randomNumbers
{
    if (randomNumbers.count == 0) {
        return randomNumbers;
    }
    
    if (![randomNumbers isKindOfClass:[NSMutableArray class]]) {
        NSLog(@"参数类型错误,请使用NSMutableArray类型对象做入参");
        return nil;
    }
    
    int min;
    for (int i = 0; i < randomNumbers.count; i ++) {
        min = i;
        for (int j = i + 1; j < randomNumbers.count; j++) {
            if ([randomNumbers[min] intValue] > [randomNumbers[j] intValue]) {
                min = j;
            }
        }
        if (i != min) {
            [randomNumbers exchangeObjectAtIndex:i withObjectAtIndex:min];
        }
    }
    
    return randomNumbers;
}

插入排序

直接插入排序(Insertion Sort)的基本操作是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增1的有序表。

+ (NSMutableArray *)insertSort:(NSMutableArray *)randomNumbers
{
    if (randomNumbers.count == 0) {
        return randomNumbers;
    }
    
    if (![randomNumbers isKindOfClass:[NSMutableArray class]]) {
        NSLog(@"参数类型错误,请使用NSMutableArray类型对象做入参");
        return nil;
    }
    
    NSUInteger count = randomNumbers.count;
    for (int i = 0; i < count; i++) {
        id temp = randomNumbers[i];
        int j;
        for (j = i - 1; j >= 0 && [randomNumbers[j]  intValue] > [temp intValue]; j--) {
            randomNumbers[j + 1] = randomNumbers[j];
        }
        randomNumbers[j + 1] = temp;
    }
    return randomNumbers;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 希尔排序

    希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效...

    Haley_Wong
  • 堆排序

    堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。 而堆是具有以下性...

    Haley_Wong
  • 快速排序

    快速排序是对冒泡排序的一种改进。 快速排序由C. A. R. Hoare在1960年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一...

    Haley_Wong
  • AI_第一部分 数据结构与算法(10.排序简介)

    第四阶段我们进行深度学习(AI),本部分(第一部分)主要是对底层的数据结构与算法部分进行详尽的讲解,通过本部分的学习主要达到以下两方面的效果:

    还是牛6504957
  • /etc/security/limits.conf的相关说明

    通过ulimit -n命令可以查看Linux系统里打开文件描述符的最大值,一般缺省值是1024,对一台繁忙的服务器来说,这个值偏小,所以有必要重新设置linux...

    拓荒者
  • “基数排序”展现Python的优雅与简洁

    在这儿那桶排序为例目的不是向大家介绍基数排序这种排序方式,是想通过基数排序的实现来展现Python的简洁与优雅。在这儿先简单的介绍一下基数排序,至于具体的内容会...

    昱良
  • 缓冲区的使用

    缓冲区是包在一个对象内的基本数据元素数组,Buffer类相比一个简单的数组的优点是它将关于数据的数据内容和信息包含在一个单一的对象中。

    Java栈
  • 设计模式之简单理解装饰器模式与运用

    ​ 装饰器模式(Decorator Pattern)允许向一个现有的对象添加新的功能,同时又不改变其结构。这种类型的设计模式属于结构型模式,它是作为...

    Dream城堡
  • Linux 日常常用指令

       最近搞了一个阿里ECS,CentOS7,涉及到一些基本的Linux指令,在这里总结一下,在搭环境中常用的一些指令,熟悉这些指令就基本能够使用CentOS进...

    Rekent
  • 算法驱动型的设计

    “Everything should be made as simple as possible, but not simpler” — Albert Eins...

    mixlab

扫码关注云+社区

领取腾讯云代金券