快速排序

算法思路

1. 选取一个初始值
2. 将所有比该初始值大的数置于初始值的右边,所有比该初始值小的数置于初始值的左边
3. 循环以上操作,直到完成排序为止。

##初级算法实现##
首先,第一轮循环时分为两步。
第一步:从最右边向左依次遍历,查找比初始值小的数,找到之后,更改arr[left]的值, 同时 left ++,即把小的数扔到左边去
第二步:从最左边向右依次遍历,查找比初始值大的数,找到之后,更改arr[right]的值, 同时 right –,即把大的数扔到右边去。
第三步:判断整个数组的排序是否结束,如果没有结束,就依次循环排序
这里 left++ 及 right– 的意思是,由于这一轮排序我们只需要让初始值左边的数均小于初始值,右边的数均大于初始值,因此找到符合条件的数后直接扔到初始值的左边或者右边,而不需要理会扔过去后的大小排序问题,这一轮我们只负责初始值的排序及定位。而在扔过去了之后,此次循环中那一位就不用再判断了,因此++或–。当left与right相等时,表示到了中间点,将其赋值为初始值即可。

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
69
70
71
72
73
public class Quicksort {
private static final int MAXSIZE = 30;
public static int[] arr = new int[MAXSIZE];

public static void main(String[] args) {

for (int i = 0; i < MAXSIZE; i++) {
arr[i] = new Random().nextInt(MAXSIZE);
}

System.out.println("修改前");
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println("");

new Quicksort().sortMethodOne(0, arr.length - 1);

System.out.println("修改后");
for (int i : arr) {
System.out.print(i + " ");
}
}

/**
*
* @param arr
* 目标数组
* @param min
* 排序的数组的起始位
* @param max
* 排序的数组的结束位
*/
private void sortMethodOne(int min, int max) {
// 一个临时变量,用于记录数组左边的位置
int left = min;

// 一个临时变量,用于记录数组右边的位置
int right = max;

// tempNumber很重要,用于记录初始点的数值,并在每次循环判断中将对应位置的值与之进行比较
int tempNumber = arr[left];

while (left < right) {
// 第一步:先从右边向左遍历,找到一个比tempNumber小的数
while (left < right && arr[right] >= tempNumber) {
right--;
}
// 找到后将arr[right]赋值给arr[left]
arr[left] = arr[right];

// 第二步:从左向右遍历,找到一个比tempNumber大的数
while (left < right && arr[left] <= tempNumber) {
left++;
}
// 找到后将arr[left]赋值给arr[right]
arr[right] = arr[left];
}

// 中间数赋值
arr[left] = tempNumber;

// 遍历整理左边的数
if (left > min) {
sortMethodOne(min, left - 1);
}

// 遍历整理右边的数
if (right < max) {
sortMethodOne(left + 1, max);
}
}
}

##算法优化##

方法一: 三数取中间值
思路:取最左边的数A,中间位置的数B,最右边的数C,将他们进行一个排序,取中间的值作为初始值。
例如:
int[] temp = { 9, 5, 6, 8, 4, 3, 2, 7, 1 }交换后的结果为{ 1, 5, 6, 8, 4, 3, 2, 7, 9 },这样的话就相当于是只交换了1和9的位置,而我们又依次循环了很多次,效率比起来的话肯定就太低了。从概率上来讲,通过三数取中间值的效率是最高的,可以避免取到的初始值一开始就为极端数的情况,一定程度上可以提升运行的效率。

方法二: 双向遍历
方法三: 减少交换次数

优化方法在这里只是一个提点,具体如何实现以及其他的优化可以视情况而定,多个优化方法也可以视情况整合,这个就看自己了。