C#，煎饼排序问题（Pancake Sorting Problem）算法与源代码

1 煎饼排序问题

给定一个未排序的数组，任务是对给定数组进行排序。您只能在阵列上执行以下操作。
翻转（arr，i）：将数组从0反转为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}
方法：与传统排序算法不同，传统排序算法试图以尽可能少的比较进行排序，其目标是以尽可能少的反转对序列进行排序。
这个想法是做一些类似于选择排序的事情。我们一个接一个地将最大元素放在末尾，并将当前数组的大小减少一个。
以下是详细步骤。设给定数组为arr[]，数组大小为n。
对每个curr_size执行以下操作：
（1）查找arr[0到curr_szie-1]中最大元素的索引。让索引为“mi”；
（2）翻转（arr，mi）；
（3）翻转（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);
               }
           }
       }
   }
}