【算法】计数排序、桶排序和基数排序详解 |
您所在的位置：网站首页 › 计数式基数排序 › 【算法】计数排序、桶排序和基数排序详解 |
|
01.计数排序、桶排序与基数排序
并不是所有的排序 都是基于比较的，计数排序和基数排序就不是。基于比较排序的排序方法，其复杂度无法突破\(n\log{n}\) 的下限，但是 计数排序 桶排序 和基数排序是分布排序,他们是可以突破这个下限达到O(n)的的复杂度的。 1. 计数排序概念 计数排序是一种稳定的线性时间排序算法。计数排序使用一个额外的数组C，使用 C[i] 来计算 i 出现的次数。然后根据数C来将原数组A中的元素排到正确的位置。 复杂度 计数排序的最坏时间复杂度、最好时间复杂度、平均时间复杂度、最坏空间复杂度都是O(n+k) 。n为元素个数，k为待排序数的最大值。 优缺点 计数排序不是比较排序，排序的速度优于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加1），这使得对于数组中数据范围很大的数组，需要大量的时间和内存。（简言之，不适于大范围数组） 通俗地理解，例如有10个年龄不同的人，统计出有8个人的年龄比A小，那A的年龄就排在第9位，用这个方法可以得到其他每个人的位置，也就排好了序。当然，年龄有重复时需要特殊处理（保证稳定性），这就是为什么最后要反向填充目标数组，以及将每个数字的统计减去1的原因。算法的步骤如下： 找出待排序数组中的最大元素和最小元素。 统计数组中值为 i 的元素出现的次数，存入数组C的第 i 项。 对所有的计数累加（从C中第一个元素开始，每一项和前一项累加）。 反向填充目标数组：将每个元素 i 放在新数组的第 C[i] 项， 每放一个元素就将 C[i] 减去1.C语言实现 #include #include #include void print_arr(int *arr, int n) { int i; printf("%d", arr[0]); for (i = 1; i < n; i++) printf("%d", arr[i]); priintf("\n"); } void counting_sort(int *ini_arr, int *sortrd_arr, int n) { int *count_arr = (int *)malloc(sizeof(int) * 100); int i, j, k; // 初始计数化数组 for (k = 0; k < 100; k++) count_arr[k] = 0; // 步骤二， 计数 for (i = 0; i < 100; i++) count_arr[i]++; // 步骤三， 对所有的计数累加（计算每个数的实际顺序） for (k = 1; k < 100; k++) count_arr[k] += count_arr[k-1]; // 步骤4， 反向填充数组 for (j = n; j > 0; j--) { int elem = ini_arr[j - 1]; // 取待排序元素 int index = count_arr[elem] - 1; // 取待排序元素在有序数组中的序号 sortrd_arr[index] = elem; // 将待排序数组存入结果数组中 count_arr[elem]--; // 修正排序结果，保证sorted_arr数组中元素的稳定性 } /* * 上述句子也可以写为： * sortrd_arr[--count_arr[ini_arr[j -1]]] = ini_arr[j -1]; * */ free(count_arr); } int main(int argc, char **argv) { int n =10; int i; int *arr = (int *)malloc(sizeof(int) * n); int *sorted_arr = (int *)malloc(sizeof(int) * n); srand(time(0)); for (i = 0; i< n; i++) arr[i] = rand()%100; printf("Init array:"); print_arr(arr, n); counting_sort(arr, sorted_arr, n); printf("Sorted_arr；"); free(arr); free(sorted_arr); return 0; } 2. 桶排序概念 桶排序（Bucket sort）或所谓的箱排序，其工作原理是将阵列分到有限数量的桶里。每个桶再分别排序。桶排序是分布排序，不是比较排序，因而不受到比较排序 O(\(n\log{n}\))下限的影响。 复杂度 最坏时间复杂度是O(n^2)， 平均复杂度是O(n+k)，最坏空间复杂度是O(n*k)。 关键步骤 设置一个定量的阵列当作空桶子。 寻访序列，并且把项目一个一个放到对应的桶子去。 对每个不是空的桶进行排序。可以在放入元素的时候进行插入排序，也可以在写回的时候进行快速排序。 从不是空的桶子里把项目放回到原来的序列中。算法实现 假设数据分布在[0, 100]之间，每个桶内部用链表表示，在数据入桶的同时插入排序。然后把各个桶中的数据合并。 #include #include #include using namespace std; const int BUCKET_NUM = 10; // 数据结构的定义，explicit表示不允许构造函数发生隐式转换 struct ListNode { explicit ListNode(int i = 0): mData(i), mNext(NULL){}; ListNode *mNext; int mData; }; ListNode *insert(ListNode *head, int val) { ListNode dummyNode; // 节点指针 ListNode *newNode = new ListNode(val); //待插入的新节点 ListNode *pre , *curr; dummyNode.mNext = head; // 将指针指向链表头部 pre = &dummyNode; // 设置临时指针。pre是当前检查元素的上一个元素 curr = head; while (NULL != curr && curr->mData mNext; } newNode->mNext = curr; // 改变指针指向 pre ->mNext = newNode; return dummyNode.mNext; // 返回链表头节点 } ListNode *Merge(ListNode *head1, ListNode *head2) // 将head2合并到head1 { ListNode dummyNode; ListNode *dummy = &dummyNode; // 临时指针 while(NULL != head1 && NULL != head2) // 循环直到末尾 { if (head1->mData mData) // 类似于归并排序 { dummy->mNext = head1; head1 = head1 -> mNext; }else{ dummy->mNext = head2; head2 = head2->mNext; } dummy = dummy->mNext; } if (NULL != head1) dummy->mNext = head1; if(NULL!=head2) dummy->mNext = head2; return dummyNode.mNext; } void BucketSort(int n,int arr[]){ vector buckets(BUCKET_NUM,(ListNode*)(0)); // 将元素分配到桶 for(int i=0;i max) max = a[i]; return max; } /* * 对数组按照"某个位数"进行排序(桶排序) * * 参数说明： * a -- 数组 * n -- 数组长度 x* exp -- 指数。对数组a按照该指数进行排序。 * * 例如，对于数组a={50, 3, 542, 745, 2014, 154, 63, 616}； * (01) 当exp=1表示按照"个位"对数组a进行排序 * (02) 当exp=10表示按照"十位"对数组a进行排序 * (03) 当exp=100表示按照"百位"对数组a进行排序 * ... */ void count_sort(int a[], int n, int exp) { // 存储"被排序数据"的临时数组 int *output = (int *)malloc(sizeof(int)*n); int i, buckets[10] = {0}; // 将数据出现的次数存储在buckets[]中 for (i = 0; i < n; i++) buckets[ (a[i]/exp)%10 ]++; // 更改buckets[i]。目的是让更改后的buckets[i]的值，是该数据在output[]中的位置。 for (i = 1; i < 10; i++) buckets[i] += buckets[i - 1]; // 将数据存储到临时数组output[]中 for (i = n - 1; i >= 0; i--) { output[buckets[ (a[i]/exp)%10 ] - 1] = a[i]; buckets[ (a[i]/exp)%10 ]--; } // 将排序好的数据赋值给a[] for (i = 0; i < n; i++) a[i] = output[i]; } /* * 基数排序 * * 参数说明： * a -- 数组 * n -- 数组长度 */ void radix_sort(int a[], int n) { int exp; // 指数。当对数组按各位进行排序时，exp=1；按十位进行排序时，exp=10；... int max = get_max(a, n); // 数组a中的最大值 // 从个位开始，对数组a按"指数"进行排序 for (exp = 1; max/exp > 0; exp *= 10) count_sort(a, n, exp); } void main() { int i; int a[] = {53, 3, 542, 748, 14, 214, 154, 63, 616}; int ilen = LENGTH(a); printf("before sort:"); for (i=0; i |
今日新闻 |
点击排行 |
|
推荐新闻 |
|
图片新闻 |
|
专题文章 |
| CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |