PHP O(n) 判斷數組是否有序（升序/降序）的單次遍歷算法

算法邏輯

單次遍歷確定單調方向：首兩元素比較定初始旗標（0=升序，1=降序），後續元素若違反方向則標記無序並提前結束。時間複雜度 O(n)，空間 O(1)。

代碼實現

function JudegSortArray($array) {
    if ($array[0] > $array[1]) $flag = 1; else $flag = 0;
    $temp = $flag;
    $len = count($array);
    for ($i = 1; $i < $len; $i++) {
        if ($flag == 0) {
            if ($array[$i] < $array[$i+1]) continue;
            else { $flag = 1; break; }
        }
        if ($flag == 1) {
            if ($array[$i] > $array[$i+1]) continue;
            else { $flag = 0; break; }
        }
    }
    if ($flag != $temp) echo "無序數組";
    else echo "有序數組";
}

// 測試
$array = [1,2,3,4,6,5];
JudegSortArray($array); // 輸出：無序數組

改進版（返回布爾+方向）

function isSorted($arr) {
    if (count($arr) < 2) return ['sorted'=>true, 'direction'=>0];
    $dir = $arr[0] <= $arr[1] ? 1 : -1; // 1=升序, -1=降序
    for ($i = 1; $i < count($arr)-1; $i++) {
        if (($arr[$i] - $arr[$i+1]) * $dir > 0) return ['sorted'=>false, 'direction'=>0];
    }
    return ['sorted'=>true, 'direction'=>$dir];
}
var_dump(isSorted([1,2,3]));     // sorted=true, dir=1
var_dump(isSorted([3,2,1]));     // sorted=true, dir=-1
var_dump(isSorted([1,3,2]));     // sorted=false

應用場景

• 數據預檢查：確認輸入已排序，可跳過排序步驟。
• 流式數據監控：檢測序列是否保持單調趨勢。