排序的线性时间和到位 [英] Sorting in linear time and in place

问题描述

假定n个记录该范围内的键从1到K。

• 在写一个算法来代替记录为O（n + k）的时间进行排序。
• 您可以使用O（K）存储输入数组之外。
• 是你的算法是否稳定？

如果我们用计数排序，我们可以做到这一点在为O（n + k）的时间，是稳定的，但不到位的。照片 如果k = 2它可以就地完成，但其不稳定（使用两个变量，以保持该阵列对于k = 0和k = 1在索引）
但对于k> 2我不能想到什么好的算法中

if we use counting sort to we can do it in O(n+k) time and is stable but its not in place.
if k=2 it can be done in place but its not stable (using two variables to maintain the indexes in the array for k=0 and k=1)
but for k>2 i couldnt think of any good algo

推荐答案

首先，让我们老调重弹了如何计数排序如下：

First, let's rehash how counting sort works:

• 怎么算锐气每一个关键的阵列中进行排序。这些计数都将得到大小 K 的数组。
• 计算按键数量的部分款项。这给出相等的键的排序后的数组，每一槽的开始位置。
• 将数组中的项目到最终位置增加相应仓的起始位置为每个项目。

• Count how often every key exists in the array to be sorted. These counts are written to an array of size k.
• Compute the partial sums of the key counts. This gives the starting position for every bin of equal keys in the sorted array.
• Move the items in the array to their final position incrementing the starting position of the corresponding bin for every item.

现在的问题是如何执行就地的最后一步。为就地置换标准的做法是选择的第一要素，并交换其与需要它的正确位置上的元素。此步骤重复对换元件，直到我们击中属于在第一位置（一个周期已经完成）一个元件。那么整个过程重复，直到在整个阵列已被处理，第二，第三等的位置的元素

Now the question is how to perform the final step in-place. The standard approach for an in-place permutation is to select the first element and swap it with the element that takes its correct position. This step is repeated with the swapped element until we hit a element that belongs in the first position (a cycle has been completed). Then the whole procedure is repeated for the elements at the second, third, etc. position until the whole array has been processed.

用计数排序的问题是，最后的立场是不容易得到，但通过增加在决赛圈的每个仓的起始位置计算。为了永远不会增加起始位置两次的元素，我们必须找到一种方法来确定是否在某个位置的元素已经搬到那里了。这可以通过跟踪原来的开始位置为每个仓来完成。如果一个元素位于原始起始位置和一个箱柜的下一个元件的位置之间，它已经被触摸。

The problem with counting sort is that the final positions are not readily available but are computed by incrementing every bin's starting position in the final loop. In order to never increment the starting position twice for an element, we have to find a way to determine if an element at a certain position has been moved there already. This can be done by keeping track of the original starting position for every bin. If an element lies between the original starting position and the position for the next element of a bin, it has been already touched.

下面是在C99运行在的实施为O（n + k）的和要求尺寸仅为两个数组 K 作为额外的存储空间。最后置换一步并不稳定。

Here's an implementation in C99 that runs in O(n+k) and requires only two arrays of size k as extra storage. The final permutation step is not stable.

#include <stdlib.h>

void in_place_counting_sort(int *a, int n, int k)
{
    int *start = (int *)calloc(k + 1, sizeof(int));
    int *end   = (int *)malloc(k * sizeof(int));

    // Count.
    for (int i = 0; i < n; ++i) {
        ++start[a[i]];
    }

    // Compute partial sums.
    for (int bin = 0, sum = 0; bin < k; ++bin) {
        int tmp = start[bin];
        start[bin] = sum;
        end[bin]   = sum;
        sum += tmp;
    }
    start[k] = n;

    // Move elements.
    for (int i = 0, cur_bin = 0; i < n; ++i) {
        while (i >= start[cur_bin+1]) { ++cur_bin; }
        if (i < end[cur_bin]) {
            // Element has already been processed.
            continue;
        }

        int bin = a[i];
        while (bin != cur_bin) {
            int j = end[bin]++;
            // Swap bin and a[j]
            int tmp = a[j];
            a[j] = bin;
            bin = tmp;
        }
        a[i] = bin;
        ++end[cur_bin];
    }

    free(start);
    free(end);
}

编辑：下面是使用尺寸的只有一个单一的阵列另一个版本氏/ code>基于莫希特Bhura的做法

Here's another version using only a single array of size k based on Mohit Bhura's approach.

#include <stdlib.h>

void in_place_counting_sort(int *a, int n, int k)
{
    int *counts = (int *)calloc(k, sizeof(int));

    // Count.
    for (int i = 0; i < n; ++i) {
        ++counts[a[i]];
    }

    // Compute partial sums.
    for (int val = 0, sum = 0; val < k; ++val) {
        int tmp = counts[val];
        counts[val] = sum;
        sum += tmp;
    }

    // Move elements.
    for (int i = n - 1; i >= 0; --i) {
        int val = a[i];
        int j   = counts[val];

        if (j < i) {
            // Process a fresh cycle. Since the index 'i' moves
            // downward and the counts move upward, it is
            // guaranteed that a value is never moved twice.

            do {
                ++counts[val];

                // Swap val and a[j].
                int tmp = val;
                val  = a[j];
                a[j] = tmp;

                j = counts[val];
            } while (j < i);

            // Move final value into place.
            a[i] = val;
        }
    }

    free(counts);
}

这篇关于排序的线性时间和到位的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！