对N个旋转位字进行有效排序

Question

给定一个arr包含按排序顺序排列的N位字的数组，是否有一种有效的算法可以将数组中所有元素的旋转结果左一位排序-与使用基数/美国标志排序相比，最好使用较小的常数因子。

sortRotated(arr : Array<Word32>)
  for(I in indices arr)
    arr[i] = rotateLeft(arr[i],1) // 0bXn..n => 0bn..nX
  efficientSort(arr)

这感觉就像它应该在线性时间是可能的，我们知道一些关于元素的排序，其中匹配的组0b0..0，0b0..1，0b1..0和0b1..1。

Answer 1

将输入数组视为两个分区。第一个是前导0位的所有单词的排序列表。第二个是相同的，前导1位。这些位将旋转到最右边的位置。剩下的是两个排序列表。一次合并通过对它们进行排序。

#include <stdio.h>
#include <stdlib.h>

void rotate_and_resort(unsigned *a, int n) {
  // rotate
  for (int i = 0; i < n; ++i) a[i] = (a[i] << 1) | (a[i] >> 31);

  // resort; find the first word with rightmost bit 1
  int rm1;
  for (rm1 = 0; rm1 < n && (a[rm1] & 1) == 0; ++rm1) /* skip */;

  // If all the words end with the same bit, we're done.
  if (rm1 == 0 || rm1 == n) return;

  // make a temp copy for merging
  unsigned t[n];
  for (int i = 0; i < n; ++i) t[i] = a[i];

  // merge
  int i = 0, j = rm1, k = 0;
  while (k < n)
    a[k++] = i < rm1 && t[i] < t[j] ? t[i++] : t[j++];
}

int cmp_unsigned(const void *va, const void *vb) {
  unsigned a = *(unsigned*)va, b = *(unsigned*)vb;
  return a > b ? 1 : a < b ? -1 : 0;
}

int main(void) {
  unsigned n = 100, a[n];
  for (int i = 0; i < n; ++i) a[i] = rand() ^ (rand() << 16);
  qsort(a, n, sizeof *a, cmp_unsigned);
  rotate_and_resort(a, n);
  for (int i = 0; i < n; ++i) printf("%u\n", a[i]);
  return 0;
}

有一种更高级的合并算法，其中临时空间最多为输入大小的一半。在这里，我使用了最简单的算法，该算法可以创建完整副本。