快速排序(Quick Sort)

介绍复杂度实现简单版本优化版本三路快排基于堆栈的非递归快速排序

介绍

快速排序（Quick Sort）是一种高效的排序算法，其平均时间复杂度为O(nlogn)，是经典的分治算法的应用，在实践中被广泛应用。

快速排序的基本思想是分而治之，先选取一个基准元素，将数组分成小于基准元素的部分和大于基准元素的部分。然后对小于和大于基准元素的部分递归地进行快速排序，最终将整个数组排序。

以下是快速排序的主要思路和实现细节：

思路：

选择一个基准元素（pivot）作为分界点，将数组分为两部分；

将小于等于基准元素的数放到左边，大于基准元素的数放到右边；

递归地对左右两部分进行快速排序，直到序列有序。

复杂度

时间复杂度：

最好情况：每次分区都能将数组均分，时间复杂度为O(nlogn)；

最坏情况：如果数组已经排序好了，时间复杂度为O(n^2)；

平均情况：时间复杂度为O(nlogn)。

空间复杂度：

快速排序是原地排序，不需要额外的存储空间，空间复杂度为O(1)。

实现

简单版本

基于快速排序的思想，我们可以实现一个简单版本的快速排序算法，首先用两个数组分别存储比基准元素小或大的元素，并且选择第一个元素作为基准元素，之后不断递归处理这两个数组，将数组划分为更小的子数组，直到数组长度小于或等于1，此时说明该数组已经是排序的了。在这递归过程中，将原数组划分了许多个细小的子数组，子数组又分为更小的子数组，当所有的子数组都排序后，原数组自然而然地也就是排序好了的。

下面是快排的简单实现版本：


function quickSort(arr) {
  // 递归终止条件，当子数组长度<=1，此时子数组已经是排序好的
  if (arr.length <= 1) {
    return arr;
  }
  const pivotIndex= 0;  // 取第一个元素作为基准元素
  const left = [];  // 比基准元素小的元素
  const right = [];  // 比基准元素相等或更大的元素
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < arr[pivotIndex]) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  // 递归
  return [...quickSort(left), arr[pivotIndex], ...quickSort(right)];
}

这种方法非常直观，也容易实现，但是实际效果并不好，首先在选择基准元素时，使用了常量 pivotIndex = 0，这会导致快排在遇到已经排序好的序列时性能退化，因为最坏情况下时间复杂度会退化到 O(n^2)；其次，每次递归调用 quickSort 函数时都会创建两个新数组，这会占用大量的内存空间，尤其是在排序较大的数组时，可能导致内存溢出。

优化版本

针对上面版本存在的两个问题，可以做两点改进：

可以随机选择某个元素作为基准元素，而不是使用第一个元素，这样可以降低最坏情况(即数组已经排序好了)的概率。

不使用新的数组，直接实现原地排序，以此减少内存占用。

避免创建新数组的思路是，递归调用quickSort函数时，传入原数组和当前数组的边界作为参数，然后每轮递归时就可以使用边界值（也就是子数组的左右下标）来确定子数组，以此避免创建新的数组。

在quickSort函数第一次调用时，边界就是0和arr.length-1。


function quickSort(arr, left=0, right=arr.length-1){
	// ...
}

随机选择数组中的某元素可以用下面语句实现：


const pivotIndex = Math.floor(Math.random() * (right - left + 1)) - left

具体实现代码：


function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left >= right) {
    return;
  }
  const pivotIndex = Math.floor(Math.random() * (right - left + 1)) + left;
  const pivot = arr[pivotIndex];
  let i = left;
  let j = right;
  while (i <= j) {
    while (arr[i] < pivot) {
      i++;
    }
    while (arr[j] > pivot) {
      j--;
    }
    if (i <= j) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
      j--;
    }
  }
  quickSort(arr, left, j);
  quickSort(arr, i, right);
  return arr;
}

核心代码在while代码块中


while (i <= j) {
    while (arr[i] < pivot) {
      i++;
    }
    while (arr[j] > pivot) {
      j--;
    }
    if (i <= j) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
      j--;
    }
  }

首先我们分别从左往右和从右往左扫描数组，找到第一个大于等于基准元素的元素和第一个小于等于基准元素的元素，并将它们交换位置，之后继续向中间缩小范围进行比较和交换位置，直到i≤j不成立，此时arr.slice(left, j + 1)范围的数都小于等于基准元素，arr.slice(i, right + 1)的数都大于等于基准元素。

这种方法实现快排有两点优点：

随机选择基准值，来避免了最坏情况下时间复杂度退化的问题，这在处理大型数据时表现良好。

使用原地排序，避免创建新的数组，减少内存占用。

