JS实现全排列（递归、循环）、快速排序

递归
1、回溯法（未去重）

function permutate2(arr) {
            let final = [];
            let result = [];

            function p(arr) {
                if (arr.length == 0) {
                    let temp = Array.from(result);
                    final.push(temp);
                    return
                }
                let length = arr.length;
                for (let i = 0; i < length; i++) {
                    result.push(arr[i])
                    let newArr = Array.from(arr);
                    newArr.splice(i, 1);
                    p(newArr);
                    result.pop(arr[i]);
                }
            }
            p(arr);
            return final;
        }
        let arr = [1, 2, 3];
        let result = permutate2(arr);
        console.log(result);

2、交换（去重）

function swap(arr, i, j) {
            let temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
function permutate1(arr) {
            let result = [];
            let length = arr.length;

            function p(arr, i, index) {
                if (i <= 0) return;
                for (let j = 0; j <= i; j++) {
                    if (i != j && arr[i] == arr[j]) {
                        continue;
                    }
                    swap(arr, i, j);
                    p(arr, i - 1);
                    if (i == 1) {
                        result.push(Array.from(arr));
                    }
                    swap(arr, i, j);
                }
            }
            p(arr, length - 1);
            return result;
        }
let arr = [1, 2, 3];
        let result = permutate1(arr);
        console.log(result);

循环（去重、内含快速排序等工具函数）

function swap(arr, i, j) {
            let temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

        function reverse(arr, s, e) {
            while (s < e) {
                let temp = arr[s];
                arr[s] = arr[e];
                arr[e] = temp;
                s++;
                e--;
            }
        }

        function getMid(arr, l, r) {
            if (l < r) {
                const mid = Math.floor((l + r) / 2);
                if (arr[l] > arr[mid]) {
                    swap(arr, l, mid);
                }
                if (arr[mid] > arr[r]) {
                    swap(arr, mid, r);
                }
                if (arr[l] > arr[mid]) {
                    swap(arr, l, mid);
                }

                swap(arr, mid, r - 1);
                return arr[r - 1];
            }
        }

        function fastSort(arr, left, right) {

            if (left >= right) return;
            let l = left;
            let r = right - 1;

            let m = getMid(arr, left, right);
            while (l < r) {
                while (arr[l] < m) {
                    l++;
                }
                while (arr[r] >= m) {
                    r--;
                }

                if (l < r) {
                    swap(arr, l, r);
                }
            }
            swap(arr, l, right - 1);
            fastSort(arr, left, l - 1);
            fastSort(arr, l + 1, right);
        }


        function permutate(arr) {
            let length = arr.length;

            fastSort(arr, 0, length - 1);
            reverse(arr, 0, length - 1);
            let str = arr.join('');
            reverse(arr, 0, length - 1);
            let p;
            let result = [];
            result.push(Array.from(arr.values()));
            while (p != str) {
                let i = length - 1;
                for (; i > 0; i--) {
                    if (arr[i - 1] < arr[i]) {
                        for (let j = length - 1; j >= i; j--) {
                            if (arr[j] > arr[i - 1]) {
                                swap(arr, j, i - 1);
                                reverse(arr, i, length - 1);
                                p = arr.join('');
                                result.push(Array.from(arr.values()));
                                // i = length - 1;
                                break;
                            }
                        }
                        break;
                    }
                }
            }
            return result;
        }
let arr = [1, 2, 3, 3, 3];
        let result = permutate(arr);
        console.log(result);