線形ソートアルゴリズム(カウントソートとバケツソート)C+...
比較ソートの下限はo(nlogn)である.では、時間複雑度o(n)の線形時間ソートアルゴリズムはありますか?一定の仮定条件下では,より速いソートアルゴリズムがあり,以下に紹介するカウントソートやバケツソートなどは線形時間ソートアルゴリズムである.
1、カウントソート
カウントソートは、基数ソートの基礎となる線形時間ソートです.基本的な考え方は、各要素xに対して、xより小さい要素の個数を決定し、xを秩序配列中の位置に直接置くことができる.手順の説明:kはソート対象シーケンスaの値の範囲[0,k]を仮定し、kはソート対象シーケンスの最大値を表す.まず、各値がaに現れる回数を補助配列countで記録し、例えばcount[i]はiのaにおける個数を表す.次にcountの要素値を順番に変更し、count[i]がaのiより大きくない要素の数を表すようにします.その後、a配列を後方から走査し、aの要素はcountの情報に基づいて補助配列bに直接配置される.最後に、秩序シーケンスbをaにコピーする.
vector sortCouting(const vector& v, int mm) {
vector coutv(mm + 1, 0),ret(v.size());
for (auto vi : v) ++coutv[vi];
for (int k1(1); k1 <= mm; ++k1) coutv[k1] += coutv[k1 - 1];
for (int k1(v.size() - 1); k1 >= 0; --k1) ret[--coutv[v[k1]]] = v[k1];
return ret;
}
2、基数排序
在计数排序中，当k很大时，时间和空间的开销都会增大（可以想一下对序列{8888,1234,9999}用计数排序，此时不但浪费很多空间，而且时间方面还不如比较排序）。于是可以把待排序记录分解成个位(第一位)、十位(第二位)....然后分别以第一位、第二位...对整个序列进行计数排序。这样的话分解出来的每一位不超过9，即用计数排序序列中最大值是9。
3、桶排序
基本原理：同计数排序一样，桶排序也对待排序序列作了假设，桶排序假设序列由一个随机过程产生，该过程将元素均匀而独立地分布在区间[0,1)上。基本思想是：把区间[0,1)划分成n个相同大小的子区间，称为桶。将n个记录分布到各个桶中去。如果有多于一个记录分到同一个桶中，需要进行桶内排序。最后依次把各个桶中的记录列出来记得到有序序列。拓展：桶排序是在已经数据的范围的条件下，创建若干个桶，根据相应的比较规则将待排数据落入各个对应的桶中，最后扫描 桶 来实现排序。如果要排序的对象不是小数型，而是整合的集合，就有下面的结论和应用。例如要对大小为[1..1000]范围内的n个整数A[1..n]排序，可以把桶设为大小为10的范围，具体而言，设集合B[1]存储[1..10]的整数，集合B[2]存储(10..20]的整数，……集合B[i]存储((i-1)*10, i*10]的整数，i = 1,2,..100。总共有100个桶。然后对A[1..n]从头到尾扫描一遍，把每个A[i]放入对应的桶B[j]中。 然后再对这100个桶中每个桶里的数字排序，这时可用冒泡，选择，乃至快排，一般来说任何排序法都可以。最后依次输出每个桶里面的数字，且每个桶中的数字从小到大输出，这样就得到所有数字排好序的一个序列了。再例如，假设有10万个人的年龄数据，年龄范围默认是0-99，如何对这10万个数据进行排序？如果用快排啊、归并排序啊...这样的排序算法是可以。但是这样的排序问题更适合桶排序。采用桶排序的方法如下：建立100个桶，这可以用一个 一维数组来表示。a[0...99]，依次扫描10万条数据，根据每条数据的值，记录到桶中。比如，第10个人的年龄是18岁，则a[18]++ （这是将出现的频率记录在桶中，是计数，它是将待排序的元素本身进行比较，而不是将“待排序的元素的组成部分”进行比较）然后，扫描这100个桶，即可得到有序的数组。
vector sortBucket(vector& v, int mm) {
vector bucket(mm + 1, 0);
for (auto vi : v) ++bucket[vi];
int cn(0);
for (int k1(0); k1 <= mm; ++k1) {
if (bucket[k1]) {
while(bucket[k1]--) v[cn++] = k1;
}
}
return v;
}
転載先:https://www.cnblogs.com/lmjy/p/7183898.html