如何检查排序和旋转的数组是升序还是降序

Question

我需要检查排序和旋转的数组是升序还是降序。我需要知道它，以便通过修改的二进制搜索找到旋转计数。

例如：

[5, 6, 1, 2, 3, 4]

按升序排列，但

[2, 1, 6, 5, 4, 3]

按降序排列

Python的实现将非常棒。谢谢你的帮助！

Answer 1

简单的恒定时间方法是检查任意3个相邻的对。最多一个包含边界，因此多数具有与数组相同的顺序。

这些可以是重叠的。例如，如果a、b、c、d在阵列中相邻，则对ab、bc、cd是好的。

Wraparound很好。例如，对于阵列abc，检查ab、bc、ca

Answer 2

am使用Java提供代码，您可以查看它是否有助于

public class IsSorted {
public static void main(String[] args){
int[] list ={4,3,2,1};
System.out.println(isSorted(list));
}
public static int isSorted(int[] a){
if(a.length==0){
return 1;
}
if(a.length==1){
return 1;
}
int[] holdingArray=new int[a.length];
for (int i =0; i<a.length; i++){
holdingArray[i]=a[i];
}

int[] virtualIncreasedArray= new int[holdingArray.length];
int[] virtualDecreasedArray= new int[holdingArray.length];
sortIncrease(holdingArray);
for(int i=0; i<holdingArray.length;i++){
virtualIncreasedArray[i]=holdingArray[i];
}
sortDecrease(holdingArray);
for(int i=0; i<holdingArray.length;i++){
virtualDecreasedArray[i]=holdingArray[i];
}
//check if array is decreasing
for(int i=0; i<virtualDecreasedArray.length;i++){
if(virtualDecreasedArray[i]!=a[i]&&virtualIncreasedArray[i]!=a[i]){
return 0;
}
}
//check if array is increasing

return 1;
}

static void sortIncrease(int[] a){
for(int unsorted=a.length-1; unsorted>0; unsorted--){
for(int i=0; i<unsorted;i++){
if(a[i]>a[i+1]){
swap(a,i,i+1);
}
}
}
}

static void sortDecrease(int[] a){
for(int unsorted=a.length-1; unsorted>0; unsorted--){
for(int i=0; i<unsorted; i++){
if(a[i]<a[i+1]){
swap(a,i,i+1);
}
}
}
}
static void swap(int[] a, int i, int j){
if(i==j){
return;
}
int temp = a[i];
a[i]=a[j];
a[j]=temp;
}

}