Knuth洗牌算法，也稱為Knuth-Durstenfeld Shuffle算法，是一種用於生成數組元素隨機排列的算法。該算法由計算機科學家Donald Knuth和Adele Durstenfeld於1969年提出。
Knuth洗牌算法的核心思想是通過遍歷數組中的每個元素，並將其與隨機位置上的元素進行交換，從而實現洗牌操作。具體步驟如下：
從數組的第一個元素開始，記為i。
生成一個隨機數random(i,n)，其中n是數組的大小。
將位置i的元素與隨機數指定的位置上的元素進行交換。
增加i的值，重複步驟2至3，直到i等於n。
這個過程確保了每個元素在每個位置上出現的機率是相等的，即每個位置中出現任意一個數的機率都是相同的。因此，Knuth洗牌算法能夠生成所有可能的排列，且每種排列的機率是相等的。
Knuth洗牌算法的空間複雜度是O(n)，時間複雜度也是O(n)，因為它需要遍歷並交換數組中的每個元素。此外，Knuth洗牌算法是一種in-place的洗牌，即在原有的數組直接進行洗牌操作。