堆排序、桶排序、基数排序，哪种最适合处理长尾词排序问题？

本文共计1473个文字，预计阅读时间需要6分钟。

使用数组实现堆排序及展示堆的大小：

javavector arr={9, 5, 3, 7, 2};int heapSize=5;heapSize=5 表示数组从索引0开始，包含5个元素，形成一个堆。堆结构就是使用数组实现的完全二叉树结构。

堆排序

使用数组和表示堆大小的整数heapSize表示堆：

vector<int> arr{9, 5, 3, 7, 2}; int heapSize = 5;

heapSize = 5 表示数组从索引0开始的5个元素表示一个堆。

堆结构就是用数组实现的完全二叉树结构。

求数组中索引i位置节点的父子节点：

父节点： (i - 1) / 2

左子节点： 2 * i + 1

右子节点： 2 * i + 2

表示堆的完全二叉树还有一个性质：

完全二叉树中每棵子树的最大值都在堆顶。（对应大根堆）

优先级队列结构，就是堆结构。

堆排序：

1.依次把数组元素加入大根堆

2.依次取出堆顶元素放在数组最后，并调整大根堆。

时间复杂度：O(N * logN) 额外空间复杂度：O(1)

void swap(vector<int>& arr, int i, int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // 把数组index位置的元素加入大根堆 void heapInsert(vector<int>& arr, int index){ // 如果父节点值更大 while(arr[(index - 1) / 2] < arr[index]){ // 父子节点交换 swap(arr, (index - 1) / 2, index); // 循环来到原父节点处 index = (index - 1) / 2; } } // 调整大根堆（因此时堆顶元素并非最大元素） void heapify(vector<int>& arr, int index, int heapSize){ // 计算左子节点 int left = 2 * index + 1; // 如果左子节点在堆中存在 while(left < heapSize){ // large表示左子节点和右子节点中更大者 int large = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left; // 如果父节点大于或等于左子节点更大者，large = 父节点 large = arr[index] >= arr[large] ? index : large; // 如果large = 父节点 则堆已调整好，return if(large == index){ return; } // 将父节点与左右子节点中更大者交换 swap(arr, large, index); // 循环来到左右子节点中更大者处 index = large; // 计算左子节点，继续while循环 left = 2 * index + 1; } } void heapSort(vector<int>& arr){ if(arr.empty() || arr.size() < 2){ return; } // 把数组元素依次加入大根堆 for(int i = 0; i < arr.size(); i++){ heapInsert(arr, i); } int heapSize = arr.size(); // 取出堆顶元素放在数组最后 swap(arr, 0, --heapSize); // 只要堆不为空 while(heapSize > 0){ // 调整大根堆 heapify(arr, 0, heapSize); // 取出堆顶元素放在数组最后 swap(arr, 0, --heapSize); } }

堆排序扩展题目

已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数组进行排序。

假设 k = 6，则：

取数组0~6位置的数放入小根堆里，取出堆顶元素放在数组0位置，再将数组7位置的数放入小根堆里，取出堆顶元素放在1位置

时间复杂度O(N * logk)

// 仿函数cmp<int> 等同于语言自带的greater<int> // 如果是 return x < y 则等同于语言自带的less<int> template<class T> struct cmp{ bool operator()(T x, T y){ return x > y; } }; void sortDistanceLessK(vector<int>& arr, int k){ // 定义小根堆用greater<int> 大根堆用less<int> 刚好相反！！ // 缺省情况下默认为less<> priority_queue<int, vector<int>, cmp<int>> q; // index表示把arr中第几个元素加入到小根堆 int index = 0; for(; index <= k; index++){ q.push(arr[index]); } // i表示把小根堆堆顶元素放到arr中i位置上 int i = 0; for(; index < arr.size(); index++, i++){ arr[i] = q.top();q.pop(); q.push(arr[index]); } while(!q.empty()){ arr[i++] = q.top();q.pop(); } } int main(){ vector<int> nums {1, 4, 3, 4, 2, 4, 6, 8, 9, 10, 12}; sortDistanceLessK(nums, 3); for(int num : nums){ cout << num; } }

桶排序

与基于比较的排序不同，桶排序是基于数据特征对数据排序

假设数据范围都在0-99，对数据排序可以统计每一个数出现的频率

最后依次输出所有数据，时间复杂度O(N)

基数排序

先对所有数据在个位排序，再对十位排序，再对百位排序...

对所有数据的第d位排序时，使用10个桶，从左往右遍历数组，根据第d位的值将数放入相应桶中，最后从第1个桶开始，把桶里的数据倒出来。

最先放入桶的数据最先被倒出来。

int maxbits(vector<int>& arr){ int max = INT_MIN; for(int i : arr){ max = i > max ? i : max; } int res = 0; while(max != 0){ res++; max /= 10; } return res; } // 获取数字x的从右往左第d位的值 int getDigit(int x, int d){ while(d > 1){ x /= 10; d--; } return x % 10; } void radixSort(vector<int>& arr, int l, int r, int digit){ // 拷贝数组，存放每次桶排序的结果 vector<int> bucket(r - l + 1, 0); // 数组的最大值有几位，就要进行几次桶排序 for(int d = 1; d <= digit; d++){ // count[i]表示arr数组中第d位小于等于i的数字有多少个 vector<int> count(10, 0); // 先统计arr数组中第d位等于i的数字有多少个 for(int i = l; i <= r; i++){ count[getDigit(arr[i], d)]++; } // 累加得到 arr数组中第d位小于等于i的数字有多少个 for(int i = 1; i < 10; i++){ count[i] = count[i] + count[i - 1]; } /* count[j]表示arr数组中第d位小于等于j的数有多少 相当于count数组把整个l-r范围按第d位的值分为10片 count[j]表示第j分片的右边界索引 从右往左遍历，当前数第d位是j 因此应将当前数拷贝到bucket数组从左往右第count[j]个位置(count[j]-1) 将count[j]--：下次找到d位同样为j的数就可以拷贝到当前数的前一位置 */ for(int i = r; i >= l; i--){ int j = getDigit(arr[i], d); bucket[count[j] - 1] = arr[i]; count[j]--; } // 把本次排序结果从bucket数组拷贝到arr for(int i = l, j = 0; i <= r; i++, j++){ arr[i] = bucket[j]; } } } void radixSort(vector<int>& arr){ if(arr.empty() || arr.size() < 2){ return; } // maxbits(arr) 表示arr数组中最大值的位数 radixSort(arr, 0, arr.size() - 1, maxbits(arr)); }