快速排序算法
- 快速排序的核心机制:基于分治法,通过选取基准元素划分数组为子数组,确保基准左侧元素小于基准,右侧元素大于基准。
- 递归划分子数组:对基准的左右子数组重复执行相同划分过程,直至每个子数组只含一个元素,完成排序。
- 性能和应用:平均时间复杂度为O(n log n),适用于大多数情况下的高效排序,空间复杂度为O(log n)。
快速排序是一种基于分治法的排序算法,其工作原理如下:
-
首先,通过选择一个基准元素(从数组中选择的元素)来将数组划分为子数组。
在划分数组时,基准元素应该被放置在这样的位置,即小于基准的元素在基准的左侧,大于基准的元素在基准的右侧。
-
然后,对左右子数组使用相同的方法进行划分,这个过程一直持续下去,直到每个子数组包含一个元素。
-
此时,元素已经排好序。最后,将这些元素合并成一个排序好的数组。
快速排序算法的工作原理
1. 选择基准元素
快速排序有不同的变体,其中基准元素可以从不同位置选择。在这里,我们将选择数组的最右侧元素作为基准元素。
2. 重新排列数组
现在,重新排列数组的元素,以便将小于基准的元素放在左侧,大于基准的元素放在右侧。
以下是重新排列数组的步骤:
-
在基准元素处固定一个指针。将从第一个索引开始的元素与基 准元素进行比较。
-
如果元素大于基准元素,则为该元素设置第二个指针。
-
现在,基准元素与其他元素进行比较。如果到达一个小于基准元素的元素,就将较小的元素与之前找到的较大元素交换位置。
-
然后,重复此过程以设置下一个较大元素为第二个指针,并将其与另一个较小元素交换。
-
这个过程一直持续到倒数第二个元素。
-
最后,将基准元素与第二个指针处的元素交换。
3. 划分子数组
然后,分别为左侧和右侧的子部分选择基准元素,然后重复步骤2。
这些子数组将被划分 ,直到每个子数组只包含一个元素。此时,数组已经排好序。
快速排序算法
quickSort(array, leftmostIndex, rightmostIndex)
if (leftmostIndex < rightmostIndex)
pivotIndex <- partition(array,leftmostIndex, rightmostIndex)
quickSort(array, leftmostIndex, pivotIndex - 1)
quickSort(array, pivotIndex, rightmostIndex)
partition(array, leftmostIndex, rightmostIndex)
set rightmostIndex as pivotIndex
storeIndex <- leftmostIndex - 1
for i <- leftmostIndex + 1 to rightmostIndex
if element[i] < pivotElement
swap element[i] and element[storeIndex]
storeIndex++
swap pivotElement and element[storeIndex+1]
return storeIndex + 1
快速排序算法的可视化示例
您可以通过以下示例图形了解快速排序算法的工作原理。
Python、Java 和 C/C++ 中的快速排序代码
# Python 中的快速排序
# 寻找分区位置的函数
def partition(array, low, high):
# 选择数组中的最右侧元素作为基准
pivot = array[high]
# 指向较大元素的指针
i = low - 1
# 遍历所有元素,将每个元素与基准进行比较
for j in range(low, high):
if array[j] <= pivot:
# 如果找到小于基准的元素
# 将其与指针 i 指向的较大元素交换位置
i = i + 1
# 交换 i 处的元素与 j 处的元素
(array[i], array[j]) = (array[j], array[i])
# 将基准元素与 i 处指针指向的较大元素交换位置
(array[i + 1], array[high]) = (array[high], array[i + 1])
# 返回划分的位置
return i + 1
# 执行快速排序的函数
def quickSort(array, low, high):
if low < high:
# 寻找基准元素,使得左侧元素小于基准,右侧元素大于基准
pi = partition(array, low, high)
# 在基准的左侧递归调用
quickSort(array, low, pi - 1)
# 在基准的右侧递归调用
quickSort(array, pi + 1, high)
data = [8, 7, 2, 1
, 0, 9, 6]
print("未排序的数组")
print(data)
size = len(data)
quickSort(data, 0, size - 1)
print('升序排列的排序后数组:')
print(data)
// Java中的快速排序
import java.util.Arrays;
class Quicksort {
// 查找分区位置的方法
static int partition(int array[], int low, int high) {
// 选择最右侧的元素作为基准
int pivot = array[high];
// 用于较大元素的指针
int i = (low - 1);
// 遍历所有元素
// 比较每个元素与基准
for (int j = low; j < high; j++) {
if (array[j] <= pivot) {
// 如果找到小于基准的元素
// 与指针 i 指向的较大元素交换位置
i++;
// 交换 i 处的元素与 j 处的元素
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
// 交换基准元素与 i 处指针指向的较大元素
int temp = array[i + 1];
array[i + 1] = array[high];
array[high] = temp;
// 返回划分位置
return (i + 1);
}
static void quickSort(int array[], int low, int high) {
if (low < high) {
// 寻找基准元素,使得左侧元素小于基准,右侧元素大于基准
int pi = partition(array, low, high);
// 对基准左侧进行递归调用
quickSort(array, low, pi - 1);
// 对基准右侧进行递归调用
quickSort(array, pi + 1, high);
}
}
}
// 主类
class Main {
public static void main(String args[]) {
int[] data = { 8, 7, 2, 1, 0, 9, 6 };
System.out.println("未排序的数组");
System.out.println(Arrays.toString(data));
int size = data.length;
// 调用 quicksort() 对数组 data 进行排序
Quicksort.quickSort(data, 0, size - 1);
System.out.println("升序排列的排序后数组: ");
System.out.println(Arrays.toString(data));
}
}
// C中的快速排序
#include <stdio.h>
// 交换元素的函数
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
// 查找分区位置的函数
int partition(int array[], int low, int high) {
// 选择最右侧的元素作为基准
int pivot = array[high];
// 用于较大元素的指针
int i = (low - 1);
// 遍历数组的每个元素
// 将它们与基准进行比较
for (int j = low; j < high; j++) {
if (array[j] <= pivot) {
// 如果找到小于基准的元素
// 将其与指针 i 指向的较大元素交换位置
i++;
// 交换 i 处的元素与 j 处的元素
swap(&array[i], &array[j]);
}
}
// 将基准元素与 i 处指针指向的较大元素交换位置
swap(&array[i + 1], &array[high]);
// 返回分区点
return (i + 1);
}
void quickSort(int array[], int low, int high) {
if (low < high) {
// 寻找基准元素,使得左侧元素小于基准,右侧元素大于基准
int pi = partition(array, low, high);
// 对基准左侧进行递归调用
quickSort(array, low, pi - 1);
// 对基准右侧进行递归调用
quickSort(array, pi + 1, high);
}
}
// 打印数组元素的函数
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
// 主函数
int main() {
int data[] = { 8, 7, 2, 1, 0, 9, 6 };
int n = sizeof(data) / sizeof(data[0]);
printf("未排序的数组\n");
printArray(data, n);
// 对 data 数组执行快速排序
quickSort(data, 0, n - 1);
printf("升序排列的数组: \n");
printArray(data, n);
}
快速排序算法(C++)
快速排序是一种高效的排序算法,采用分而治之的策略,是在平均情况下性能最好的排序算法之一。
快速排序代码示例(C++)
#include <iostream>
using namespace std;
// 交换元素函数
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
// 打印数组函数
void printArray(int array[], int size) {
int i;
for (i = 0; i < size; i++)
cout << array[i] << " ";
cout << endl;
}
// 重排数组并找到分区点
int partition(int array[], int low, int high) {
// select the rightmost element as pivot
int pivot = array[high];
// pointer for greater element
int i = (low - 1);
// traverse each element of the array
// compare them with the pivot
for (int j = low; j < high; j++) {
if (array[j] <= pivot) {
// if element smaller than pivot is found
// swap it with the greater element pointed by i
i++;
// swap element at i with element at j
swap(&array[i], &array[j]);
}
}
// swap pivot with the greater element at i
swap(&array[i + 1], &array[high]);
// return the partition point
return (i + 1);
}
void quickSort(int array[], int low, int high) {
if (low < high) {
// find the pivot element such that
// elements smaller than pivot are on left of pivot
// elements greater than pivot are on righ of pivot
int pi = partition(array, low, high);
// recursive call on the left of pivot
quickSort(array, low, pi - 1);
// recursive call on the right of pivot
quickSort(array, pi + 1, high);
}
}
// Driver code
int main() {
int data[] = {8, 7, 6, 1, 0, 9, 2};
int n = sizeof(data) / sizeof(data[0]);
cout << "未排序数组: \n";
printArray(data, n);
quickSort(data, 0, n - 1);
cout << "升序排列的数组: \n";
printArray(data, n);
}
快速排序的复杂度
时间复杂度 | |
---|---|
最佳情况 | O(n*log n) |
最坏情 况 | O(n^2) |
平均情况 | O(n*log n) |
空间复杂度 | O(log n) |
稳定性 | 否 |
1. 时间复杂度
-
最坏情况复杂度(Big-O):
O(n^2)
当所选的枢轴元素是数组中的最大或最小元素时,会发生这种情况。这种情况下,枢轴元素位于已排序数组的一个极端。一个子数组总是空的,另一个子数组包含
n - 1
个元素。因此,快速排序只在这个子数组上调用。但是,对于分散的枢轴,快速排序算法的性能更好。
-
最佳情况复杂度(Big-omega):
O(n*log n)
当枢轴元素总是位于中间或接近中间时发生。 -
平均情况复杂度(Big-theta):
O(n*log n)
当上述条件不发生时发生。
2. 空间复杂度
快速排序的空间复杂度为 O(log n)
。
快速排序的应用
在以下情况下使用快速排序算法:
- 编程语言适用于递归
- 时间复杂度重要
- 空间复杂度重要