除了这种方法，还有其他两种优化版本：三路快排和基于堆栈的非递归快速排序算

三路快排

三路快排在处理存在大量重复元素的情况下表现更好。它的基本思路是将数组分成三个部分，分别是小于、等于和大于基准值的部分，并分别对三个部分递归进行快速排序。


function quickSort(arr, left = 0, right = arr.length - 1) {
	if (left >= right) {
		return arr;
	}

	const pivotIndex = Math.floor(Math.random() * (right - left + 1)) + left;
	const pivot = arr[pivotIndex];

	let i = left;
	let l = left;
	let r = right;

	while (i <= r) {
		if (arr[i] < pivot) {
			[arr[i], arr[l]] = [arr[l], arr[i]];
			l++;
		} else if (arr[i] > pivot) {
			[arr[i], arr[r]] = [arr[r], arr[i]];
			r--;
			i--;
		}
		i++;
	}

	quickSort(arr, left, l - 1);
	quickSort(arr, r + 1, right);

	return arr;
}

在这个代码实现中，首先使用了三个指针，分别是 l、i和r。l指向小于基准值的元素的右边界，i指向等于基准值的元素的右边界，r指向大于基准值的元素的左边界。在遍历数组时，如果当前元素小于基准值，则将其与小于基准值的元素的右边界交换，并将 l和i分别加1；如果当前元素大于基准值，则将其与大于基准值的元素的左边界交换，并将r减1,i保持不变；如果当前元素等于基准值，则将i加 1。遍历完成后，我们将数组分成了小于、等于和大于基准值的三个部分。然后，我们递归地对小于和大于基准值的两个部分进行快速排序。

排序的核心代码如下：


	while (i <= r) {
		if (arr[i] < pivot) {
			[arr[i], arr[l]] = [arr[l], arr[i]];
			l++;
		} else if (arr[i] > pivot) {
			[arr[i], arr[r]] = [arr[r], arr[i]];
			r--;
			i--;
		}
		i++;
	}

由于指针i从左开始向右扫描，且i表示等于标准值右边界，那么i的左侧就是已经处理过的小于或者等于标准值的元素，所以i左侧的值必定已经小于或者等于基准值，因此当arr[i] < pivot 时，交换位置的arr[l]必定小于或者等于基准值，于是交换位置后i直接向右移动；但是i右侧尚未扫描，进行位置交换的arr[r]不能保证其小于或等于基准值，因此当arr[i] > pivot 时除了交换arr[r]外，还需要保持i不移动，以便再次比较。最后就是等于基准值的元素，直接跳过(i++)。

三路快排与本文前面的快排算法大体相似，主要区别在于三路快排是将数组分为三个分区，即大于基准值的分区、等于基准值的分区和小于基准值的分区，这样可以减少对重复元素的操作。

三路快排的时间复杂度为 O(nlogn)，空间复杂度为 O(logn)。它在处理存在大量重复元素的情况下表现更好，因为它能够将重复元素均匀地分布到三个部分中，从而避免了单个部分包含大量重复元素的情况。

基于堆栈的非递归快速排序

基于堆栈的非递归快速排序算法使用显式的堆栈来代替递归调用。这种实现方式避免了递归调用带来的栈溢出问题，这在处理大型数组时能够获得更好的性能。


function quickSort(arr) {
  const stack = [[0, arr.length - 1]];
  while (stack.length) {
    const [left, right] = stack.pop();
    if (left >= right) {
      continue;
    }
    const pivotIndex = Math.floor(Math.random() * (right - left + 1)) + left;
    const pivot = arr[pivotIndex];
    let i = left;
    let j = right;
    while (i <= j) {
      while (arr[i] < pivot) {
        i++;
      }
      while (arr[j] > pivot) {
        j--;
      }
      if (i <= j) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
        i++;
        j--;
      }
    }
    stack.push([left, j]);
    stack.push([i, right]);
  }
  return arr;
}

在这个代码实现中，我们使用一个显式的堆栈来代替递归调用。我们首先将整个数组的左右边界 [0, arr.length - 1] 压入堆栈中。然后，在每次循环中弹出堆栈的最后一个元素，并对该元素对应的子数组进行排序。在排序过程中，我们使用随机选择基准值的方式来避免最坏情况下时间复杂度的退化。排序完成后，我们将小于基准值的部分和大于基准值的部分的左右边界依次压入堆栈中。在循环结束时，我们得到了一个已经排好序的数组。

基于堆栈的非递归快速排序的时间复杂度和空间复杂度与递归实现方式相同，时间复杂度为 O(nlogn)，空间复杂度为 O(logn)。但是，由于它避免了递归调用带来的栈溢出问题，并且使用了显式的堆栈，因此在处理大型数组时能够获得更好的性能。