【基本有序数组中找到有且仅有的一个无序元素并进行排序之顺序法】2022-10-12

缘由基本有序数组中找到有且仅有的一个无序元素-数据结构与算法-CSDN问答

template <class 形参>
inline void 算交换(形参& a, 形参& b){ 形参 ab = a – b;a -= ab; b += ab; }
template <class 形参>
void 三个升序(形参& a, 形参& b, 形参& c)
{
if (a > c)算交换(a, c);
if (a > b)算交换(a, b);
if (b > c)算交换(b, c);
}
void 基本有序数组中找到有且仅有的一个无序元素(int* a, int n)
{//缘由https://ask.csdn.net/questions/7806512/53941298
int x = 1, k = 0;
while (x < 10)
if (a[x – 1] < a[x] && a[x] < a[x + 1]){ k = 1; x = 0; break; }
else if (a[x – 1] > a[x] && a[x] > a[x + 1]){ x = 0; break; }
else ++x;//检测升序降序
while (x < n – 1)
{
if (k == 1)
{
if (a[x]>a[x + 1])
{
if(n – x>2)
三个升序(a[x], a[x + 1], a[x + 2]);
else
三个升序(a[x – 1], a[x], a[x + 1]);
break;
}
}
else
{
if (a[x]<a[x + 1])
{
if (n – x>2)
三个升序(a[x + 1], a[x], a[x – 1]);//逆升序
else
三个升序(a[x + 1], a[x], a[x – 1]);
break;
}
}
++x;
}
}