煎饼分类问题?
在这里,我们将看到另一个名为Pancakesort的排序问题。这个问题很简单。我们有一个数组。我们必须对此进行排序。但是我们只能使用一个叫做rev(arr,i)的操作。这会将arr的元素从0反转到第i个位置。
这个想法就像选择排序。我们反复将max元素放在最后以减小数组的大小。让我们看一下获得想法的算法。
算法
pancakeSort(arr,n)
Begin
size := n
while size > 1, do
index := index of max element in arr from [0 to size – 1]
rev(arr, index)
rev(arr, size - 1)
size := size - 1
done
End示例
#include<iostream>
using namespace std;
void rev(int arr[], int i) {
int temp, st = 0;
while (st < i) {
temp = arr[st];
arr[st] = arr[i];
arr[i] = temp;
st++;
i--;
}
}
int maxIndex(int arr[], int n) {
int index, i;
for (index = 0, i = 0; i < n; ++i){
if (arr[i] > arr[index]) {
index = i;
}
}
return index;
}
int pancakeSort(int arr[], int n) {
for (int size = n; size > 1; size--) {
int index = maxIndex(arr, size);
if (index != size-1) {
rev(arr, index);
rev(arr, size-1);
}
}
}
int main() {
int arr[] = {54, 85, 52, 25, 98, 75, 25, 11, 68};
int n = sizeof(arr)/sizeof(arr[0]);
pancakeSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
}输出结果
Sorted array: 11 25 25 52 54 68 75 85 98
热门推荐
1 训练狗狗憋尿
2 狗狗追踪训练
3 狗狗训练要多少钱
5 深圳狗狗训练
6 训练狗狗唤回
7 狗狗叫怎么训练
8 狗狗训练班
10 狗狗社会化训练
11 狗狗叫回训练
12 广州狗狗训练学校
13 狗狗训练躺下
14 狗狗随行训练
15 训练狗狗巡回
16 狗狗要怎么训练
17 狗狗喂食训练
18 训练狗狗躺下