快速排序（Quick Sort）是一种高效的、分治法的排序算法，它在实际应用中被广泛采用，因为其性能优越。本文将详细介绍快速排序的工作原理，提供示例和Python、Go、Java以及C语言的实现代码。
快速排序的基本思想
快速排序的核心思想是通过选择一个基准元素，将数组划分为两个子数组：小于基准的子数组和大于基准的子数组。然后，递归地对这两个子数组进行排序，最后将它们合并起来，完成整个排序过程。
以下是快速排序的详细步骤：
- 选择基准元素： 从待排序的数组中选择一个基准元素。通常，我们选择第一个元素，但也可以使用其他策略，如随机选择。
- 划分数组： 将数组中的元素按照与基准元素的比较结果划分为两个子数组，一个包含小于基准的元素，另一个包含大于基准的元素。
- 递归排序： 对划分后的子数组递归地应用快速排序算法，分别排序小于基准的子数组和大于基准的子数组。
- 合并结果： 最后，将已排序的子数组合并起来，形成最终有序的数组。
快速排序的关键在于划分步骤，也就是如何选择基准元素和将元素分配到子数组的过程。这一过程的高效性使得快速排序在大多数情况下表现出色。
快速排序的示例
让我们通过一个示例来理解快速排序的工作原理。假设我们有一个整数数组 [5, 2, 9, 3, 4]，我们希望按升序排序它。
- 选择基准元素： 我们选择第一个元素 5 作为基准。
- 划分数组： 我们遍历数组并将小于等于基准的元素放在左边，大于基准的元素放在右边。在这个示例中，划分后的结果是 [2, 3, 4] [5] [9]。
- 递归排序： 我们对左边的子数组 [2, 3, 4] 和右边的子数组 [9] 分别应用快速排序。
- 合并结果： 最终，将左边的子数组 [2, 3, 4]、基准元素 5 和右边的子数组 [9] 合并起来，得到 [2, 3, 4, 5, 9]，这就是排序后的数组。
快速排序的时间复杂度
快速排序通常具有较快的平均运行时间，并且在许多情况下表现优异。其平均时间复杂度为O(n*log(n))，其中n是数组的长度。在最坏情况下，时间复杂度为O(n^2)，但这种情况较少发生，并且通过随机选择基准元素或使用三取样划分等方法可以避免。
与其他排序算法相比，快速排序通常更快，尤其是在处理大型数据集时。它是许多标准库中的默认排序算法，如Python的sorted()函数和Java的Arrays.sort()方法。
示例代码
以下是快速排序的示例代码，分别使用Python、Go、Java和C语言编写。
Python 快速排序
1
2
3
4
5
6
7
8
9
10
11
12
13
| def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[0]
less = [x for x in arr[1:] if x <= pivot]
greater = [x for x in arr[1:] if x > pivot]
return quick_sort(less) + [pivot] + quick_sort(greater)
arr = [5, 2, 9, 3, 4]
sorted_arr = quick_sort(arr)
print("排序后的数组:", sorted_arr)
|
Go 快速排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| package main
import "fmt"
func quickSort(arr []int) []int {
if len(arr) <= 1 {
return arr
}
pivot := arr[0]
var less, greater []int
for _, v := range arr[1:] {
if v <= pivot {
less = append(less, v)
} else {
greater = append(greater, v)
}
}
less = quickSort(less)
greater = quickSort(greater)
return append(append(less, pivot), greater...)
}
func main() {
arr := []int{5, 2, 9, 3, 4}
sorted_arr := quickSort(arr)
fmt.Println("排序后的数组:", sorted_arr)
}
|
Java 快速排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| import java.util.Arrays;
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
public static int partition(int[] arr, int low, int high) {
int pivot = arr[low];
int left = low + 1;
int right = high;
while (true) {
while (left <= right && arr[left] <= pivot) {
left++;
}
while (left <= right && arr[right] >= pivot) {
right--;
}
if (left <= right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
} else {
break;
}
}
int temp = arr[low];
arr[low] = arr[right];
arr[right] = temp;
return right;
}
public static void main(String[] args) {
int[] arr = {5, 2, 9, 3, 4};
quickSort(arr, 0, arr.length - 1);
System.out.print("排序后的数组: ");
System.out.println(Arrays.toString(arr));
}
}
|
C 语言 快速排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| #include <stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int arr[], int low, int high) {
int pivot = arr[low];
int left = low + 1;
int right = high;
while (1) {
while (left <= right && arr[left] <= pivot) {
left++;
}
while (left <= right && arr[right] >= pivot) {
right--;
}
if (left <= right) {
swap(&arr[left], &arr[right]);
} else {
break;
}
}
swap(&arr[low], &arr[right]);
return right;
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
int main() {
int arr[] = {5, 2, 9, 3, 4};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("排序后的数组: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
|
以上示例代码展示了不同编程语言中的快速排序算法实现。这些示例帮助你理解快速排序的工作原理，并提供了可供参考和使用的代码示例。无论使用哪种编程语言，快速排序都是一种高效的排序算法，适用于各种应用场景。