資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究用 C++ 進行煎餅排序
假設我們有一個數組 A，我們將在 A 上執行煎餅排序技術。這裡的主要限制因素是，我們只可以使用一個名為 rev(arr,i) 的操作。這將反轉從 0 到第 i 個位置的 arr 元素。這個想法類似於選擇排序。我們反覆放置最大元素以減小陣列的大小。因此，如果輸入是 [54,85,52,25,98,75,25,11,68]，那麼結果將是 [11,25,25,52,54,68,75,85,98]
為此，我們將按照以下步驟 -
size := n
while size > 1, do
index := arr 中 [0 到 size - 1] 範圍內的最大元素的索引
rev(arr, index)
rev(arr, size - 1)
size := size - 1
讓我們看看以下實現，以獲得更好的理解 -
示例
#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] << " ";
}輸入
[54, 85, 52, 25, 98, 75, 25, 11, 68]
輸出
[11,25,25,52,54,68,75,85,98]
更新於： 2020 年 5 月 2 日
522 次瀏覽
廣告