sort 排序手写

/**
 * 手动实现数组排序函数，类似Array.sort()
 * @param {Array} arr - 需要排序的数组
 * @param {Function} [compareFn] - 比较函数，格式为(a, b) => number
 * @returns {Array} 排序后的数组（原地排序，修改原数组）
 */
function customSort(arr, compareFn) {
    // 处理默认比较函数（字符串按Unicode，数字按大小）
    if (typeof compareFn !== 'function') {
        compareFn = (a, b) => {
            // 转为字符串后按Unicode编码比较
            const strA = String(a);
            const strB = String(b);
            return strA.localeCompare(strB);
        };
    }

    // 快速排序核心函数
    function quickSort(arr, left, right) {
        // 递归终止条件：子数组长度 <= 1
        if (left >= right) return;

        // 选择基准元素（这里简单选择中间元素）
        const pivotIndex = Math.floor((left + right) / 2);
        const pivot = arr[pivotIndex];

        // 分区操作：将小于基准的放左边，大于基准的放右边
        let i = left;
        let j = right;
        while (i <= j) {
            // 找到左侧第一个需要交换的元素（比基准大）
            while (compareFn(arr[i], pivot) < 0) {
                i++;
            }
            // 找到右侧第一个需要交换的元素（比基准小）
            while (compareFn(arr[j], pivot) > 0) {
                j--;
            }
            // 交换元素
            if (i <= j) {
                [arr[i], arr[j]] = [arr[j], arr[i]];
                i++;
                j--;
            }
        }

        // 递归排序左右子数组
        quickSort(arr, left, j);
        quickSort(arr, i, right);
    }

    // 启动快速排序（从整个数组开始）
    quickSort(arr, 0, arr.length - 1);

    // 类似原生sort，返回原数组（原地排序）
    return arr;
}


// 测试示例
const numbers = [3, 1, 4, 1, 5, 9];
customSort(numbers, (a, b) => a - b);
console.log(numbers); // [1, 1, 3, 4, 5, 9]

const strings = ['banana', 'apple', 'cherry'];
customSort(strings, (a, b) => a.localeCompare(b));
console.log(strings); // ['apple', 'banana', 'cherry']

// 使用默认比较函数（字符串按Unicode，数字按字符串比较）
const mixed = [10, 2, '1', '20'];
customSort(mixed);
console.log(mixed); // ['1', '10', '2', '20']（按字符串Unicode排序）