如何快速判断数组是否已排序？3种方法带你轻松搞定！

今天来聊聊一个很基础但很重要的面试题：如何判断一个数组是否已经按升序排列？

问题描述

给定一个数组arr[]，判断它是否按升序排列。允许数组中有相等的元素，连续相等的元素视为有序的。

示例：

• 输入：arr[] = [10, 20, 30, 40, 50]→ 输出：true（已排序）
• 输入：arr[] = [90, 80, 100, 70, 40, 30]→ 输出：false（未排序）

方法一：迭代法（推荐）

这是最直接、最高效的方法。我们只需要遍历数组一次，检查每个元素是否大于或等于前一个元素。如果发现前一个元素大于当前元素，立刻返回false。

思路解析：

以数组[10, 20, 30, 5, 6]为例：

• i = 1：10 <= 20 ✅
• i = 2：20 <= 30 ✅
• i = 3：30 > 5 ❌ 返回 false

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

代码实现（C++）：

#include<iostream>#include<vector>usingnamespacestd;boolisSorted(vector<int>&arr){for(inti=1;i<arr.size();i++)if(arr[i-1]>arr[i])returnfalse;returntrue;}intmain(){vector<int>arr={10,20,30,40,50};cout<<(isSorted(arr)?"true\n":"false\n");return0;}

Python 实现：

defisSorted(arr):n=len(arr)foriinrange(1,n):ifarr[i-1]>arr[i]:returnFalsereturnTrueif__name__=="__main__":arr=[10,20,30,40,50]print("true"ifisSorted(arr)else"false")

Java 实现：

classGFG{staticbooleanisSorted(intarr[]){intn=arr.length;for(inti=1;i<n;i++)if(arr[i-1]>arr[i])returnfalse;returntrue;}publicstaticvoidmain(String[]args){intarr[]={10,20,30,40,50};System.out.print(isSorted(arr)?"true\n":"false\n");}}

刚看完这3种判断数组排序的方法，是不是觉得光靠文字理解算法还是有点抽象？别急，这里安利一个宝藏工具——图码。它把60+种数据结构和算法做成交互式动画，能直观看到每一步操作。更绝的是，你还能输入自定义数据或上传C/C++/Java/Python代码，瞬间生成专属可视化动画。无论是备战408考研、数据结构期末考试，还是刷算法面试题，图码都能帮你把抽象逻辑变得一目了然，还支持24小时AI代码解析。快去试试，学习效率直接拉满。

图码-数据结构与算法交互式可视化平台
访问网站：https://totuma.cn

方法二：递归法

递归方法的核心思想是：检查最后两个元素是否有序，然后递归地检查剩余部分。

步骤：

1. 如果数组大小为0或1，直接返回true（空数组或单元素数组总是有序的）。
2. 检查最后两个元素是否满足arr[n-1] >= arr[n-2]。
3. 如果满足，递归调用检查前 n-1 个元素。

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(n)（递归调用栈）

C++ 实现：

#include<iostream>#include<vector>usingnamespacestd;boolisSortedHelper(vector<int>&arr,intn){if(n==0||n==1)returntrue;returnarr[n-1]>=arr[n-2]&&isSortedHelper(arr,n-1);}boolisSorted(vector<int>&arr){returnisSortedHelper(arr,arr.size());}intmain(){vector<int>arr={10,20,30,40,50};cout<<(isSorted(arr)?"true\n":"false\n");return0;}

Python 实现：

defisSortedhelper(arr,n):ifn==0orn==1:returnTruereturnarr[n-1]>=arr[n-2]andisSortedhelper(arr,n-1)defisSorted(arr):n=len(arr)returnisSortedhelper(arr,n)if__name__=="__main__":arr=[10,20,30,40,50]print("true"ifisSorted(arr)else"false")

方法三：使用内置函数（仅限C++和Python）

这个方法最简单，但只适用于支持相关内置函数的语言。

C++ 使用is_sorted()：

#include<iostream>#include<algorithm>#include<vector>usingnamespacestd;boolisSorted(vector<int>&arr){returnis_sorted(arr.begin(),arr.end());}intmain(){vector<int>arr={10,20,30,40,50};cout<<(isSorted(arr)?"true\n":"false\n");return0;}

Python 使用sorted()：

defis_sorted(arr):returnarr==sorted(arr)if__name__=="__main__":arr=[10,20,30,40,50]print("true"ifis_sorted(arr)else"false")

总结

推荐：在实际开发或面试中，迭代法是最优选择——时间复杂度低、空间复杂度低、代码清晰易懂。

如果对你有帮助，记得点赞收藏哦！