C#,煎饼排序问题(Pancake Sorting Problem)算法与源代码
2023-09-11 14:15:48 时间
给定一个未排序的数组,任务是对给定数组进行排序。您只能在阵列上执行以下操作。
翻转(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);
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);
}
}
}
}
}
相关文章
- c# 中内部类的简单介绍 C#内部类
- 如何使用T-SQL备份还原数据库及c#如何调用执行? C#中索引器的作用和实现。 jquery控制元素的隐藏和显示的几种方法。 localStorage、sessionStorage用法总结 在AspNetCore中扩展Log系列 - 介绍开源类库的使用(一) span<T>之高性能字符串操作实测
- C#字符串数组排序 C#排序算法大全 C#字符串比较方法 一个.NET通用JSON解析/构建类的实现(c#) C#处理Json文件 asp.net使用Jquery+iframe传值问题
- 微信通过openID发送消息/后台post、get提交并接收数据 C# .NET 配置404,500等错误信息 连接字符串
- C#【必备技能篇】垃圾回收机制(GC)的理解(资源清理+内存管理)
- C#,图论与图算法,图最短路径的迪杰斯特拉(Dijkstra)算法与源代码
- C#,图论与图算法,有向图(Directed Graph)的环(Cycle)的普通判断算法与源代码
- C#,恩廷格尔组合数(Entringer Number)的算法与源程序
- C#,K中心问题(K-centers Problem)的算法与源代码
- C#,卡特兰数(Catalan number,明安图数)的算法源代码
- C#,归并排序算法(Merge Sort Algorithm)的源代码及数据可视化
- 《C#多线程编程实战(原书第2版)》——第3章 使用线程池 3.1 简介
- C# 常用算法 递归
- C# IoC 容器
- Unity 面试题汇总(二)之 C# 位运算、算法基础
- C# List和SortedList简介
- C# 比较多个数组(lambda,匿名比较器)