老青菜

桶排序

2019-05-13

桶排序(BucketSort)是计数排序的升级版,属于非比较类排序。利用函数的映射关系,把大量数据分割成了基本有序的数据块(桶),只需要对桶中的少量数据做先进的比较排序即可。

算法思路

  1. 设置一个定量的数组当作空桶;
  2. 遍历输入数据,并且把数据一个一个放到对应的桶里去;
  3. 对每个不是空的桶进行排序;
  4. 拼接起来桶里的数据。

代码实现

//objc
- (void)bucketSort:(int[] )arr withLength:(int )length {
    if (length<=0) {
        return;
    }
    int max = arr[0];
    int min = arr[0];
    //找出最大、最小值
    for (int i=1; i<length; i++) {
        int temp = arr[i];
        if (max<temp) {
            max = temp;
        }
        if (min>temp) {
            min = temp;
        }
    }
    if (max == min) {
        //元素全部相等
        return;
    }
    //初始化桶
    const int bucketSize = MIN(5, length);
    const int bucketCount = ceill((max-min)/bucketSize)+1;
    NSMutableArray<NSMutableArray *> *buckets = [[NSMutableArray alloc] initWithCapacity:bucketCount];
    for (int i=0; i<bucketCount; i++) {
        buckets[i] = [[NSMutableArray alloc] init];
    }
    //把数据映射到桶里
    for (int i=0; i<length; i++) {
        int temp = arr[i];
        int bucketIndex = (temp-min)/bucketSize;
        [buckets[bucketIndex] addObject:@(temp)];
    }
    //桶内排序
    int index = 0;
    for (int i=0; i<bucketCount; i++) {
        //单个桶排序,这里使用插入排序
        [self bucketInsertSort:buckets[i]];
        //排完序列的桶,重新保存到数组里
        for (int j=0; j<buckets[i].count; j++) {
            arr[index] = [buckets[i][j] intValue];
            index++;
        }
    }
}
/** 桶内使用插入排序 */
- (void)bucketInsertSort:(NSMutableArray *)arr {
    int length = (int)arr.count;
    //第一个元素是有序序列,遍历无序的序列,一个个插入元素
    for (int i=1; i<length; i++) {
        //遍历有序序列,和 待插入的元素比较
        long insertVar = [arr[i] longValue];
        int j = i;
        //如果 待插入元素比 有序序列的元素小,把有序的元素往后移
        while (j-1>=0 && insertVar<=[arr[j-1] longValue]) {
            arr[j] = arr[j-1];
            j--;
        }
        //找到要插入的位置,插入元素
        arr[j] = @(insertVar);
    }
}

算法分析

桶排序的效率取决于桶的数量,桶越多,效率越高。
最好情况下时间复杂度是 O(n),即每个桶只有一个数据。
最坏的情况事件复杂度是 O(n²)
空间复杂度也是O(n+k)

使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章