|
快速排序使用分治法策略来把一个序列分为较小和较大的2个子序列，然后递归地排序两个子序列。 步骤为： 挑选基准值：从数列中挑出一个元素，称为“基准”（pivot），
分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成，
递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。
递归到最底部的判断条件是数列的大小是零或一，此时该数列显然已经有序。 选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响。 通常明显比其他算法更快，因为它的内部循环可以在大部分的架构上很有效率地达成。 JAVA代码实现: [color=var(--hltools-color)][size=1.15em]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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| public class QuickSort {
/*
算法思路：
1）从数组中选取一个数字作为分界值
2）对数组进行遍历，大于分界值的 右边去，小于分界值左边
3)遍历+递归
*/
public static void quickSort(int[] arr, int low, int height) {
// 如果low大于等于high，表示区间内少于两个元素，不需要排序
if (low < height) {
// partitioning index，取得划分后的基准元素的位置
int pivot =partition(arr, low, height);
// 递归排序基准值左边的子数组
quickSort(arr, low, pivot - 1);
//递归排序基准值右边的子数组
quickSort(arr, pivot + 1, height);
}
}
// low和high参数表示当前正在处理的数组段的起始索引(low)和结束索索(high)
private static int partition(int[] arr, int low, int high) {
// 选择最后一个元素作为基准值
int pivot = arr[high];
// i是小于基准值部分的最后一个元素的索引
int i = low - 1;
for (int j = low; j < high; j++) {
// 比基准值小的元素
if (arr[j] < pivot) {
i++;
// arr 和 arr[j] 交换位置
changePosition(arr, i, j);
}
}
// 将基凔值换到中间，即大于基准值的元素和小于基准值的元素的分界线
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1; // 返回基准值新的位置
}
public static void changePosition(int[] arr, int left, int right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
// 用于调用的快速排序方法，供外部使用，使得调用者不需要指定数组的起始索引和结束索引
public static void sort(int[] arr) {
quickSort(arr, 0, arr.length - 1);
}
// 主方法，用于测试
public static void main(String[] args) {
int[] array = {10, 7, 8, 9, 1, 5};
sort(array); // 排序数组
// 打印排序后的数组
for (int value : array) {
System.out.print(value + " ");
}
}
} |
| 
发表于 2025-2-5 19:53:58
