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