小范围排序练习题

题目

已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。
给定一个int数组A，同时给定A的大小n和题意中的k，请返回排序后的数组。

思路

在所有的排序中，与位置有关的排序是插入排序和堆排序，根据题中所描述，移动的位置不超过K，那么插入排序能达到O（n *** k），堆排序可以达到O（logk * n），最后选择使用大小为k的小顶堆来不断进行处理

答案

void swapInt(int i, int j, int *A) {
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}

void adjustMinHeap(int *B, int start, int end) {
    for (int current = start, left = current * 2 + 1; left <= end; current = left, left = left * 2 + 1) {
        // 获取左右节点中最小的
        if (left < end && B[left] > B[left + 1]) {
            left++;
        }
        
        if (B[current] > B[left]) {
            swapInt(current, left, B);
        } else {
            break;
        }
    }
}

vector<int> sortElement(vector<int> A, int n, int k) {
    // 新建一个辅助排序的数组
    int *B = new int[k];
    for (int i = 0; i < k; i++) {
        B[i] = A[i];
    }
    
    // 构造最小堆
    for (int i = k/2 - 1; i >= 0; i--) {
        adjustMinHeap(B, i, k - 1);
    }
    
    // 中间阶段
    for (int i = k; i < n; i++) {
        A[i - k] = B[0];
        B[0] = A[i];
        adjustMinHeap(B, 0, k - 1);
    }
    
    // 最后阶段
    for (int i = n - k; i < n; i++) {
        A[i] = B[0];
        k--;
        B[0] = B[k];
        adjustMinHeap(B, 0, k);
    }
    return A;
}