Shulou(Shulou.com)06/03 Report--

1. Counting and sorting

Main idea: the main idea is to count the number of times, to use the direct addressing method, to count the maximum and minimum numbers, to open up the space size of the difference between the two numbers, for duplicate data, use count to count, time complexity O (number of ranges), space complexity O (number of ranges) counting sort suitable for data-intensive situations, when data-intensive and non-duplicated data, you can directly use 'bitmap'. It can save space.

Void CountSort (int* a, size_t size) {assert (a); int max = a [0]; int min = a [0]; int count = 0; for (size_t I = 0; I

< size; ++i) //寻找数组中的最大数和最小数 { if (a[i] < min) { min = a[i]; } if (a[i] >

Max) {max = a [I];}} int* tmp = new int [max-min + 1]; / / Open up storage space and initialize memset (tmp, 0, sizeof (int) * (max-min + 1)); for (size_t I = 0; I

< max - min + 1; ++i) //直接定址法 { int num = a[i] - min; tmp[num]++; } for (size_t i = 0; i < size;) //将排序好的顺序写入a数组中 { for (size_t j = 0; j < max - min + 1; ++j) { count = tmp[j]; while (count--) //对于重复数据需要多次进行写入 { a[i] = j + min; i++; } } } delete[] tmp;} 2.基数排序 主要思想：和'快速转置'的思想相像，开辟两个数组count和start，count用来统计个位上分别为0~9的数据个数，start用来统计数据的开始位置（起始位置为0，下一位的数据开始的位置=上一个数据的开始位置+上一位总的数据个数），另开辟size大小的空间来存放每次排序，下面是低位基数排序，从个位开始排序，然后排序十位，进而百位，直到排到最大数据的最高位，排序结束。 int GetMaxRadix(int* a, size_t size) //寻找最大数据的位数{ int index = 1; //数据最小有一位 int max = 10; for (size_t i = 0; i < size; ++i) { while (a[i] >

= max) / / data greater than 1 bit {index++; max = max * 10;}} return index;} void LSDSort (int* a, size_t size) {assert (a); int index = GetMaxRadix (a, size); / / find the number of the most big data digits int count [10] = {0} / / the number of occurrences of recorded data int start [10] = {0}; / the starting position of recorded data int radex = 1; int* bucket = new int [size]; for (int k = 1; k)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.