3
我想提高我的算法知识的0/1排序顺序，我试图解决从Skiena的算法设计手册以下问题：算法：只使用比较
4-26考虑的问题使用比较对n 0和1的序列进行排序。对于x和y两个值的每个比较，算法会学习哪个x保持不变。 （a）给出一个算法，在最坏情况下对n - 1个比较进行排序。证明你的算法是最优的。
（b）在平均情况下给出一种算法对2n/3个比较进行排序（假设每个n个输入为0或1，概率相等）。证明你的算法是最优的。
这是我（一）解决方案：
void sort(int arr[], int length) {
int last_zero = -1;
for (int i = 1; i < length; i++) {
if (arr[i] < arr[i-1]) {
int tmp = arr[i];
arr[i] = arr[++last_zero];
arr[last_zero] = tmp;
} else if (arr[i] > arr[i-1]) {
last_zero = i-1;
}
}
return;
}
有没有更好的方式来做到这一点？
我不知道如何处理（b）部分。有一个类似的问题here，但我不明白那里的解释。
编辑：显然这被认为太模糊，所以让我根据回复进行跟进。
我正在追踪@ amit的回复。我不太明白这部分：
（！！！！！这样I_K = i_h为K = H，I_K =对于k = i_h小时，I_K = j_h 对所有K，H） 。
无论如何，我想我通常理解你提出的解决方案（b）的想法。然而，当我试图为它编写代码时，我发现很难完成。这是我迄今为止，并根据我的测试它成功地对所有（0,1）和（1,0）对进行排序并将相等的对推到数组的末尾，所以我最终得到{全零，全1 ，等于对}。我试图实际移动数组元素，而不是计数0和1的数字。我被困在如何从我至今着手：
int compare(int a, int b);
void shift_right(int arr[], int start, int end);
int prob_4_26_b(int arr[], int length) {
int last_zero = -1;
int last_one = -1;
for (int i = 0; i < length; i += 2) {
int tmp = compare(arr[i], arr[i+1]);
int cur_zero, cur_one;
if (tmp == 0) {
continue;
}
cur_zero = i;
cur_one = i + 1;
/* We have a 0 and a 1 */
/* If this is the first zero we have put it at index 0
and shift everything from index 0 to cur_zero-1 right by 1.
last_zero = 0 and if there are ones last_one++ */
if (last_zero == -1) {
int start = 0;
int end = cur_zero - 1;
shift_right(arr, start, end);
arr[0]=0;
last_zero = 0;
if (last_one != -1) {
last_one++;
}
}
/* If this is not the first zero we have then put it at
last_zero+1 and shift everything from last_zero+1 to cur_zero-1
right by 1. last_zero++ and if we have ones last_one++. */
else {
int start = last_zero + 1;
int end = cur_zero - 1;
shift_right(arr, start, end);
arr[last_zero+1] = 0;
last_zero++;
if (last_one != -1) {
last_one++;
}
}
/* If this is the first one we have put it after the last_zero.
Shift everything from last_zero+1 to cur_one-1 right by 1.
last_one = last_zero+1. */
if (last_one == -1) {
int start = last_zero + 1;
int end = cur_one-1;
shift_right(arr, start, end);
arr[last_zero+1] = 1;
last_one = last_zero + 1;
}
/* If this is not the first one we have put it at last_one+1
and shift everything from last_one+1 to cur_one-1 right by 1.
last_one++ */
else {
int start = last_one + 1;
int end = cur_one - 1;
shift_right(arr, start, end);
arr[last_one+1] = 1;
last_one++;
}
}
return 0;
}
void shift_right(int arr[], int start, int end) {
for (int i = end; i >=start; i--) {
arr[i+1] = arr[i];
}
}
int compare(int a, int b) {
if (a < b)
return -1;
else if (a > b)
return 1;
else
return 0;
}