以線性時間排序並在適當位置

Question

假設n個記錄的鍵範圍從1到k。

• 編寫一個算法來排序O（n + k）時間內的記錄。
• 您可以在輸入數組外使用O（k）存儲。
• 您的算法是否穩定？

如果我們使用計數排序，我們可以在O（n + k）時間內完成並且穩定，但是它不適用。
如果k = 2，它可以在適當的位置完成，但它不穩定（使用兩個變量來維持k = 0和k = 1的陣列中的索引）
但是對於k> 2我想不出任何好的算法

Answer 1

首先，讓我們老調重彈如何計算排序工作：

• 計數每一個鍵的數組中的頻率存在進行排序。這些計數被寫入大小爲k的數組。
• 計算關鍵計數的部分總和。這給出了排序數組中每個相等鍵的bin的起始位置。
• 將數組中的項目移動到其最終位置，爲每個項目遞增相應倉位的起始位置。

現在的問題是如何執行最後一步就地。就地排列的標準方法是選擇第一個元素，並將其與使用其正確位置的元素交換。這個步驟通過交換元素重複，直到我們擊中屬於第一個位置的元素（一個循環已完成）。然後對第二，第三等位置的元素重複整個過程，直到整個數組已被處理。

計數排序的問題是最終位置不容易獲得，但是通過遞增每個倉在最後一個循環中的起始位置來計算。爲了永遠不會爲元素增加兩次起始位置，我們必須找到一種方法來確定某個位置上的元素是否已經移動到那裏。這可以通過跟蹤每個箱的原始起始位置來完成。如果一個元素位於原始起始位置和箱子下一個元素的位置之間，則它已經被觸摸。

這是C99中的一個實現，它在O(n+k)中運行，並且只需要兩個大小爲k的數組作爲額外存儲。最後的置換步驟不穩定。

#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); 
} 

編輯：這裏是只使用基於莫希特Bhura的做法尺寸k的單個陣列另一個版本。

#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); 
} 

Answer 2

這是我的代碼，在O（N + K）運行時，只使用1大小k（除了大小爲n的主陣列）

#include <stdio.h> 
#include <string.h> 

#include <stdlib.h> 


int main(int argc, char const *argv[]) 
{ 
int n = atoi(argv[1]); 
int k = atoi(argv[2]); 

printf("%d\t%d",n,k); 

int *a,*c; 
int num,index,tmp,i; 
a = (int*)malloc(n*sizeof(int)); 
c = (int*)calloc(k,sizeof(int)); 

srand(time(NULL)); 

for(i=0;i<n;i++) 
{ 
    num = (rand() % (k)); 
    a[i] = num; 
    c[num]++; 
} 

printf("\n\nArray is : \n"); 
for(i=0;i<n;i++) 
{ 
    printf("\t%d",a[i]); 
    if(i%8==7) 
     printf("\n"); 
} 

printf("\n\nCount Array is : \n"); 
for(i=0;i<k;i++) 
{ 
    printf("\t%d(%d)",c[i],i); 
    if(i%8==7) 
     printf("\n"); 
} 

//Indexing count Array 
c[0]--; 
for(i=1;i<k;i++) 
{ 
    c[i] = c[i-1] + c[i];  
} 

printf("\n\nCount Array After Indexing is : \n"); 
for(i=0;i<k;i++) 
{ 
    printf("\t%d(%d)",c[i],i); 
    if(i%8==7) 
     printf("\n"); 
} 

// Swapping Elements in Array 
for(i=0;i<n;i++) 
{ 
    index = c[a[i]]; 
    //printf("\na[%d] = %d, going to position %d",i,a[i],index); 
    c[a[i]]--; 
    if(index > i) 
    { 
     tmp = a[i]; 
     a[i] = a[index]; 
     a[index] = tmp; 
     i--; 
    } 
} 

printf("\n\n\tFinal Sorted Array is : \n\n"); 
for(i=0;i<n;i++) 
{ 
    printf("\t%d",a[i]); 
    if(i%8==7) 
     printf("\n"); 
} 

printf("\n\n"); 

return 0; 
} 

即使此算法中的額外陣列不穩定。所有元素都以相反的順序排列。

P.S：鍵的範圍是0至（K-1）

Answer 3

整值序列的一個例子。排序不穩定。雖然它不像Mohit提供的答案那麼簡潔，但它通過跳過已在其正確時間段中的元素（時間漸近地相同）而略微更快（對於通常情況下，k < n）。在實踐中，我更喜歡Mohit的那種更緊密，更簡單的循環。

def sort_inplace(seq): 
    min_ = min(seq) 
    max_ = max(seq) 
    k = max_ - min_ + 1 
    stop = [0] * k 
    for i in seq: 
     stop[i - min_] += 1 
    for j in range(1, k): 
     stop[j] += stop[j - 1] 
    insert = [0] + stop[:k - 1] 
    for j in range(k): 
     while insert[j] < stop[j] and seq[insert[j]] == j + min_: 
      insert[j] += 1 
    tmp = None 
    for j in range(k): 
     while insert[j] < stop[j]: 
      tmp, seq[insert[j]] = seq[insert[j]], tmp 
      while tmp is not None: 
       bin_ = tmp - min_ 
       tmp, seq[insert[bin_]] = seq[insert[bin_]], tmp 
       while insert[bin_] < stop[bin_] and seq[insert[bin_]] == bin_ + min_: 
        insert[bin_] += 1 

有了更緊密的循環，但還是跳過已搬遷元素：

def dave_sort(seq): 
    min_ = min(seq) 
    max_ = max(seq) 
    k = max_ - min_ + 1 
    stop = [0] * k 

    for i in seq: 
     stop[i - min_] += 1 

    for i in range(1, k): 
     stop[i] += stop[i-1] 
    insert = [0] + stop[:k - 1] 

    for meh in range(0, k - 1): 
     i = insert[meh] 
     while i < stop[meh]: 
      bin_ = seq[i] - min_ 
      if insert[bin_] > i: 
       tmp = seq[insert[bin_]] 
       seq[insert[bin_]] = seq[i] 
       seq[i] = tmp 
       insert[bin_] += 1 
      else: 
       i += 1 

編輯：莫希特的Python中的方法與額外的比特來驗證排序的穩定性的影響。在維基百科條目（最後一段）

from collections import namedtuple 
from random import randrange 

KV = namedtuple("KV", "k v") 

def mohit_sort(seq, key): 
    f = lambda v: getattr(v, key) 
    keys = map(f, seq) 
    min_ = min(keys) 
    max_ = max(keys) 
    k = max_ - min_ + 1 
    insert = [0] * k 

    for i in keys: 
     insert[i - min_] += 1 

    insert[0] -= 1 
    for i in range(1, k): 
     insert[i] += insert[i-1] 

    i = 0 
    n = len(seq) 
    while i < n: 
     bin_ = f(seq[i]) 
     if insert[bin_] > i: 
      seq[i], seq[insert[bin_]] = seq[insert[bin_]], seq[i] 
      i -= 1 
     insert[bin_] -= 1 
     i += 1 


def test(n, k): 
    seq = [] 
    vals = [0] * k 
    for _ in range(n): 
     key = randrange(k) 
     seq.append(KV(key, vals[key])) 
     vals[key] += 1 
    print(seq) 
    mohit_sort(seq, "k") 
    print(seq) 


if __name__ == "__main__": 
    test(20, 3)