桶排序和计数排序

发表于 | 浏览 次

比较排序,例如归并排序, 堆排序, 快速排序等等. 在比较排序中, 各元素的次序依赖于它们之间的比较.任何比较排序在最坏情况下都要经过O(nlogn)次比较.
快速排序的额外空间复杂度为O(logn)，归并排序的空间复杂度为O(n)，堆排序的空间复杂度为O(1)

桶排序

假设输入数据服从均匀分布, 平均情况下它的时间代价为O(n). 与计数排序类似,因为对输入数据做了某种假设, 桶排序的速度也很快.具体来说,计数排序假设数据都属于一个小区间内的整数, 而桶排序假设输入是由一个随机过程产生,该过程将元素均匀,独立地分布在[0,1]区间内.
桶排序将[0,1]区间划分为n个相同大小的子区间, 或称为桶.然后将n个输入数分别放在各个桶中.因为输入数据是均匀,独立地分布在[0,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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
void bucketSort1(vector<int> &nums, int bucketSize) {
    if (nums.size() < 2) {
        return;
    }
    vector<vector<int>> help(nums.size(), vector<int>(0));
    int i;
    int maxVal, minVal;
    maxVal = nums[0];
    minVal = nums[0];

    for (int i = 1; i < nums.size(); ++i) {
        if (nums[i] < minVal) {
            minVal = nums[i];
        } else if (nums[i] > maxVal) {
            maxVal = nums[i];
        }
    }

    int bucketCount = (maxVal - minVal) / bucketSize + 1;
    vector<vector<int>> buckets(bucketCount, vector<int>(0));

    for (int i = 0; i < nums.size(); ++i) {
        int index = (nums[i] - minVal) / bucketSize;
//        cout << "nums[" << i << "]" << nums[i] << " index:" << index << endl;
        buckets[index].push_back(nums[i]);
    }
    int arrIndex = 0;
    for (int i = 0; i < buckets.size(); ++i) {
        if (buckets[i].empty()) {
            continue;
        }
        insectionSort(buckets[i]);
        
//        cout << "第" << i << "个桶中:";
//        for (int j = 0; j < buckets[i].size(); ++j) {
//            cout << buckets[i][j] << " ";
//        }
//        cout << endl;

        for (int value : buckets[i]) {
            nums[arrIndex++] = value;
        }
    }
}

另一种与桶排序相关的排序方法.

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
// max是数组中元素的最大值, 数组中的元素都在0-max之间
void bucketSort(vector<int> &arr, int max) {
    int i, j;
    vector<int> buckets(max, 0);    // 桶数组,所有

    if (arr.empty() || max < 1) {
        return;
    }
    for (int i = 0; i < arr.size(); ++i) {
        buckets[arr[i]]++;
    }

    // bucket[i]表示数组arr中等于i的元素个数
    for (int i = 0, j = 0; i < maxVal; ++i) {
        // 当数组arr中等于i的元素个数不为0,就把元素i加入到原来的数组arr中
        while ((buckets[i]--) > 0) {
            arr[j++] = i;
        }
    }
}

void testBucketSort() {
    vector<int> arr = {8, 2, 3, 4, 3, 6, 6, 3, 9};
    for (int i = 0; i < arr.size(); ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
    cout << endl;
    bucketSort(arr, 10);
    for (int i = 0; i < arr.size(); ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

计数排序

计数排序假设n个输入元素的每一个都是在0-k区间内的一个整数,其中k为某个整数.
计数排序的基本思想:对于每一个输入元素x, 确定小于x的元素个数,.利用这一信息,就可以直接把x放在它在输出数组中的位置上了.

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

void countingSort(vector<int> &nums) {
    if (nums.size() < 2) {
        return;
    }
    int maxVal = -2147483648;
    for (int i = 0; i < nums.size(); ++i) {
        maxVal = maxVal > nums[i] ? maxVal : nums[i];
    }
    vector<int> count(maxVal + 1, 0);
    // count[i]表示数组nums中等于i的元素个数
    for (int i = 0; i < nums.size(); ++i) {
        ++count[nums[i]];
    }

    // count[i]表示数组nums中小于等于i的元素个数
    for (int i = 1; i < count.size(); ++i) {
        count[i] += count[i - 1];
    }
    vector<int> aux(nums.size());
    for (int i = 0; i < nums.size(); ++i) {
        // count[nums[i]]表示数组nums中小于等于nums[i]的元素个数,因此count[nums[i]]也就是nums[i]在排序后数组中的位置
//        cout << "nums[" << i << "]:" << nums[i] << " count:" << count[nums[i]] << endl;
        aux[--count[nums[i]]] = nums[i];
    }
    for (int i = 0; i < nums.size(); ++i) {
        nums[i] = aux[i];
    }
    cout << endl;
}

void testcountingSort() {
//    vector<int> nums{2, 1, 2, 4, 5};
    vector<int> nums{5, 4, 3, 2, 2, 4, 1};
    for (int i = 0; i < nums.size(); ++i) {
        cout << nums[i] << " ";
    }
    cout << endl;
    cout << endl;
    countingSort(nums);
    for (int i = 0; i < nums.size(); ++i) {
        cout << nums[i] << " ";
    }
    cout << endl;
}

基数排序

假设n个d位的元素存放在数组A中, 其中第1位是最低位, 第d位是最高位.

1
2
3
radixSort(A, d)
	for i = 1  to d
		use a stable sort to sort array A on digit i