檢查數組的排序性

Question

我需要一個算法用於查找N元素隨機排序的整數 數組要麼已經排序或者沒有排序。

Answer 1

只需遍歷數組，直到找到一個小於前一個的元素。在C/Java'ish僞代碼：

int prev = array[0]; 
boolean sorted = true; 
for (int i=1; i<array.length; i++) { 
    if (array[i] < prev) { 
    sorted = false; 
    break; 
    } 
    prev = array[i]; 
} 

Answer 2

測試如果按升序排序：

for item i in items 
    if i > nextitem 
     return false 

return true