关于最常用的排序算法

冒泡排序：

相邻比较，一点点的把最大的“冒泡”到最右边，像气泡冒泡

//冒泡排序
var sortArray = function(nums) {
    let n = nums.length;
    for (let i = 0; i < n - 1; i++) {
        let swapped = false;
        for (let j = 0; j < n - 1 - i; j++) {
            if (nums[j] > nums[j+1]) {
                [nums[j], nums[j+1]] = [nums[j+1], nums[j]];
                swapped = true;
            }
        }
        //如果这一轮没有交换，说明已经排好序了，直接终止
        if (!swapped) break;
    }
    return nums;
};

插入排序：

分为有序区和无序区，从无序区抽取一个数字，把它插入到有序区中他应该在的位置，像打牌一样

//插入排序
var sortArray = function(nums) {
    let n = nums.length;
    //默认第一位是排好序的
    for (let i = 1; i < n; i++) {
        let current = nums[i];
        let j = i - 1;
        //前面的值比要排序的值大，内容后移
        while (j >= 0 && nums[j] > current) {
            nums[j + 1] = nums[j];
            j--;
        }
        nums[j + 1] = current
    }
    return nums;
}

快速排序：

基础版本：

//分为三区
function quickSortBasic(arr) {
    if (arr.length <= 1) return arr;
    //基准点选择，有多种方法，最简单的使用第一个元素，但效率会很低
    const pivot = arr[0];
    const left = [];
    const middle = [];  // 新增：存放等于pivot的元素
    const right = [];
    
    for (let i = 0; i < arr.length; i++) {  // 从0开始，包括pivot
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else if (arr[i] === pivot) {
            middle.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    
    // 注意：middle已经包含了pivot，不需要单独加
    return [...quickSortBasic(left), ...middle, ...quickSortBasic(right)];
}

三路快排

//快速排序
var sortArray = function(nums) {
    if (nums.length <= 1) return nums;
    
    // 主排序函数
    const quickSort = (arr, left = 0, right = arr.length - 1) => {
        // 1. 小数组用插入排序（重要优化！）
        if (right - left < 16) {
            insertionSort(arr, left, right);
            return;
        }
        
        // 2. 三数取中选pivot + 随机化
        const pivotIndex = getPivot(arr, left, right);
        const pivotValue = arr[pivotIndex];
        
        // 3. 三路分区（关键！解决重复元素问题）
        let lt = left;      // 小于pivot的边界
        let gt = right;     // 大于pivot的边界
        let i = left;       // 当前检查位置
        
        // 把pivot换到最左边（方便三路分区）
        [arr[pivotIndex], arr[left]] = [arr[left], arr[pivotIndex]];
        
        while (i <= gt) {
            if (arr[i] < pivotValue) {
                // 小于pivot：换到左边
                [arr[i], arr[lt]] = [arr[lt], arr[i]];
                lt++;
                i++;
            } else if (arr[i] > pivotValue) {
                // 大于pivot：换到右边
                [arr[i], arr[gt]] = [arr[gt], arr[i]];
                gt--;
                // i不增加，因为换过来的元素还没检查
            } else {
                // 等于pivot：跳过
                i++;
            }
        }
        
        // 4. 递归排序左右两部分
        // 注意：arr[lt..gt] 已经是等于pivot的部分，不需要再排序
        quickSort(arr, left, lt - 1);
        quickSort(arr, gt + 1, right);
    };
    
    // 插入排序（处理小数组）
    const insertionSort = (arr, left, right) => {
        for (let i = left + 1; i <= right; i++) {
            const current = arr[i];
            let j = i - 1;
            while (j >= left && arr[j] > current) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = current;
        }
    };
    
    // 优化的pivot选择：三数取中 + 小随机化
    const getPivot = (arr, left, right) => {
        // 基础：三数取中
        const mid = left + Math.floor((right - left) / 2);
        
        // 对三个数进行简单排序
        if (arr[left] > arr[mid]) [arr[left], arr[mid]] = [arr[mid], arr[left]];
        if (arr[left] > arr[right]) [arr[left], arr[right]] = [arr[right], arr[left]];
        if (arr[mid] > arr[right]) [arr[mid], arr[right]] = [arr[right], arr[mid]];
        
        // 额外优化：50%概率使用mid，50%概率随机选（避免针对性测试用例）
        if (Math.random() > 0.5) {
            return mid;
        } else {
            // 在[left, right]范围内随机选
            return left + Math.floor(Math.random() * (right - left + 1));
        }
    };
    
    // 开始排序
    quickSort(nums, 0, nums.length - 1);
    return nums;
};