详解十大经典排序算法（六）：快速排序（QuickSort）

2024-03-19 23:25| 来源: 网络整理| 查看: 265

算法原理

分区（Partition）：选择一个基准元素，将数组分为两个子数组，小于基准的放在左边，大于基2准的放在右边。递归排序：对左右两个子数组分别进行快速排序。合并：不需要实际的合并操作，因为在分解和递归排序阶段已经完成了排序。

算法描述

快速排序是一种基于分治思想的高效排序算法，由英国计算机科学家 Tony Hoare 于1960年提出。它的核心思想是选择一个基准元素，将数组分成两个子数组，小于基准的在左边，大于基准的在右边，然后对子数组进行递归排序。这一过程持续进行，直到整个数组有序。

算法原理可以简要概括为以下步骤：

选择基准元素：从待排序的数组中选择一个元素作为基准（pivot）。选择基准的方法有多种，常见的包括选择第一个元素、最后一个元素、中间元素，或者随机选择一个元素。

分区过程：将数组中的其他元素按照与基准的大小关系划分到基准的两侧，使得基准左边的元素都小于基准，右边的元素都大于基准。这个过程称为分区（partition）。具体的分区算法有多种，其中一种常见的是Lomuto分区方案和Hoare分区方案。

Lomuto分区方案： a. 从左到右遍历数组，将比基准小的元素放到基准的左侧。 b. 使用一个索引i来记录当前小于基准的元素的位置，初始时i指向数组的起始位置。 c. 遇到小于基准的元素时，将它与索引i指向的元素交换，并将i递增。 d. 最后，将基准元素与索引i指向的元素交换，这样基准元素就放置在了其最终的位置。

Hoare分区方案： a. 使用两个指针，一个从数组的左端移动到右端，另一个从右端移动到左端，分别找到大于和小于基准的元素。 b. 交换这两个元素的位置。 c. 重复这个过程，直到两个指针相遇。最后，基准元素的位置就是两指针相遇的位置。

递归排序：对基准左右两侧的子数组分别递归地应用快速排序算法。即，对左侧的子数组和右侧的子数组分别进行步骤1和步骤2，直到每个子数组只有一个元素，此时整个数组就是有序的。

合并结果：不需要实际的合并操作，因为在分区和递归排序阶段已经完成了排序。

动画演示

在这里插入图片描述能看懂动画你就理解了快速排序

好吧，可能这个图不太好理解，看个视频讲解把： B站小姐姐讲解快速排序>>>

代码实现

public static void quickSort(int[] arr, int low, int high) { if (low // 选择最右边的元素作为基准 int pivot = arr[high]; // 将小于基准的元素移动到左边，大于基准的元素移动到右边 int i = low - 1; for (int j = low; j i++; swap(arr, i, j); } } // 将基准元素放到正确的位置 swap(arr, i + 1, high); return i + 1; } private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }

算法复杂度

时间复杂度（最坏）时间复杂度（最好）时间复杂度（平均）空间复杂度稳定性O(n^2)O(n log n)O(n log n)O(log n)不稳定最好情况：在最优情况下，快速排序的时间复杂度是O(n log n)。这通常发生在每次分区都能将数组均匀地分成两半的情况下。平均情况：在平均情况下，快速排序的时间复杂度是O(n log n)。这是因为每次分区都将数组分成两部分，每一部分都需要O(log n)次分区操作。最坏情况：最坏情况下的时间复杂度是O(n^2)，当每次分区都选择最大或最小的元素作为基准时，会导致分区不均衡。空间复杂度：快速排序是一种原地排序算法，它不需要额外的存储空间来存储临时数据。因此，其空间复杂度是O(1)。这是因为所有的操作都是在输入数组上进行的，只需要常数级别的辅助空间用于存储一些变量，如循环索引、基准元素等。

快速排序的优化方式

快速排序是一种高效的排序算法，但在某些情况下可能面临最坏情况，即分区不均衡，导致性能下降。

随机选择基准元素：在每次排序开始时，随机选择数组中的一个元素作为基准元素，而不是固定选择第一个或最后一个元素。这可以避免在某些情况下导致最坏情况发生。 public static void quickSort(int[] arr, int low, int high) { if (low int pivot = arr[high]; int i = low - 1; for (int j = low; j i++; swap(arr, i, j); } } swap(arr, i + 1, high); return i + 1; } private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } private static int getRandomIndex(int low, int high) { Random random = new Random(); return random.nextInt(high - low + 1) + low; } 三数取中法：选择基准元素时，不是简单地选择第一个或最后一个元素，而是选择第一个、中间和最后一个元素中的中间值作为基准元素。 public static void quickSort(int[] arr, int low, int high) { if (low if ((arr[i] - arr[j]) * (arr[k] - arr[i]) >= 0) { return i; } else if ((arr[j] - arr[i]) * (arr[k] - arr[j]) >= 0) { return j; } else { return k; } }

这两种优化方式可以在某些情况下提高快速排序的性能，特别是在面对特定输入数据的时候。随机选择基准和三数取中法都有助于减少最坏情况的发生概率，提高算法的鲁棒性。