快速排序（Quick Sort）

介绍

快速排序（Quick Sort）是一种高效的排序算法，它通过选取一个“基准”元素，将数组分为两部分：比基准小的元素和比基准大的元素，然后递归地对这两部分进行排序，从而实现对整个数组的排序。快速排序由英国计算机科学家托尼·霍尔（Tony Hoare）于1960年提出，因此也被称为霍尔排序。

所谓最差时间复杂度

最优时间复杂度：O(n log n)；
最差时间复杂度：O(n²)；
平均时间复杂度：O(n log n)；

看上去最差有点差（和冒泡一样），实际上就没见过最差情况；

动画模拟

工作原理

快速排序的工作原理基于分治策略，具体步骤如下：

选取基准： 从待排序序列中选取一个元素作为基准值（pivot）。基准值的选择可以是任意的，但常见的选择方法包括选取序列的第一个元素、最后一个元素、中间元素或随机选取一个元素。
分区操作： 重新排列序列，使得所有比基准值小的元素都移动到基准值的左边，所有比基准值大的元素都移动到基准值的右边。在这个分区操作结束时，该基准值就处于序列的中间位置，这个基准值的位置就已经被确定，然后可以将基准值位置左边的子序列和右边的子序列独立排序。
递归排序： 递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。递归的最底部情形是序列的大小是零或一，也就是已经排序好了。

在快速排序的具体实现中，分区操作通常使用双指针技术来实现。一个指针从数组的开头开始向右移动，另一个指针从数组的末尾开始向左移动。当左指针指向的元素小于等于基准元素，且右指针指向的元素大于等于基准元素时，交换这两个元素的位置。当左指针移动到右指针的位置时，整个数组就被划分为了两个子数组。

算法特性

时间复杂度：

平均时间复杂度：O(n log n)。在实际应用中，由于快速排序的随机性，其平均时间复杂度为O(n log n)，因此具有很高的效率。
最坏时间复杂度：O(n²)。当每次选取的基准元素都是当前数组中的最小或最大元素时，会导致每次划分得到的子数组大小相差很大，从而使得递归树的深度很大，排序效率降低。然而，在实际应用中，这种情况很少出现。
最优时间复杂度：O(n log n)。当每次划分都能将数组均匀地分成两部分时，递归树的深度最小，排序效率最高。

空间复杂度：* 快速排序是一种原地排序算法，只需要常数级别的额外空间，因此在处理大规模数据时具有很大的优势。然而，递归调用栈会占用一定的空间，其空间复杂度为O(log n)（在最优情况下）到O(n)（在最坏情况下，但这种情况很少见）。
稳定性： 快速排序是一种不稳定的排序算法。这意味着在排序过程中，相等的元素可能会改变它们的相对顺序。这通常不会影响到排序结果的正确性，但在某些特定的应用场景下，如需要保持元素原始顺序的排序，就需要选择其他稳定的排序算法。
分治策略： 快速排序采用分治策略来解决问题。它将一个大问题分解成若干个小问题来处理，然后将处理结果合并起来得到最终答案。这种策略使得快速排序在处理大规模数据时具有很高的效率。
原地排序： 快速排序只需要常量级的额外空间来存放辅助信息（如递归调用栈和基准值），因此被称为原地排序算法。这使得它在处理大规模数据时具有很大的优势。

源码

vue

<script setup lang="ts">
import SortBarChart from "../comp/sort-bar-chart.vue";
import { ref } from "vue";
import { genRandArray, sortExchangeReact } from "../sort.util";
import { sleep } from "../../../utils/cmm.util";

const data = ref<number[]>(genRandArray(1, 100, 100));

const refreshData = () => {
  data.value = genRandArray(1, 100, 100);
};

const stepInterval = ref<number>(20);
const actives = ref<number[]>([]);

/**
 * 快速排序入口
 * [start, end] 分治处理范围
 * @param start 开始位置
 * @param end 结束位置
 */
const sort = async (start: number = 0, end: number = data.value.length - 1) => {
  let left = start;
  let right = end;
  if (start >= end) return;
  let p = left;
  while (left < right) {
    actives.value = [left, right];
    await sleep(stepInterval.value);
    if (data.value[left] > data.value[right]) {
      sortExchangeReact(data.value, left, right);
      p = p == left ? right : left;
    }
    if (p == left) right--;
    else left++;
  }
  await sort(start, p - 1);
  await sort(p + 1, end);
};
</script>

<template>
  <div class="">
    <a-space direction="horizontal">
      <a-input-number v-model="stepInterval" :step="50" :min="5" style="width: 200px">
        <template #suffix>ms</template>
        <template #prefix> 步进间隔 </template>
      </a-input-number>
      <a-button @click="sort()">开始排序</a-button>
      <a-button @click="refreshData">刷新数据</a-button>
    </a-space>
    <div class="mt-sm" style="height: 300px">
      <sort-bar-chart :data="data" :actives="actives" />
    </div>
  </div>
</template>

<style scoped lang="less"></style>

快速排序（Quick Sort） ​

介绍 ​

动画模拟 ​

工作原理 ​

算法特性 ​

源码 ​

快速排序（Quick Sort）

介绍

动画模拟

工作原理

算法特性

源码