堆排序 桶排序 基数排序

堆排序

使用数组和表示堆大小的整数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));
}