algorithm - 旋转 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 位相同。这些位被旋转到最右边的位置。剩下的是两个排序列表。单个合并 channel 对它们进行排序。

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

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