排序算法之：猴子排序（Bogo Sort） 题目描述 猴子排序（Bogo Sort）是一种基于随机性的排序算法。其核心思想是：随机打乱数组，然后检查数组是否已有序。如果无序，则重复随机打乱和检查的过程，直到数组恰好被随机打乱成有序状态为止。由于排序成功完全依赖于概率，该算法在实际中几乎无用，但其思想有助于理解算法复杂度的边界情况。 解题过程 检查有序性 首先，需要实现一个辅助函数来检查数组是否已按升序排列。遍历数组，比较相邻元素。若所有相邻元素都满足 array[i] <= array[i+1] ，则数组有序；否则无序。 随机打乱数组 若数组无序，则随机打乱其元素顺序。常用的打乱方法是 Fisher-Yates 洗牌算法：从最后一个元素开始，随机选择一个当前位置及之前的元素，并与当前位置交换，逐步向前处理。 循环直到有序 将步骤1和步骤2置于循环中，每次打乱后立即检查有序性。一旦检测到数组有序，立即终止循环并返回排序后的数组。 关键点与复杂度分析 时间复杂度 ：最佳情况为 O(n)（一次随机即有序），最差情况为 O(∞)（可能永远无法随机出有序序列）。平均时间复杂度为 O(n * n!)，因为共有 n! 种排列，每次随机打乱有 1/n ! 的概率得到有序序列。 适用场景 ：仅用于教学或娱乐，不可用于实际排序任务。 优化思路 ：无实际优化空间，但可添加最大尝试次数限制以避免无限循环。 通过以上步骤，你可以实现一个完整的猴子排序算法，直观感受随机化算法的特性。