常见几种排序

一、比较类排序

通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlog2n)，因此也称为非线性时间比较类排序。

1、冒泡排序、选择排序

冒泡排序：每轮冒泡操作使得最大元素在队尾，进行 n-1轮。
选择排序：每轮选择出最小元素在队首，进行n-1轮。
这两种算法时间复杂度均为：O(n2)，不消耗额外空间，适用于常规数据排序。

2、插入排序

工作原理：通过构建有序队列，对于未排序元素，在已排序队列中从后向前扫描，找到相应位置并插入。
算法思路：选取第一个元素看做排序好的的基准队列，然后从剩余元素从左往右一个一个插入该队列中。
算法实现如下：

- (void)sortObjectsInInsertingWithArr:(NSMutableArray *)arr {

    // 取第一个元素作为排序好的队列，每次插入一个元素到排序好的队列
    for (NSInteger i = 1; i < arr.count; i++) {

        // 排序好的队列元素为 i个
        // 待插入元素为 arr[i]
        // 那么插入之后队列元素为 i+1个

        NSInteger j = i;

        // 从排好的队列后边插入
        while (j > 0 && [arr[j] integerValue] < [arr[j - 1] integerValue]) {
            [arr exchangeObjectAtIndex:j withObjectAtIndex:j-1];
            j--;
        }
    }
}

平均时间复杂度为：O(n2)，最好时间复杂度：O(n)，最差时间复杂度：O(n2)，不消耗额外空间。适用于基本排序好的队列，不适合基本逆序排列的队列。

3、快速排序

基本思想：通过一轮排序将待排队列分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分队列继续进行排序，以达到整个序列有序。

- (void)quickSort:(NSMutableArray *)arr left:(NSInteger)left right:(NSInteger)right {
    if (left < right) {
        NSInteger i = left;
        NSInteger j = right;
        NSNumber *base = arr[i];

        while (i < j) {
            while (i < j && [base integerValue] <= [arr[j] integerValue]) {
                j--;
            }
            if (i == j) {
                break;
            }
            arr[i++] = arr[j];

            while (i < j && [base integerValue] >= [arr[i] integerValue]) {
                i++;
            }
            if (i == j) {
                break;
            }
            arr[j--] = arr[i];
        }

        arr[i] = base;
        [self quickSort:arr left:left right:i - 1];
        [self quickSort:arr left:i + 1 right:right];
    }
}

平均时间复杂度：O(nlog2n)，最好时间复杂度：O(nlog2n)，最差时间复杂度：O(n2)，空间复杂度：O(nlog2n)。

二、非比较类排序

不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

1、计数排序

有限范围的整数，记录每个元素出现的次数，并按从小到大顺序输出。
过程：创建计数数组 countArr；所有元素 + X 使得最小元素为 0；遍历队列，每次 countArr[元素值] 计数加 1；遍历 countArr 按计数输出元素 index - X；

2、基数排序

有限个整数，依次按个位、十位、百位。。。排序。
每轮这样：0 - 9 个桶子存储该位相同的元素，然后 0 - 9 桶子中元素串起来。

iOStips

相关

标签