首页 > 基础算法 > 排序 > 对接近有序的数组排序
2014
04-12

对接近有序的数组排序

给定一个数组,数组内每一个元素的位置和其最终排序好的位置 的 距离相差在 k 以内,怎么有效的对其排序?要求时间复杂度为 O(n log k)

例如:当k=2时,如果一个元素的位置为 7,那么再最终的排序数组中该元素的位置在 5-9 之间。

方法一 插入排序

比较每个排序算法的特点,会发现插入排序对于这种情况可能会比较好,因为插入元素时,比较的次数不会超过k。

/* 插入排序 */
void insertionSort(int A[], int size)
{
   int i, key, j;
   for (i = 1; i < size; i++)
   {
       key = A[i];
       j = i-1;

       /* 插入一个元素,对于大的后移。最多比较k次 */
       while (j >= 0 && A[j] > key)
       {
           A[j+1] = A[j];
           j = j-1;
       }
       A[j+1] = key;
   }
}

最多需要k次比较和k个元素后移,因此复杂度为 O(nk)

方法二为堆排序

依然没有达到要求 O(n log k) ,可以使用 堆来继续优化。详细步骤如下:

1) 用最开始的k+1个元素 创建一个大小为k+1的小顶堆。时间为 O(k)
2) 依次从小顶堆中取出最小元素放到结果数组中,然后从剩下的待排序数组中添加新的元素到堆中

从堆中取出一个元素并加入新的元素,为花费 O(Log k )的时间。所以总共的时间复杂度为 O(k) + O((n-k)*logK)

代码实现:

#include<iostream>
using namespace std;
void swap(int *x, int *y);

//小顶堆类
class MinHeap
{
    int *harr; // 堆中的元素数组
    int heap_size; // 堆的大小
public:
    // 构造函数
    MinHeap(int a[], int size);

    // 从给定的下标开始调整堆
    void MinHeapify(int );

    //i的左孩子的下标
    int left(int i) { return (2*i + 1); }

    // i的右孩子的下标
    int right(int i) { return (2*i + 2); }

    //取走最小值(或者说是 root), 并添加新的元素x
    int replaceMin(int x);

    // 取最小值
    int extractMin();
};

// k为每个元素的当前位置和排序数组位置相差的范围
int sortK(int arr[], int n, int k)
{
    // 用前 (k+1) 个元素创建最小堆
    int *harr = new int[k+1];
    for (int i = 0; i<=k && i<n; i++) // i < n 防止 k>n的情况
        harr[i] = arr[i];
    MinHeap hp(harr, k+1);

    for(int i = k+1, ti = 0; ti < n; i++, ti++)
    {
        //如果有剩余元素,就替换掉堆顶
        if (i < n)
            arr[ti] = hp.replaceMin(arr[i]);
        // 否则就依次取走堆顶的元素,
        else
            arr[ti] = hp.extractMin();
    }
}

// 以下是标准的小顶堆的实现
MinHeap::MinHeap(int a[], int size)
{
    heap_size = size;
    harr = a;  
    int i = (heap_size - 1)/2;
    while (i >= 0)
    {
        MinHeapify(i);//构建初始堆
        i--;
    }
}

//从小顶堆中移除堆顶元素
int MinHeap::extractMin()
{
    int root = harr[0];
    if (heap_size > 1)
    {
        harr[0] = harr[heap_size-1];
        heap_size--;
        MinHeapify(0);
    }
    return root;
}

// 替换root和给定的x
int MinHeap::replaceMin(int x)
{
    int root = harr[0];
    harr[0] = x;
    if (root < x)
        MinHeapify(0);
    return root;
}

// 调整小顶堆(递归的方法)
void MinHeap::MinHeapify(int i)
{
    int l = left(i);
    int r = right(i);
    int smallest = i;
    if (l < heap_size && harr[l] < harr[i])
        smallest = l;
    if (r < heap_size && harr[r] < harr[smallest])
        smallest = r;
    if (smallest != i)
    {
        swap(&harr[i], &harr[smallest]);
        MinHeapify(smallest);
    }
}

// 交换
void swap(int *x, int *y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

//打印数组
void printArray(int arr[], int size)
{
   for (int i=0; i < size; i++)
       cout << arr[i] << " ";
   cout << endl;
}

// 测试
int main()
{
    int k = 3;
    int arr[] = {2, 6, 3, 12, 56, 8};
    int n = sizeof(arr)/sizeof(arr[0]);
    sortK(arr, n, k);

    cout << "Following is sorted array\n";
    printArray (arr, n);

    return 0;
}

参考:http://www.geeksforgeeks.org/nearly-sorted-algorithm/


  1. 这道题目的核心一句话是:取还是不取。
    如果当前取,则index+1作为参数。如果当前不取,则任用index作为参数。