跳到主要内容

快速排序

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

一、认识​

快速排序(Quicksort) 又称划分交换排序 partition-exchange sort 简称快排。快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。首先从数列中挑出一个元素，并将这个元素称为基准，英文pivot。重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。之后，在子序列中继续重复这个方法，直到最后整个数据序列排序完成。

1.1 特点​

  • 非稳定排序: 如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，则为非稳定排序。

  • 原地排序: 原地排序就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序。

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

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

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

1.2 扩展​

  • 排序算法的稳定性:

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i] = r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。

那么排序算法的稳定性有什么意义呢？其实它只在一种情况下有意义：当要排序的内容是一个对象的多个属性，且其原本的顺序存在意义时，如果我们需要在二次排序后保持原有排序的意义，就需要使用到稳定性的算法。

二、思想​

快速排序算法的基本思想是：

  • 从数组中取出一个数，称之为基数（pivot）

  • 遍历数组，将比基数大的数字放到它的右边，比基数小的数字放到它的左边。遍历完成后，数组被分成了左右两个区域

  • 将左右两个区域视为两个数组，重复前两个步骤，直到排序完成

三、实现​

3.1 数组中心为基准递归​

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;
}

3.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[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;
}

3.3 数组开头为基准递归​

function quickSort(array, start, end) {
  if (start >= end) {
    return;
  }
  let left = start;
  let right = end;
  let pivot = array[left];
  while (left < right) {
    while (left < right && array[right] > pivot) {
      right--;
    }
    while (left < right && array[left] <= pivot) {
      left++;
    }
    [array[left], array[right]] = [array[right], array[left]];
  }
  [array[start], array[left]] = [array[left], array[start]];
  quickSort(array, start, left - 1);
  quickSort(array, right + 1, end);
}

function sort(array) {
  quickSort(array, 0, array.length - 1);
}

3.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[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;
}