1?煎餅排序問題

給定一個(gè)未排序的數(shù)組，任務(wù)是對(duì)給定數(shù)組進(jìn)行排序。您只能在陣列上執(zhí)行以下操作。
翻轉(zhuǎn)（arr，i）：將數(shù)組從0反轉(zhuǎn)為i
示例：
輸入：arr[]={23、10、20、11、12、6、7}
輸出：{6、7、10、11、12、20、23}
輸入：arr[]={0，1，1，0，0}
輸出：{0，0，0，1，1}
方法：與傳統(tǒng)排序算法不同，傳統(tǒng)排序算法試圖以盡可能少的比較進(jìn)行排序，其目標(biāo)是以盡可能少的反轉(zhuǎn)對(duì)序列進(jìn)行排序。
這個(gè)想法是做一些類似于選擇排序的事情。我們一個(gè)接一個(gè)地將最大元素放在末尾，并將當(dāng)前數(shù)組的大小減少一個(gè)。
以下是詳細(xì)步驟。設(shè)給定數(shù)組為arr[]，數(shù)組大小為n。
對(duì)每個(gè)curr_size執(zhí)行以下操作：
（1）查找arr[0到curr_szie-1]中最大元素的索引。讓索引為“mi”；
（2）翻轉(zhuǎn)（arr，mi）；
（3）翻轉(zhuǎn)（arr，curr_size–1）；

2 源代碼

using System;
using System.Collections;
using System.Collections.Generic;namespace Legalsoft.Truffer.Algorithm
{public static partial class Algorithm_Gallery{private static int PSP_Ceil_Search(int[] arr, int low, int high, int x){if (x <= arr[low]){return low;}if (x > arr[high]){return -1;}int mid = (low + high) / 2;if (arr[mid] == x){return mid;}if (arr[mid] < x){if (mid + 1 <= high && x <= arr[mid + 1]){return mid + 1;}else{return PSP_Ceil_Search(arr, mid + 1, high, x);}}if (mid - 1 >= low && x > arr[mid - 1]){return mid;}else{return PSP_Ceil_Search(arr, low, mid - 1, x);}}private static void PSP_Flip(ref int[] arr, int i){int temp, start = 0;while (start < i){temp = arr[start];arr[start] = arr[i];arr[i] = temp;start++;i--;}}private static void PSP_Insertion_Sort(ref int[] arr, int size){for (int i = 1; i < size; i++){int j = PSP_Ceil_Search(arr, 0, i - 1, arr[i]);if (j != -1){PSP_Flip(ref arr, j - 1);PSP_Flip(ref arr, i - 1);PSP_Flip(ref arr, i);PSP_Flip(ref arr, j);}}}}
}

第二部分：

using System;
using System.Collections;
using System.Collections.Generic;namespace Legalsoft.Truffer.Algorithm
{public static partial class Algorithm_Gallery{private static int PSP_Find_Maxium(int[] arr, int n){int mi=0;for (int i = 0; i < n; i++){if (arr[i] > arr[mi]){mi = i;}}return mi;}public static void Pancake_Sort(ref int[] arr, int n){for (int curr_size = n; curr_size > 1; curr_size--){int mi = PSP_Find_Maxium(arr, curr_size);if (mi != curr_size - 1){PSP_Flip(ref arr, mi);PSP_Flip(ref arr, curr_size - 1);}}}}
}

3 源程序

using System;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm
{
? ? public static partial class Algorithm_Gallery
? ? {
? ? ? ? private static int PSP_Ceil_Search(int[] arr, int low, int high, int x)
? ? ? ? {
? ? ? ? ? ? if (x <= arr[low])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? return low;
? ? ? ? ? ? }
? ? ? ? ? ? if (x > arr[high])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? return -1;
? ? ? ? ? ? }
? ? ? ? ? ? int mid = (low + high) / 2;

? ? ? ? ? ? if (arr[mid] == x)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? return mid;
? ? ? ? ? ? }
? ? ? ? ? ? if (arr[mid] < x)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if (mid + 1 <= high && x <= arr[mid + 1])
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? return mid + 1;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? return PSP_Ceil_Search(arr, mid + 1, high, x);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? if (mid - 1 >= low && x > arr[mid - 1])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? return mid;
? ? ? ? ? ? }
? ? ? ? ? ? else
? ? ? ? ? ? {
? ? ? ? ? ? ? ? return PSP_Ceil_Search(arr, low, mid - 1, x);
? ? ? ? ? ? }
? ? ? ? }

? ? ? ? private static void PSP_Flip(ref int[] arr, int i)
? ? ? ? {
? ? ? ? ? ? int temp, start = 0;
? ? ? ? ? ? while (start < i)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? temp = arr[start];
? ? ? ? ? ? ? ? arr[start] = arr[i];
? ? ? ? ? ? ? ? arr[i] = temp;
? ? ? ? ? ? ? ? start++;
? ? ? ? ? ? ? ? i--;
? ? ? ? ? ? }
? ? ? ? }

? ? ? ? private static void PSP_Insertion_Sort(ref int[] arr, int size)
? ? ? ? {
? ? ? ? ? ? for (int i = 1; i < size; i++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? int j = PSP_Ceil_Search(arr, 0, i - 1, arr[i]);

? ? ? ? ? ? ? ? if (j != -1)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? PSP_Flip(ref arr, j - 1);
? ? ? ? ? ? ? ? ? ? PSP_Flip(ref arr, i - 1);
? ? ? ? ? ? ? ? ? ? PSP_Flip(ref arr, i);
? ? ? ? ? ? ? ? ? ? PSP_Flip(ref arr, j);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
?

using System;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm
{
?? ?public static partial class Algorithm_Gallery
?? ?{
?? ??? ?private static int PSP_Find_Maxium(int[] arr, int n)
?? ??? ?{
?? ??? ??? ?int mi=0;
?? ??? ??? ?for (int i = 0; i < n; i++)
?? ??? ??? ?{
?? ??? ??? ??? ?if (arr[i] > arr[mi])
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?mi = i;
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ??? ?return mi;
?? ??? ?}

?? ??? ?public static void Pancake_Sort(ref int[] arr, int n)
?? ??? ?{
?? ??? ??? ?for (int curr_size = n; curr_size > 1; curr_size--)
?? ??? ??? ?{
?? ??? ??? ??? ?int mi = PSP_Find_Maxium(arr, curr_size);
?? ??? ??? ??? ?if (mi != curr_size - 1)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?PSP_Flip(ref arr, mi);
?? ??? ??? ??? ??? ?PSP_Flip(ref arr, curr_size - 1);
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ?}
?? ?}
}
?