跳到主要内容

快速排序

2024年04月03日
柏拉文
越努力，越幸运

一、认识​

快速排序(Quicksort) 是一种高效的排序算法，基于分治（Divide and Conquer）策略。其核心思想是: 1. 选择一个基准元素（pivot）; 2. 将数组分区（partition）, 使得所有小于基准的元素位于基准左侧，大于基准的元素位于基准右侧; 3. 对左右两个子数组递归执行相同的操作。

快速排序(Quicksort) 复杂度:

  • 排序方式: In-place (不占用额外内存，只占用常数内存)

  • 时间复杂度: O(nlognlog_{}{n}) [n 代表数据规模及数据量大小]

  • 空间复杂度: O(nlognlog_{}{n})

二、实现​

2.1 数组开头为基准递归(选用当前方案)​

思路:

  1. 分区过程, 分区的目标是将所有小于等于 pivot 的元素移到左侧，大于 pivot 的元素移到右侧: 1. 右指针向左移动直到找到一个小于等于 pivot 的元素; 2. 左指针向右移动直到找到一个大于 pivot 的元素; 3. 经过 1,2, 的调整, 此时的 right 就是小于 pivot 的元素, left 就是大于 pivot 的元素, 需要交换这两个元素的位置; 4. 重复上述步骤直到左右指针相遇

  2. 分区结束, 分区结束后, 需要移动基于 pivot 到正确的位置。left 指针的位置正好是 pivot 应该在的位置。此时，将 pivot（初始时在 start 位置）与 left 位置的元素交换, 使得 pivot 处于正确的排序位置。

  3. 递归子数组, 分区完成后, 对基准元素左右两侧的子数组递归执行相同的排序过程。

function quickSort(nums) {
  const sort = (start, end) => {
    if (start >= end) {
      return;
    }

    let left = start;
    let right = end;
    let pivot = nums[left];

    while (left < right) {
      while (left < right && nums[right] > pivot) {
        right--;
      }
      while (left < right && nums[left] <= pivot) {
        left++;
      }
      [nums[left], nums[right]] = [nums[right], nums[left]];
    }
    [nums[start], nums[left]] = [nums[left], nums[start]];
    sort(start, right - 1);
    sort(left + 1, end);
  };

  sort(0, nums.length - 1);

  return nums;
}

2.2 数组开头为基准迭代​

function sortArray(nums){
    let start=0;
    let end=nums.length-1;
    let stack=[[start,end]];
    while(stack.length>0){
        let range=stack.pop();
        if(range[0]>=range[1]){
            continue 
        }
        let left=range[0];
        let right=range[1];
        let pivot=nums[left];
        while(left<right){
            while(left<right&&nums[right]>pivot){
                right--;
            }
            while(left<right&&nums[left]<=pivot){
                left++;
            }
            [nums[left],nums[right]]=[nums[right],nums[left]];
        }
        [nums[range[0]],nums[left]]=[nums[left],nums[range[0]]];
        if(range[0]<right){
            stack.push([range[0],left-1]);
        }
        if(range[1]>left){
            stack.push([right+1,range[1]]);
        }
    }
    return nums;
}

2.3 数组中心为基准递归​

function sortArray(nums){
    const sort=(nums,start,end)=>{
        if(start>=end){
            return 
        }
        let pivot=nums[Math.floor((start+end)/2)];
        let left=start;
        let right=end;
        while(left<=right){
            while(nums[left]<pivot){
                left++;
            }
            while(nums[right]>pivot){
                right--;
            }
            if(left<=right){
                [nums[left],nums[right]]=[nums[right],nums[left]];
                left++;
                right--;
            }
        }
        sort(nums,start,right);
        sort(nums,left,end);
    }
    sort(nums,0,nums.length-1);
    return nums;
}

2.4 数组中心为基准迭代​

function sortArray(nums){
    let start=0;
    let end=nums.length-1;
    let stack=[[start,end]];
    while(stack.length>0){
        let range=stack.pop();
        if(range[0]>=range[1]){
            continue;
        }
        let left=range[0];
        let right=range[1];
        let pivot=nums[Math.floor((left+right)/2)];
        while(left<=right){
            while(nums[left]<pivot){
                left++;
            }
            while(nums[right]>pivot){
                right--;
            }
            if(left<=right){
                [nums[left],nums[right]]=[nums[right],nums[left]];
                left++;
                right--;
            }
        }
        if(range[0]<right){
            stack.push([range[0],right]);
        }
        if(range[1]>left){
            stack.push([left,range[1]]);
        }
    }
    return nums;
}