算法:快速排序

排序算法介绍

维基百科的解释
里面介绍了各种各样的排序算法.
其中的快速排序有一个非常经典的动态图.
quickSort

代码示例

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
public class QuickSort {

public static void main(String[] args) {
int[] array = { 8, 2, 5, 10, 7, 6, 15, 9, 12 };
for (int i : array) {
System.out.print(i);
System.out.print(",");
}
System.out.println();
sort(array, 0, array.length - 1);
for (int i : array) {
System.out.print(i);
System.out.print(",");
}

}

/**
* 快速排序,递归
*
* @param array
* @param low
* @param high
*/
public static void sort(int[] array, int low, int high) {
if (low < high) {
int p = partion(array, low, high);
sort(array, low, p - 1);
sort(array, p + 1, high);
}
}

/**
* 将数据分区,比中轴小的放在左边,大的放在右边
*
* @param array
* @param low
* @param high
* @return
*/
public static int partion(int[] array, int low, int high) {
// 取最低位为中轴,并把该位置当做临时位进行交换
int middle = array[low];
while (low < high) {
// 先从右往左找一个比中轴小的交换到交换位
while (low < high && array[high] > middle) {
high--;
}
array[low] = array[high];
// 先从左往右找一个比中轴大的交换到交换位
while (low < high && array[low] < middle) {
low++;
}
array[high] = array[low];
}
// 整个交换完成后将中轴放回到交换位
array[low] = middle;
return low;
}


// *****************************以下这种实现跟动态图更为接近**************************************

public static int partion2(int[] array, int low, int high) {
int middle = array[low];
int index = low;
low++;
while (low < high) {
while (low < high && array[high] > middle) {
high--;
}
while (low < high && array[low] < middle) {
low++;
}
if (low == high) {
break;
} else {
exchangeElements(array, low, high);
}

}
// 放置中轴
exchangeElements(array, low, index);
return low;
}

/**
* 把array中的index1和index2的内容互换
*
* @param array
* @param index1
* @param index2
*/
public static void exchangeElements(int[] array, int index1, int index2) {
if (array == null || array.length < 1) {
throw new IllegalArgumentException("array can not be null or empty!");
}
if (index1 < 0 || index2 < 0 || index1 > (array.length - 1) || index2 > (array.length - 1)) {
throw new IllegalArgumentException("index must >0 and < array's size");
}
if (index1 == index2) {
return;
}
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}

}