/**
 * 快速排序算法实现
 * 时间复杂度: 平均 O(n log n), 最坏 O(n²)
 * 空间复杂度: O(log n)
 */

// 基本快速排序实现
function quickSort(arr) {
    // 基本情况：如果数组长度小于等于1，直接返回
    if (arr.length <= 1) {
        return arr;
    }
    
    // 选择基准值（这里选择最后一个元素）
    const pivot = arr[arr.length - 1];
    const left = [];
    const right = [];
    
    // 将数组分成两部分
    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] <= pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    
    // 递归排序左右两部分，然后合并
    return [...quickSort(left), pivot, ...quickSort(right)];
}

// 原地快速排序（更高效，不创建新数组）
function quickSortInPlace(arr, left = 0, right = arr.length - 1) {
    if (left < right) {
        const pivotIndex = partition(arr, left, right);
        quickSortInPlace(arr, left, pivotIndex - 1);
        quickSortInPlace(arr, pivotIndex + 1, right);
    }
    return arr;
}

// 分区函数
function partition(arr, left, right) {
    // 选择最右边的元素作为基准值
    const pivot = arr[right];
    let i = left - 1;
    
    // 将小于基准值的元素移到左边
    for (let j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            i++;
            [arr[i], arr[j]] = [arr[j], arr[i]]; // 交换元素
        }
    }
    
    // 将基准值放到正确的位置
    [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
    return i + 1;
}

// 优化的快速排序（三数取中法选择基准值）
function quickSortOptimized(arr, left = 0, right = arr.length - 1) {
    if (left < right) {
        const pivotIndex = partitionOptimized(arr, left, right);
        quickSortOptimized(arr, left, pivotIndex - 1);
        quickSortOptimized(arr, pivotIndex + 1, right);
    }
    return arr;
}

// 优化的分区函数（三数取中法）
function partitionOptimized(arr, left, right) {
    // 三数取中法选择基准值
    const mid = Math.floor((left + right) / 2);
    const pivot = medianOfThree(arr, left, mid, right);
    
    // 将基准值移到最右边
    [arr[pivot], arr[right]] = [arr[right], arr[pivot]];
    
    let i = left - 1;
    
    for (let j = left; j < right; j++) {
        if (arr[j] <= arr[right]) {
            i++;
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
    }
    
    [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
    return i + 1;
}

// 三数取中法
function medianOfThree(arr, left, mid, right) {
    const a = arr[left];
    const b = arr[mid];
    const c = arr[right];
    
    if (a < b) {
        if (b < c) return mid;
        else if (a < c) return right;
        else return left;
    } else {
        if (a < c) return left;
        else if (b < c) return right;
        else return mid;
    }
}

// 测试函数
function testQuickSort() {
    console.log("=== 快速排序算法测试 ===");
    
    // 测试用例
    const testCases = [
        [64, 34, 25, 12, 22, 11, 90],
        [5, 2, 4, 6, 1, 3],
        [1],
        [],
        [3, 3, 3, 3],
        [9, 8, 7, 6, 5, 4, 3, 2, 1]
    ];
    
    testCases.forEach((testCase, index) => {
        console.log(`\n测试用例 ${index + 1}: [${testCase.join(', ')}]`);
        
        // 测试基本快速排序
        const arr1 = [...testCase];
        const result1 = quickSort(arr1);
        console.log(`基本快速排序: [${result1.join(', ')}]`);
        
        // 测试原地快速排序
        const arr2 = [...testCase];
        const result2 = quickSortInPlace(arr2);
        console.log(`原地快速排序: [${result2.join(', ')}]`);
        
        // 测试优化快速排序
        const arr3 = [...testCase];
        const result3 = quickSortOptimized(arr3);
        console.log(`优化快速排序: [${result3.join(', ')}]`);
    });
}

// 性能测试函数
function performanceTest() {
    console.log("\n=== 性能测试 ===");
    
    // 生成随机数组
    const generateRandomArray = (size) => {
        return Array.from({length: size}, () => Math.floor(Math.random() * 1000));
    };
    
    const sizes = [100, 1000, 10000];
    
    sizes.forEach(size => {
        const arr = generateRandomArray(size);
        console.log(`\n数组大小: ${size}`);
        
        // 测试基本快速排序
        const arr1 = [...arr];
        const start1 = performance.now();
        quickSort(arr1);
        const end1 = performance.now();
        console.log(`基本快速排序: ${(end1 - start1).toFixed(2)}ms`);
        
        // 测试原地快速排序
        const arr2 = [...arr];
        const start2 = performance.now();
        quickSortInPlace(arr2);
        const end2 = performance.now();
        console.log(`原地快速排序: ${(end2 - start2).toFixed(2)}ms`);
        
        // 测试优化快速排序
        const arr3 = [...arr];
        const start3 = performance.now();
        quickSortOptimized(arr3);
        const end3 = performance.now();
        console.log(`优化快速排序: ${(end3 - start3).toFixed(2)}ms`);
    });
}

// 导出函数供其他模块使用
if (typeof module !== 'undefined' && module.exports) {
    module.exports = {
        quickSort,
        quickSortInPlace,
        quickSortOptimized,
        testQuickSort,
        performanceTest
    };
}

// 如果直接在浏览器中运行，执行测试
if (typeof window !== 'undefined') {
    // 将函数添加到全局作用域
    window.quickSort = quickSort;
    window.quickSortInPlace = quickSortInPlace;
    window.quickSortOptimized = quickSortOptimized;
    window.testQuickSort = testQuickSort;
    window.performanceTest = performanceTest;
    
    console.log("快速排序算法已加载，可以使用以下函数：");
    console.log("- quickSort(arr): 基本快速排序");
    console.log("- quickSortInPlace(arr): 原地快速排序");
    console.log("- quickSortOptimized(arr): 优化快速排序");
    console.log("- testQuickSort(): 运行测试用例");
    console.log("- performanceTest(): 运行性能测试");
}