> For the complete documentation index, see [llms.txt](https://r24zeng.gitbook.io/leetcode-notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://r24zeng.gitbook.io/leetcode-notebook/zhong-yu-shua-dao-100-dao-le-wo-shi-fen-shui-ling/bu-chong-120-dao/31.-next-permutation.md).

# 31. Next Permutation

\# Medium

{% hint style="info" %}
找到规律就好做了

In-place sorting by bubble sort.
{% endhint %}

![Solution](https://3288217904-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LxJcc9A1TOyn5a5HJQ4%2F-MF2seBSGsfHpzr0ZzXR%2F-MF3CkOU1znhlipHo4T7%2F1597798529891.jpg?alt=media\&token=cea1acfd-c1d6-4836-8de1-695c5fb9587a)

{% tabs %}
{% tab title="Python" %}

```python
class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        # find the first pair "ab", a<b from end to start
        i = self.index(nums)
        if i == -1:
            self.sort(nums, 0)
        else:
            # find the closest number in [b:] to exchange with 'a'
            self.exchange(nums, i)
            # sort following numbers in ascending order
            self.sort(nums, i+1)
        
        
    def index(self, nums):
        for i in range(len(nums)-1, 0, -1):
            if nums[i-1] < nums[i]:
                return i-1
        return -1
            
    def exchange(self, nums, i):
        x = i+1
        for j in range(i+2, len(nums)):
            if nums[j] > nums[i] and nums[j] < nums[x]:
                x = j
        nums[i], nums[x] = nums[x], nums[i]
        
    def sort(self, nums, x):
        for i in range(len(nums)-x):
            for j in range(x, len(nums)-1):
                if nums[j] > nums[j+1]:
                    nums[j], nums[j+1] = nums[j+1], nums[j]
```

{% endtab %}
{% endtabs %}

冒泡排序时间复杂度为 $$O(n^2)$$ ，所以整体时间复杂度为 $$O(n^2)$$ ，空间复杂度为 $$O(1)$$&#x20;