排序算法之快速排序
算法思想
快速排序是一种分治思想,将每切分的那一块都按照标准值分好左右.一直切分直到最后就是一个排序好的数组.
例如数组
第一步,选取第一个值5作为标准值
第二步,然后定义左右指针,左指针从1位置往后遍历,右指针从后往前遍历,最终需要左右指针的左边都是比标准值小,右边比标准值大
第三步,左指针遍历到1位置,获取到值8,比标准值大,则该值应该放在左指针的右边,此时左指针暂停遍历.
第四步,开始遍历右指针,右指针获取到值7,比标准值5大,则继续往前遍历,遍历到下一个值为4,比标准5小.则右指针暂停遍历.
第五步,交换左右指针的值,使得左右指针值都可以满足左边比标准值小,右边比标准值大
第六步: 重复上述1~5步,直到最终左指针大于等于右指针
第七步: 比较相遇位置的值与标准值,为了满足标准值左边的值都比标准值小,右边的值都比标准值大.如果相遇位置值比标准值小,则直接与相遇位置值交换,如果比标准值大,则与相遇前一个位置的值交换.此处由于6是比标准值5大的,所以将5与6的前一个值2进行交换.
此时可以看到数组经过多次交换后,已经形成了左边都比标准值小,右边都比标准值大的局面
第八步: 以标准值为界,将数组切成两份
分别对左右两边执行1~8步,直到最终切分出来的子数组只要1个元素或2个元素,那么直接比较交换.
这样最终得到的就是一个排序的数组
代码实现
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
68
| public class PivotSort {
public static void main(String[] args) {
int[] arr = {5, 8, 3, 6, 2, 4, 7};
pivotSort(arr, 0, arr.length);
System.out.println(Arrays.toString(arr));
}
public static void pivotSort(int[] nums, int start, int end) {
//如果给的数组最多只有1个值,那么直接返回
if (end - start <= 0) {
return;
//如果是两个值那么直接比较
} else if (end - start == 1) {
if (nums[end] < nums[start]) {
swap(nums, start, end);
}
} else {
//以起始值为标准值
int pivot = nums[start];
//从第一个值往后遍历
int left = start + 1;
//从最后第一个值往前遍历
int right = end;
while (left < right) {
while (left < end && nums[left] < pivot) {
left++;
}
while (right > start && nums[right] >= pivot) {
right--;
}
if (left < right) {
swap(nums, left, right);
}
}
int pivotPosition = left;
//如果左指针已经在右指针之后了
if (left >= right) {
//比较基准值与左指针位置值的大小
if (nums[left] >= pivot) {
pivotPosition = left - 1;
if (left - 1 != start) {
swap(nums, start, left - 1);
}
} else {
swap(nums, start, left);
}
}
//以基准值为界,且成两半,继续执行以上步骤
pivotSort(nums, start, pivotPosition - 1);
pivotSort(nums, pivotPosition + 1, end);
}
}
/**
* 交换值
* @param nums
* @param p1
* @param p2
*/
private static void swap(int[] nums, int p1, int p2) {
nums[p1] = nums[p1] ^ nums[p2];
nums[p2] = nums[p1] ^ nums[p2];
nums[p1] = nums[p1] ^ nums[p2];
}
}
|