问题

现在需要对乱序的0-n-1这n个数进行排序，如何在O(N)的时间和O(1)的空间内完成

思路：
乱序的0-n-1排好序后，恰好是value = index，即每个元素的值是多少，排序完成后的下标就是多少，为了方便好记，将元素的value = index的情景称为“在家”
借鉴这样的属性，我们遍历乱序的nums数组，对nums每一个位置，检查该位置上的元素是否在家，若不在家，通过置换让该元素回家；对于置换过来的元素，同样要检查是否在家，不在则继续置换。直到当前位置上的元素在家，才滑动到下一位置检查

例如：排序[3,1,0,2]的过程如下

检查第0位置，发现元素3不在家，让3回家——[2,1,0,3]
继续检查第0位置，发现元素2不在家，让2回家——[0,1,2,3]
继续检查第0位置，发现元素0已经在家，扫描下一位置
...
后续位置123都检查完后，排序完毕

实现代码：

# 交换排序
# 对于一个长度为n的list，如果里面的元素为乱序的0到n-1，那么可以使用交换排序在O(N)时间复杂度内完成排序
class Solution:
    def massage(self, nums: List[int]) -> List[int]:    
        for index in range(len(nums)):
            # 当index处的值nums[index]不等于index（不在家），将其与下标为nums[index]的值交换位置
            while nums[index] != index:
                # 交换
                temp = nums[nums[index]]
                nums[nums[index]] = nums[index]
                nums[index] = temp
        return nums

另外，环形交换还能应用在数组或者矩阵翻转上面
1.leetcode189旋转数组：给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数
[1,2,3,4,5,6]向右移动2个位置，[5,6,1,2,3,4]

思路，我们观察元素的最初位置和最终位置，可以发现它们实际上进行了环形交换，例子中有2个环，1-3-5，2-4-6，即1到3的位置，3到5的位置，5到1的位置，同理2到4的位置，4到6的位置，6到2的位置。那么会有几个环呢？n和k%n的最大公因数个

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if not nums:
            return []
        
        l = len(nums)
        def getGcd(a,b):
            a, b = max(a, b), min(a,b)
            if b == 0:
                return a
            return getGcd(b, a%b)
        # 求最大公因数
        gcd = getGcd(l,k%l)
        count = 0
        # 一个环一个环遍历
        while count < gcd:
            start = begin = count
            pre = nums[start]
            while True:
                # 下一位置
                nextpos = (begin+k) % l
                # 保存下一位置的值
                temp = nums[nextpos]
                # 换位
                nums[nextpos] = pre
                begin = nextpos
                pre = temp
                # 当回到环的起点时break
                if start == begin:
                    break
            count += 1
            

2. N × N 矩阵旋转 90 度

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        # 【思路：由外向内一圈一圈环形交换；规律：a[i][j] = a[j][N-1-i]】
        n = 0
        N = len(matrix)
        a = matrix
        while n <= N // 2:
            # 环形交换当前圈
            for i in range(n, N-n-1):
                # a[n][i]
                ori_pos = begin_position = (n, i)
                pre = a[begin_position[0]][begin_position[1]]
                while True:
                    # 目标位置
                    nextposition = (begin_position[1], N-1-begin_position[0])
                    temp = a[nextposition[0]][nextposition[1]]
                    # 交换
                    a[nextposition[0]][nextposition[1]] = pre
                    pre = temp
                    # 判断是否回到起点
                    begin_position = nextposition
                    if ori_pos == begin_position:
                        break

            n += 1

环形交换模板——存起点，不断交换，判断是否回到起点：

# 保存起点
ori_begin = begin = 起始位置
# 保存起始值
pre = nums[begin]
while True:
    nextpos = f(begin)
    temp = nextpos.val
    nums[nextpos] = pre
    pre = temp
    begin = nextpos
    # 判断是否回起点
    if ori_begin == begin:
        break