這裡我們將看到另一個排序問題,名為煎餅排序。這個問題很簡單。我們有一個陣列。我們必須對此進行排序。但我們只能使用一種稱為 rev(arr, i) 的運算。這會將 arr 的元素從 0 反轉到第 i 個位置。
這個想法就像是選擇排序。我們反覆將最大元素放在末尾,以減少數組的大小。讓我們看看演算法來理解這個想法。
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
以上是一個煎餅排序問題?的詳細內容。更多資訊請關注PHP中文網其他相關文章!